UVa 468

題目

http://domen111.github.io/UVa-Easy-Viewer/?468

我們今天設計了一個新的加密方式，首先是先寫下明文 $P$

接下來我們會分析 $P$ 當中每個字母出現的頻率

接下來建立一個對照的字串 $S$ ， $S$ 當中每個字都會對應到 $P$ 的某個相同出現頻率的字

我們保證題目當中只會出現字母，並且每個字母的出現頻率都不相同

如果給你 $S$ 以及加密後的密文 $C$，你可以找到 $P$ 嗎?

想法

因為每個字母出現的頻率都是獨特的，所以我們可以先分別統計 $P$ 和 $S$ 的每個字母出現次數

經過排序過後就可以很快對應出每個字母應該要對應到誰

最後建立一個對照表，輸出對著這張表就可以了

Code

//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;

const int Max = 1e9+10;
int n;
char tbl[128];
bool out=false;
string s;

// 利用 statistics 來進行次數統計
// 根據 cnt 來排序，也記錄下了統計的字母是誰
struct statistics{
	char alpha;
	// 用一個極大值，使得這些不存在的字元排序後都會在最後方
	int cnt=Max;
};

bool cmp(statistics p, statistics q){
	if(p.cnt != q.cnt) return p.cnt < q.cnt;
	return false;
}

int main(){
	cin>>n;
	while(n--){
		if(out) cout<<"\n";
		else out=true;
		
		// 方便起見用 128
		statistics text[128], cipher[128];
		// 只需要對 A~z 做初始化
		for(int i=65 ; i<123 ; i++){
			text[i].alpha = cipher[i].alpha = char(i);
			text[i].cnt = cipher[i].cnt = 0;
		}
		
		cin>>s;
		for(int i=0 ; i<s.size() ; i++){
			text[s[i]].cnt++;
		}
		cin>>s;
		for(int i=0 ; i<s.size() ; i++){
			cipher[s[i]].cnt++;
		}
		
		sort(text, text+128, cmp);
		sort(cipher, cipher+128, cmp);
		
		for(int i=0 ; cipher[i].cnt!=Max ; i++){
			// 建立對照表
			tbl[cipher[i].alpha] = text[i].alpha;
		}
		
		for(int i=0 ; i<s.size() ; i++){
			cout<<tbl[s[i]];
		}
		cout<<"\n";
	}
	return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(len(P) + len(C))$

每筆測資統計時間複雜度為 $O(len(P) + len(C))$

每筆測資排序時間複雜度為 $O(2mlogm)$ ，其中 $m = 128$

每筆測資輸出時間複雜度為 $O(len(C))$

總時間複雜度約為 $n(2(len(P) + len(C)) + 2mlogm + len(C))$