培養信心練手題,POJ2159題目描述如下:
【poj刷題記錄】2159:Ancient Cipher
【poj刷題記錄】2159:Ancient Cipher 這題乍一看挺簡單,但我還是掉了一個坑ORZ。
解題思路其實就是求一下加密前和加密後的字元串是否等價,兩種加密方法,第二種換位置法顯然隻是一個煙霧彈,隻對排列順序做改變,不對替換法之後的序列中字母本身(即涉及的字母有哪些以及每種字母有幾個)做出改變。
我最一開始沒有仔細讀題,被舉的例子誤導,以為替換法是整體字元串統一加一個任意常數k,就把轉換前後的兩個字元串從A到Z排序之後對對應位做差,如果每一位差都相等說明可以通過轉換得到對方,反之不能,WA了很久想不明白錯在哪裡,後來又仔細讀了一遍題發現替換法并不是整個字元串統一加一個随機常數k,而是無規律的随便用字母替換原先字元串中的字母(隻要保證被替換字母相同的位置替換後字母也相同即可) 是以就隻能通過計算每個字母出現的個數,去比對前後兩個字元串中出現k次的字母個數是否相同,相同即可被替換,代碼如下:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
char before[101], after[101];
cin >> after >> before;
int alpha_before[26] = { 0 }, alpha_after[26] = { 0 };
int len = strlen(before), i = 0, flag = 0;
for (i = 0; i < len; i++)
{
alpha_before[before[i] - 'A']++;
alpha_after[after[i] - 'A']++;
}
sort(alpha_before, alpha_before + 26);
sort(alpha_after, alpha_after + 26);
for (i = 0; i < 26; i++)
{
if (alpha_before[i] != alpha_after[i])
{
flag = 1;
cout << "NO" << endl;
break;
}
}
if (flag == 0)
cout << "YES" << endl;
return 0;
}