d777 - NOIP2009 1.潜伏者

🔗 前往 ZeroJudge 原題

題目描述

題目描述了R國和S國之間的間諜戰，S國使用一種簡單的字母替換加密方式。給定一組加密信息和其對應的原文，要求解密S國的密碼，並使用解密的密碼來解密另一段加密信息。如果無法成功解密，則輸出 "Failed"。

解題思路

本題的核心是建立原文和密文之間的映射關係。程式使用兩個陣列 ax 和 bx 來儲存這個映射。ax 儲存原文字母對應的密文，bx 儲存密文字母是否已被使用。

程式首先遍歷原文和密文，建立映射關係。如果原文字母尚未映射，則檢查對應的密文字母是否已被使用。如果密文字母未被使用，則建立映射；否則，判斷為矛盾，輸出 "Failed"。如果原文字母已經映射，則檢查映射是否一致，如果不一致，則判斷為矛盾，輸出 "Failed"。

建立映射後，程式檢查是否所有26個字母都已映射。如果沒有，則輸出 "Failed"。

最後，程式使用建立的映射來解密第三段加密信息，並輸出解密後的結果。

複雜度分析

• 時間複雜度: O(n + m)，其中 n 是原文和密文的長度，m 是第三段加密信息的長度。
• 空間複雜度: O(1)，因為 ax 和 bx 陣列的大小是固定的 (300)，不依賴於輸入大小。

程式碼

#include <iostream>
using namespace std;
int ax[300],bx[300],ac=1,ct;
string a,b,c;
int main(){
	cin >> a >> b >> c;
	for(int i=0;i<a.length();++i){
		if(ax[a[i]]==0){
			if(bx[b[i]]){
				ac=0;
			}
			bx[b[i]]=1;
			ax[a[i]]=b[i];
		}
		else{
			if(ax[a[i]]!=b[i])ac=0;
		}
	}
	for(int i=0;i<300;++i){
		if(ax[i]){
			++ct;
		}
	}
	if(ct<26)ac=0;
	if(ac==0){
		cout << "Failed";
	}
	else{
		for(int i=0;i<c.length();++i){
			cout << (char)ax[c[i]];
		}
	}
}