首页 > ACM题库 > HDU-杭电 > hdu 2694 Cipher -拓扑排序-[解题报告]C++
2014
02-13

hdu 2694 Cipher -拓扑排序-[解题报告]C++

Cipher

问题描述 :

The Playfair cipher or Playfair square is a manual symmetric encryption technique and was the first literal digraph
substitution cipher. The technique encrypts pairs of letters (digraphs), instead of single letters as in the simple
substitution cipher and rather more complex Vigenère cipher systems then in use. The Playfair is thus significantly harder
to break since the frequency analysis used for simple substitution ciphers does not work with it. Frequency analysis can still
be undertaken, but on the 600 possible digraphs rather than the 26 possible monographs. The frequency analysis of digraphs
is possible, but considerably more difficult and it generally requires a much larger ciphertext in order to be useful.

Despite its invention by Wheatstone, it became known as the Playfair cipher after Lord Playfair, who heavily promoted its
use. The first recorded description of the Playfair cipher was in a document signed by Wheatstone on 26 March 1854.It was
used for tactical purposes by British forces in the Second Boer War and in World War I and for the same purpose by the
Australians and Germans during World War II. This was because Playfair is reasonably fast to use and requires no special
equipment. A typical scenario for Playfair use would be to protect important but non-critical secrets during actual combat.
By the time the enemy cryptanalysts could break the message, the information was useless to them.

However Playfair is no longer used by military forces because of the advent of digital encryption devices. Playfair is now
regarded as insecure for any purpose because modern hand-held computers could easily break the cipher within seconds.

The Playfair cipher uses a 5 by 5 table containing a keyword or phrase. Memorization of the keyword and some simple
rules was all that was required to create the 5 by 5 table and use the cipher.
To generate the key table, one would first
fill in the spaces in the table with the letters of the keyword (dropping any duplicate letters), then fill the remaining
spaces with the rest of the letters of the alphabet in order (combine ‘I’ and ‘J’ to reduce the alphabet to fit).

To encrypt a message, one would change the lowercase to uppercase, break the message into digraphs (groups of 2 letters
and throw away spaces) such that, for example, "Hello World" becomes "HE LL OW OR LD", and map them out on the key table.
The two letters of the digraph look like the corners of a rectangle in the key
table. Note the relative position of the corners of this rectangle. Then apply the following rules, in order, to each pair
of letters in the plaintext:
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.

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).

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).

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 encrypted letter of the pair is the one that lies on the same row as the first plaintext letter.

输入:

The input consists of multiple test cases. The first line of input contains an integer T, which is the number of test cases.
Each test case containing two lines: the key and the message.
The length of the key and the message will
not exceed 500.
You may assume that the message does not contain substring such as "XX", "IJ" , "JI", and does not end with "X".

输出:

The input consists of multiple test cases. The first line of input contains an integer T, which is the number of test cases.
Each test case containing two lines: the key and the message.
The length of the key and the message will
not exceed 500.
You may assume that the message does not contain substring such as "XX", "IJ" , "JI", and does not end with "X".

样例输入:

3
Charles 
Meet me at the Hammersmith Bridge tonight 
Death 
Laboulaye Lady 
to go to jail together 
to stand up for freedom together 

样例输出:

GDVBYTBCQYPRSCRKYKDCDIMPASHMEMDOUGKIRP 
MEIKQOTXCQTEZY 
OGNITUMPQDIEKHHWDPADOGOHGLHB 

Hint
Hint1. Using "Death" as the key, the table becomes: D E A T H B C F G I / J K L M N O P Q R S U V W X Y Z NOTE that 'J' is in same place with 'I'! Encrypting the message "Laboulaye Lady": LA BO UL AY EL AD YX The pair LA forms a rectangle, replace it with ME. The pair BO forms a rectangle, replace it with IK. The pair UL forms a rectangle, replace it with QO. The pair AY forms a rectangle, replace it with TX. The pair EL in a column, replace it with CQ. The pair AD in a row, replace it with TE. The pair YX in a row, replace it with ZY. ME IK QO TX CQ TE ZY Thus the message becomes "MEIKQOTXCQTEZY". 2. Assume one wants to encrypt the digraph OR. There are three general cases: 1) 2) 3) * * * * * * * O * * Z * * O * * O Y R Z * * B * * * * * * * * * * * * * * * * * * * * * * * * * * * * * R * * R * * X * * * * * * * * Y * * * * * * * Hence, OR -> YZ Hence, OR -> BY Hence, OR -> ZX

http://acm.hdu.edu.cn/showproblem.php?pid=2647

原以为存在1-》2-》3-》4且6-》3的时候要算出money3=money1+2;且money6=money3-1.后来发现要使钱最少,其实moeny
6应该为888(最先度数为0的点),这样的只要一遍拓扑排序即可。其中vector G[n]存储邻接表。

#include
#include
#include
#include
#include
using namespace
std;
vector<</FONT>int>
G[10005];
int
deg[10005];
int
Min[10005];
int
vis[10005];

int topo(int
deg[], int n)
{

   
int
flag =
0;
   
int
k = 0;  //
标记名次
   
stack<</FONT>int>
s;
   
memset(vis, 0,
sizeof(vis));
   
for
(int i =
1;
i <= n; i ++){
        
if
(deg[i]
==
0){
           
vis[i]
=
1;
           
s.push(i);
           
Min[i]
=
k;
           
flag = 1;
        
}
   
}

    k
++;
   
if
(flag
== 0)
return -1;
   
while
(!s.empty()){
    
//   cout << s.top()
<< endl;
       
for
(int i =
0;
i <</FONT>
G
[s.top()].size(); i ++){
           
deg[G[s.top()][i]] –;
       
}

       
s.pop();
       
flag = 0;
       
for
(int i =
1;
i <= n; i ++){
           
if
(vis[i]
==
0 && deg[i] ==
0){
               
vis[i]
=
1;
               
s.push(i);
               
Min[i]
=
k;
               
flag = 1;
           
}
       
}

   
//    if(flag ==
0) return
-1;
       
k ++;
   
}

   
if
(!s.empty())
return -1;
    else
return
0;
}

int main()
{

   
int
n,
m;
   
int
x,
y;
   
while
(scanf(“%d%d”,
&
n,
&
m) !=
EOF){
       
for
(int i =
0;
i <</FONT> 10005; i
++)
           
G[i].clear();          
// 注意要清零
       
for
(int i =
0;
i <</FONT>
m
; i ++){
           
scanf(“%d%d”,
&
x,
&
y);
           
G[y].push_back(x);
       
}

       
memset(deg, 0,
sizeof(deg));
       
for
(int i =
1;
i <= n; i ++){
           
for
(int j =
0;
j <</FONT>
G
[i].size();
j ++){
       
//            
printf(“~%d\n”,
G[i][j]);
                   
deg[G[i][j]] ++;
           
}
       
}

     
//  for(int i = 1; i <= n; i ++)
     
//     
printf(“~%d\n”, deg[i]);
       
int
ans =
topo(deg, n);
       
if
(ans
== -1)
printf(“-1\n”);
       
else
{
           
int
res =
0;
           
for
(int i =
1;
i <= n; i ++)
               
res += Min[i];
           
printf(“%d\n”,res
+ n*888);
       
}
   
}

   
return
0;
}

刚开始是自己以前YY的题目,交这题时竟然超时,无奈再写一遍,参看网上的代码,有的写的真的很简洁啊。

// 为什么改用stack不行
#include
#include
#include
#include
#include
using namespace std;

vector G[10005];
int deg[10005];
int Min[10005];

void topo(int n)
{
    queue
s;
    int num =
0;
    memset(Min,
0, sizeof(Min));
    for(int i =
1; i <= n; i ++){
        
if(deg[i] == 0){
           
s.push(i);
        
}
    }
   
while(!s.empty()){
       
cout << s.front() << endl;
       
int x = s.front();
       
s.pop();
       
num ++;
       
for(int i = 0; i < G[x].size(); i ++){
           
int u = G[x][i];
           
if(–deg[u] == 0){
               
s.push(u);
               
Min[u] = Min[x] + 1;
           
}
       
}
    }
   
//printf(“ans=%d\n”, ans);
    if(num
==  n) printf(“-1\n”);
    else {
       
int res = 0;
       
for(int i = 1; i <= n; i ++)
           
res += Min[i];
       
printf(“%d\n”,res + n*888);
    }
}

int main()
{
    int n,
m;
    int x,
y;
   
while(scanf(“%d%d”, &n, &m) != EOF){
       
for(int i = 0; i <= n; i ++){
           
G[i].clear();          
// 清零
           
deg[i] = 0;
       
}
       
for(int i = 0; i < m; i ++){
           
scanf(“%d%d”, &x, &y);
           
G[y].push_back(x);
           
deg[x]
++;         
// 输入即可记录度数
       
}
       
topo(n);
    }
    return
0;
}
这里是ac的代码,其中有些可以合并,并且不需要开这么大的数组


解题转自:http://blog.sina.com.cn/s/blog_b60f0e070101gxr6.html