420      阿裏雲  技術社區[雲棲]

poj 2159 Ancient Cipher

這題主要應該就是理解題意的問題，我的確是把題目理解錯了，WA了三次，每次都以為一定是正確的，後來看了別人的解釋才知道是題目理解錯了（竟然還看到了別人的結題報告也有錯的。。。），另外就是學會了用STL的sort快排，很方便，在<algorithm>頭文件裏麵，這說明了一定要自己會寫排序，但是不一定每次都是自己寫函數，有N多好的函數別人已經寫好了，你隻用知道什麼時候該用就可以了。。。但是自己也要會寫（萬一比賽不允許用庫函數）

開始錯誤的想法：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

int main()
{
	char input[102],source[102];

	scanf("%s%s",input,source);
	//printf("\n%s\n%s\n",input,source);

	int i;
	for(i=0;i<strlen(input);i++)
	{
		if(input[i]=='A')
			input[i]='Z';

		else
			input[i]=input[i]-1;
	}

	// 標準庫自帶排序函數sort(ip_start,ip_end) 對某連續的地址段的對象內容進行升序快排（從小到大），<algorithm>
	sort(input,input+strlen(input));
	sort(source,source+strlen(source));

	//printf("\n%s\n%s\n",input,source);	//ok

	if(strcmp(input,source)==0)
		printf("YES\n");

	else
		printf("NO\n");

	return 0;
}

看了別人的解釋：（注意下麵的 For example, applying substitution 。。。，代表不是普適的，隻是舉的一個特例）

“substitution cipher （置換密碼）：

Substitution cipher changes all occurrences of each letter to some other letter. Substitutes for all letters must be different.For some letters substitute letter may coincide with the original letter. For example, applying substitution cipher that changes all letters from 'A' to 'Y' to the next ones in the alphabet, and changes 'Z' to 'A', to the message "VICTORIOUS" one gets the message "WJDUPSJPVT".

“移位”隻是置換密碼的一種，隻要滿足“Substitutes for all letters must be different.”就是置換了，比如

A->B

C->H

Z->D

對於這道題,input:

AAABB
CCCEE

應輸出

YES

所以明文與密文的“字母頻率的數組”應該是一樣的，即明文中某字母出現8次，密文中也必須有某個字母出現8次。

所以字母種類，字母頻率同時相等時，即被破解。

permutation cipher（排列密碼）：

Permutation cipher applies some permutation to the letters of the message. For example, applying the permutation <2, 1, 5, 4, 3, 7, 6, 10, 9, 8> to the message "VICTORIOUS" one gets the message "IVOTCIRSUO".

明文隨機排列，所以字母種類和頻率都不變。

對於這道題，排列密碼考慮和不考慮對解題無影響！”

正確的代碼

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

int input[26],source[26];

int main()
{
	char temp[102];

	scanf("%s",temp);
	int i;
	for(i=0;i<strlen(temp);i++)
	{
		input[temp[i]-'A']++;
	}



	scanf("%s",temp);
	for(i=0;i<strlen(temp);i++)
	{
		source[temp[i]-'A']++;
	}

	// 標準庫自帶排序函數sort(ip_start,ip_end) 對某連續的地址段的對象內容進行升序快排（從小到大），<algorithm>
	sort(input,input+26);
	sort(source,source+26);


	for(i=0;i<26;i++)
		if(input[i]!=source[i])
		{
			printf("NO\n");
			return 0;
		}

	printf("YES\n"); 

	return 0;
}

最後更新：2017-04-03 14:54:38

  上一篇： RGMII,MII,GMI接口

  下一篇： NOR型flash與NAND型flash的區別