首页 > ACM题库 > HDU-杭电 > HDU 3147-Playfair Cipher[解题报告]HOJ
2014
03-06

HDU 3147-Playfair Cipher[解题报告]HOJ

Playfair Cipher

问题描述 :

The Playfair cipher is a manual symmetric encryption technique and was the first digraph substitution cipher. The scheme was invented in 1854 by Charles Wheatstone, but bears the name of Lord Playfair who promoted the use of the cipher.

The Playfair cipher uses a 5 by 5 table containing each letter in the English alphabet exactly once (except ‘Q’ which is missing). The table constitutes the encryption key. To more easily remember the table, it is typically generated from a key phrase. First fill in the spaces in an empty table with the letters of the key phrase (dropping spaces and duplicate letters), then fill the remaining spaces with the rest of the letters of the alphabet in order. The key phrase is written in the top rows of the table, from left to right. For instance, if the key phrase is "playfair example", the encryption key becomes

Beacons

To encrypt a message, one would remove all spaces and then break the message into digraphs (groups of 2 letters) such that, for example, "Hello World" becomes "HE LL OW OR LD". Then map them out on the key table, and apply the rule below that matches the letter combination:
  • If both letters are the same (or only one letter is left), add an ‘X’ after the first letter. Encrypt the new pair and continue (note that this changes all the remaining digraphs).
  • If the letters appear on the same row of your table, replace them with the letters to their immediate right respectively (wrapping around to the left side of the row if a letter in the original pair was on the right side of the row). With the table above, the digraph ‘CH’ would be encrypted ‘DB’.
  • If the letters appear on the same column of your table, replace them with the letters immediately below respectively (wrapping around to the top side of the column if a letter in the original pair was on the bottom side of the column). With the table above, the digraph ‘VA’ would be encrypted ‘AE’.
  • If the letters are not on the same row or column, replace them with the letters on the same row respectively but at the other pair of corners of the rectangle defined by the original pair. The order is important { the first letter of the encrypted pair is the one that lies on the same row as the first letter of the plaintext pair. With the table above, the digraph ‘KM’ would be encrypted ‘SR’.

Write a program that reads a key phrase and a plaintext to encrypt, and outputs the encrypted text.

The text to encrypt will not contain two ‘x’s following each other, or an ‘x’ as the last character, as this might cause the first rule above to repeat itself indefinitely.

输入:

The input contains two lines. The first line contains the key phrase. The second line contains the text to encrypt. Each line will contain between 1 and 1000 characters, inclusive. Each character will be a lower case English letter, ‘a’ – ‘z’ (except ‘q’), or a space character. Neither line will start or end with a space.

输出:

The input contains two lines. The first line contains the key phrase. The second line contains the text to encrypt. Each line will contain between 1 and 1000 characters, inclusive. Each character will be a lower case English letter, ‘a’ – ‘z’ (except ‘q’), or a space character. Neither line will start or end with a space.

样例输入:

playfair example
hide the gold in the tree stump
the magic key
i love programming competition

样例输出:

BMNDZBXDKYBEJVDMUIXMMNUVIF
YDVHCWSPKNTAHKUBIPERMHGHDVRU

#include<iostream>
#include<vector>
#include<fstream>
#include<queue>
#include<algorithm>
#include<list>
#include<cstdio>
#include<stack>
#include<cstring>
#include<cmath>
#include<string>
#include<sstream>
#include<map>
#include <bitset>
#include <set> 

using namespace std ;

#define			pii			pair < int , int >
#define			MP			make_pair

map < char , pii > table ;
map < pii , char > table2 ;
bool visit[100] ;

int main()
{
	//freopen("a.in","r",stdin);
	int t , R , C ;
	string key , text ;
	cin >> t ;
	getline ( cin , text ) ;
	while ( t-- ){
		table.clear() , table2.clear() ;
		memset ( visit , 0 , sizeof visit ) ;
		visit['q'-'a'] = 1 ;
		getline ( cin , key ) ;
		getline ( cin , text ) ;
		R = C = 0 ;
		for ( int i = 0 ; i < key.size() ; i++ ){
			if ( key[i] >= 'a' && key[i] <= 'z' && !visit[key[i]-'a'] ){
				visit[key[i]-'a'] = 1 ;
				table[key[i]] = MP ( R , C ) ; 
				table2[MP(R,C)] = key[i] ;
				C++ ;
				if ( C == 5 ){
					R++ ;
					C = 0 ;
				}
			}
		}
		for ( int i = 'a' ; i <= 'z' ; i++ ){
			if ( !visit[i-'a'] ){
				table[(char)(i)] = MP ( R , C ) ; 
				table2[MP(R,C)] = (char)(i) ;
				C++ ;
				if ( C == 5 ){
					R++ ;
					C = 0 ;
				}
			}
		}
		for ( int i = 0 ; i < text.size() ; i++ ){
			if ( text[i] == ' ' ){
				text.erase ( text.begin() + i ) ;
				i-- ;
			}
		}
		for ( int i = 0 ; i < text.size()-1 ; i+=2 ){
			if ( text[i] == text[i+1] )
				text.insert ( text.begin() + i + 1 , 'x' ) ;
		}
		if ( (int)(text.size())%2 )
			text.push_back ( 'x' ) ;
		char ch1 , ch2 ;
		int x_ch1 , y_ch1 , x_ch2 , y_ch2 , new_x , new_y ;
		for ( int i = 0 ; i < (int)(text.size())-1 ; i+=2 ){
			ch1 = text[i] , ch2 = text[i+1] ;
			if ( ch1 == ch2 ) ch2 = 'x' ;
			x_ch1 = table[ch1].first ;
			y_ch1 = table[ch1].second ;
			x_ch2 = table[ch2].first ;
			y_ch2 = table[ch2].second ;
			if ( x_ch1 == x_ch2 ){
				new_y = (y_ch1+1)%5 ;
				cout << (char)(table2[MP(x_ch1,new_y)]-32);
				new_y = (y_ch2+1)%5 ;
				cout << (char)(table2[MP(x_ch2,new_y)]-32) ;
			}
			else if ( y_ch1 == y_ch2 ){
				new_x = (x_ch1+1)%5 ;
				cout << (char)(table2[MP(new_x,y_ch1)]-32) ;
				new_x = (x_ch2+1)%5 ;
				cout << (char)(table2[MP(new_x,y_ch2)]-32) ;
			}
			else{
				new_y = abs ( y_ch1 - y_ch2 ) ;
				if ( y_ch1 < y_ch2 ){
					y_ch1 += new_y ;
					y_ch2 -= new_y ;
				}
				else if ( y_ch1 > y_ch2 ){
					y_ch1 -= new_y ;
					y_ch2 += new_y ;
				}
				cout << (char)(table2[MP(x_ch1,y_ch1)]-32) ;
				cout << (char)(table2[MP(x_ch2,y_ch2)]-32) ;
			}
		}
		cout << endl ;
	}
	return 0;
}

  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环

  3. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧