本文純屬原創，轉載請注明出處。謝謝。

題目傳送門：http://poj.org/problem?id=1449

Time Limit:?1000MS	?	Memory Limit:?10000K
?	?	?

Description

During the Second World War, the German military forces mainly used one special machine to secure their communication: the Enigma (see Figure 4). Breaking the Enigma cipher is one of the main success stories of Allied cryptanalysis and the triumph was mainly attributed to the emergence of digital computation and the genius of the people working at Bletchley Park, the secret cryptanalysis headquarters in England. The reason for this is that, while Enigma is certainly secure against pen and paper attacks, it is quite easily breakable using digital computers.?

?
Figure 4: An Enigma machine (picture source: http://www.nsa.gov/museum/enigma.html).
The Enigma was a rotor machine, a cipher method which was popular at that time. A rotor is an insulated disk on which electrical contacts, one for each letter of the alphabet, are placed uniformly around the periphery and on each side. An internal conduction path through the insulating material connects contacts in pairs, one on each side of the disk. An electric current entering on one side travels on an internal path through the rotor cross-section, emerging at one of the contacts on the other side (see Figure 5 for a 3D visualisation of two rotors). Figure 6 shows a schematic side view of the complete rotor system. It shows that the Enigma has three rotors π0, π2 plus an additional reflecting rotor πR.?

The input to Enigma is a stream of alphabetic characters without blanks. Every character is subject to the following steps:?

1. The plaintext is subject to an initial permutation IP which is implemented by a plugboard.?

2. The character resulting from step 1 is sent through the three rotors π0, π2.?

3. The resulting character is then sent through the reflecting rotor πR.?

4. The character from step 3 is passed back through the rotors π2, π0 (i.e., in the opposite direction).?

5. The character from step 4 is subject to the inverse IP^-1?of the initial permutation IP.?

The interesting point about the use of rotors is that after processing each character, every rotor might be rotated by a certain angle (i.e., a certain amount of letters) before processing the next character. With the Enigma, rotor π0 is rotated by one in anti-clockwise direction with every new character. When π0 has finished one round (i.e., after processing 26 characters), rotor π1 moves by one character. Similarly, rotor π2 is rotated by one character when π1 has finished one revolution, and the reflecting rotor πR moves when π2 has finished its rotation. Obviously, πR is the slowest of the four rotors.?

The process described above can be used both for encryption and decryption, provided that the permutation πR implemented by the reflecting rotor is an involution. That means πR = πR^-1, or, equivalently, ξ=πR(ζ) whenever ζ=πR(ξ). You may assume that this condition holds.?

The secret key of the Enigma consists of (1) the rotors π0, π2, and πR, (2) the plugboard permutation IP, and (3) the initial rotational displacements k0, k1, k2, kR of π0, π2, and πR (see below). The rotors were changed infrequently and were selected from a set of four possible rotors in the Wehrmacht model.?

Problem?

You are time-warped to Bletchley Park together with your laptop and should help to decipher some messages which have been intercepted over the day. You are given the entire ciphertext, parts of the plaintext, and parts of the Enigma key. Your task is to determine the correct key and finally complete the plaintext by decoding the ciphertext.?

Input

The first line contains the number of scenarios.?

Each scenario begins with the secret key of the Enigma. The secret key is specified by 6 lines. The first four lines contain a specification of the rotors π0, π2 and πR as a sequence of lowercase alphabetic characters. Character i (1<=i<=26) gives the mapping of the i-th character of the alphabet (e.g., "bha..." means that "a" is mapped to "b", "b" is mapped to "h", "c" is mapped to "a" etc.). Physically, the sequence of characters is given in clockwise direction looking from the front of the rotor stack π0, . . . , πR. After the rotors follows a similar line giving the plugboard permutation IP. Finally, the sixth line of the key gives the initial displacement k0, k1, k2, kR of the four rotors π0, π2, and πR as a string of four characters where "a" means that the rotor is in its original position (as defined by the rotor specification above), "b" means that it is rotated by one position in the usual way etc. For example, "dgaa" means that rotor π0 has initial displacement 3, π1 has 6, and π2, πR are both in their original position.?

After the key follow two lines, each containing at least 1 and at most 80 lowercase letters, and no other characters. The first line contains the plaintext while the second line contains the ciphertext. The plaintext and any part of the key may be incomplete, i.e., some positions in the strings may be question marks "?". The number of question marks in the input will be at most 3.

Output

The output for each scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. In the next line you are to output the completed, decrypted plaintext. You can assume that a solution exists and that it is unique. Terminate the output for each scenario with a blank line.

Sample Input

2 wfbtiznuvcqejpokshxgmadyrl hmrgnqpkjcaivwluebfzsyxtdo druahlbfzvgmwckxpiqysontje owtvskypjifmluahrqecndbzgx ?

bcdefghijklmnopqrstuvwxyz aaaa manyorganizationsrelyoncom??

ters grsuztldsznkwnerdpfbovvqnobkyiqn oqzunvhtxwryfebicmjpklsgda zupogrskynxtwdfqvbliejcmha kzvlyjuodmscewxtfbphriqgna gbcnylaztwkfmdspqvoiurjxeh rfyhkxbuvplgtqmdiewjosznca dmeo ???

ave

Sample Output

Scenario #1: manyorganizationsrelyoncomputersScenario #2: acm

這道題題目長的我這樣的英語不好的愣是看了半天。

這是2001年XX歐現場賽的題，題目又臭又長。關鍵事實上就是一個十足的水題。關鍵是網上臨時還找不到這個題的題解，僅僅有趙端陽寫的《acm國際大學生程序設計競賽題解1》里面有提到這道題，可是解說不夠具體，沒有解釋這個機器的工作原理，所以看了一天多才看懂。然后就毅然決定寫一篇來好好解釋一下。

大意是這種：（算了我還是先解釋一下這個機器）

首先Enigma作為德國二戰時期御用的加密解密器。這個題完全然全地還原了這臺天才之作的結構。

它由一個置換盤。3個置換轉子盤，和一個反射轉子盤組成。

首先是置換盤是一個簡單的替換加密器，正向通過時A替換成X。反向通過時X就替換成A，它是固定的，也是最基礎最簡單的加密方法。

《福爾摩斯探案集》里面《跳舞的小人》一節就是用的這種方法。簡單地來說就是用26個新的符號替換原來的26個字母。盡管這里替換的26個符號也是取自26個字母?？墒撬鼈兲鎿Q之后就不代表原來的意思了。而反過來就是將26個字符相應替換回原來的字母。

接著最難理解的是3個置換轉子，這也是這個機器的精髓。

昨天沒有看到電路圖的時候我一直在想怎么實現的，后來看了一眼電路圖瞬間明確了。

以下放圖。

這是一個置換轉子盤的工作原理圖。

我們能夠看到，不管是明文（左盤）還是密文（右盤），都是按順序排列并且不變的，變的是中間的轉子電路圈。而我們能夠看到。置換電路圈的電路是不變的，那么假設一開始A連到D，那么代表的是連在A點的這個電路是往下連3個的，那么一旦轉子往下轉動一個，不是B連接到了D點，而是B點得到了原來在A點的電路。那么B就會連到往下3個的那個地方，反之亦然。

那么每一個盤在初始狀態的連接情況。就代表著這個盤26個點的電路連接狀況，也就是密鑰。

假設理解了這個工作原理。那么最后一個反射轉子盤就很好理解了，無非就是去掉了這個轉子的右盤。而把左盤上的點兩兩連在一起，構成了13對，當然轉動也會帶來配對的改變。

而這四個能夠轉的盤什么時候轉動呢？規則是這種：每處理完一個字符，第1個轉子盤逆時針轉一個字符，假設第1個轉子盤轉了26下，也就是處理完26個字符，第二個轉子盤逆時針轉動一個字符，然后第二個轉26下第三個就轉一個字符，第四個亦然。當然我們最開始能夠把每一個盤都撥動若干個字符。這個撥動不算轉動次數。

以上就是對于這個機器的工作原理的解釋，也是這個題最核心的地方，僅僅要弄懂了這一點，這個題就是水題了。

題意：如今給你這么一個機器。首先告訴你四個盤的密鑰（它對于每條密鑰，是按每行26個字符給的，第x行第i個字符代表著字母‘a’+i-1在初始狀態下通過第x個盤應該變成什么）。接著第五行告訴你那個固定的簡單置換盤的相應關系（給的方式同上），接下來第六行給你一行四個字符，第i個字符表示初始狀態下。第i個盤被撥動了c[i]-‘a’個字符。接下來第七行給你了一段明文，第八行給你了這段明文在這個機器如上的狀態下被加密之后的密文。

然后如今告訴你，這上面八行字符串里面有至多3個字符被弄得看不清了，所以讀入的時候用‘？’取代了，那么請你找出這三個‘？’應該相應的正確字符后，輸出完整的明文（題目保證每組測試數據有且僅有一解）。

那么這個密文在題目中的執行順序是什么呢：

1、每一個字符首先正向通過簡單置換板

2、通過步驟1得到的字符再依次正向通過1、2、3這三個轉子置換板

3、通過步驟2得到的字符再通過反射轉子置換板

4、通過步驟3得到的字符再依次逆向通過3、2、1這三個轉子置換板

5、通過步驟4得到的字符再逆向通過簡單置換板得到明文

6、每一個字符完畢上述五步之后，各個轉子轉動，為下一個字符的處理做準備。

思路：拿到這個題首先分析，僅僅有3個字符不確定，并且每一個之后26種情況，所以總共僅僅有26*26*26=17526種可能性，全然能夠枚舉出來然后一一檢測能否滿足解密過程。

于是就愉快地用dfs枚舉然后檢測了。

以下貼代碼。

#include <cstdio> #include <cmath> #include <cstring> #include <string> #include <map> #include <vector> #include <iostream> #include <algorithm> #define moo 1000000007//10^9+7 #define PI acos(-1.0) using namespace std; char s[10][100];//存最原始的8行字符串 int a[10][100];//存處理后的8行字符串，處理方法是對每一個字符-'a' struct question {int x;int y; }que[5];//存問號在的位置，第X行第Y個字符 int cou;//存問號的數量 int cheek()//檢測函數，對于當前枚舉的情況，假設解密正確則返回1，否則返回0 {int b1[100];int b2[100];//將明文密文取出，由于要做改動。所以避免對原數據造成影響。

int len=strlen(s[7]); for(int i=0;i<len;i++) { b1[i]=a[4][a[7][i]];//將密文第一次通過簡單置換板的操作順手做了 b2[i]=a[6][i]; } int d[4][30];//存每一個轉子正向通過時的電路圖 int e[4][30];//存每一個轉子逆向通過時的電路圖 for(int i=0;i<4;i++) { for(int j=0;j<26;j++) { int t=a[i][j]; d[i][j]=t-j;//正向通過。從j變成t，電路是+（t-j） e[i][t]=j-t;//逆向通過，從t變成j，電路是+（j-t） } } int c[4];//存的是每一個轉子置換板當前的轉動情況。 for(int i=0;i<4;i++) c[i]=a[5][i]; for(int i=0;i<len;i++) { for(int j=0;j<=3;j++) { b1[i]+=d[j][(b1[i]+c[j]+26)%26]; b1[i]=(b1[i]+26)%26; }//當前字符依次正向通過1、2、3這三個板，由于反射板工作原理與普通的沒什么兩樣，所以也順手正向通過 for(int j=2;j>=0;j--) { b1[i]+=e[j][(b1[i]+c[j]+26)%26]; b1[i]=(b1[i]+26)%26; }//然后再逆向通過3、2、1這三個板。 for(int j=0;j<26;j++)//推斷這個字符逆向通過簡單置換板之后是不是得到明文。假設不是，則當前枚舉錯誤 if(b1[i]==a[4][j]&&b2[i]!=j) return 0; c[0]++;//對于每一個轉子做對應轉動。為處理下一個字符做準備 if(c[0]==a[5][0]+26) { c[0]=a[5][0]; c[1]++; if(c[1]==a[5][1]+26) { c[1]=a[5][1]; c[2]++; if(c[2]==a[5][2]+26) { c[2]=a[5][2]; c[3]++; if(c[3]==a[5][3]+26) c[3]=a[5][3]; } } } } return 1; } int dfs(int x) { if(x==cou) { if(cheek()==1) return 1; return 0; } for(int i=0;i<26;i++)//枚舉每一位填'a'+i的情況 { a[que[x+1].x][que[x+1].y]=i; if(dfs(x+1)==1) return 1; } return 0; } void init() {//預處理八行字符串，把全部點都處理成int型，方便操作，而且把'?'都提取出來 for(int i=0;i<8;i++) { int len=strlen(s[i]); for(int j=0;j<len;j++) { if(s[i][j]=='?

') { cou++; que[cou].x=i; que[cou].y=j; } else a[i][j]=s[i][j]-'a'; } } } int main() { int T; cin>>T; int dd=T; while(T--) { for(int i=0;i<8;i++) scanf("%s",s[i]); cou=0; init(); dfs(0); printf("Scenario #%d:\n",dd-T); int len=strlen(s[6]); for(int i=0;i<len;i++) printf("%c",a[6][i]+'a'); printf("\n\n"); } return 0; }

轉載于:https://www.cnblogs.com/jzdwajue/p/7293902.html

總結

以上是生活随笔為你收集整理的POJ 1449 amp; ZOJ 1036 Enigma（简单枚举）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。