ZOJ 1020 Puzzle Out
共 1473字，需浏览 3分钟
·
2021-11-09 02:23
Puzzle Out
Time Limit: 10000 msMemory Limit: 32768 KB
The scientific committee members of the 26th ACM/ICPC, who design the contest problems, use the following encryption algorithm to communicate the problem drafts securely through the Internet. To encrypt a text, all occurrences of each letter is replaced with another letter (possibly itself), such that no two letters are encrypted to the same letter. Both original and encrypted texts consist of only upper-case letters and blanks. Blanks are not encrypted and are repeated exactly in the encrypted text. As an example, the string GSRH RH GSV URIHG HZNKOV is the encrypted form of THIS IS THE FIRST SAMPLE according to the encryption table (A → Z, B → Y, C → X, …, Z → A).
A recipient of a problem draft has lost the encryption table, but he has a dictionary which includes all the possible words appearing in the problems. You are to help him set up a decryption table to enable him restore the original problem draft from the encrypted one. Given a dictionary of the original words used in the text, and the encrypted text, we want to find the right encryption table such that after decrypting the given encrypted text back to the original one, all words can be found in the dictionary.
Input
The first part of the input is a dictionary of English words common to all test cases. The first line of the file is d (1 <= d <= 50000); the number of words in the dictionary, followed by d lines each containing a word in the dictionary. The words in the dictionary are sorted in alphabetical order and all are in uppercase. Each word has at most 20 characters, but you can assume that sum of the length of all words in the dictionary is no more than 350,000. The next line contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. Each test case, which is preceded by a single blank line, consists of multiple lines in the input file forming the encrypted text. Each line has a string containing only uppercase letters and blank. You may assume that no line break is occurred in the middle of a word and there may be arbitrary number of blank characters at the end of each line. Maximum length of input lines is 80.
Output
The output contains exactly t lines, each corresponding to a test case. Each line should contain a single string of 26 characters which is the encryption of the string ABCDEFGHIJKLMNOPQRSTUVWXYZ according to the encryption table used in the test case. Letters in the output string should be in uppercase. It is possible that some letters do not appear in the encrypted text at all. In this case, put a * mark in place of those letters not appearing in the decrypted version of the input text. If the test case has no solution, the output line should contain #No solution#. If there is more than one possible encryption table for a test case, the output line should contain #More than one solution#.
Sample Input
14
BE
CHANGE
FIRST
IN
IS
MUST
SAMPLE
SEE
THE
THIS
TO
WISH
WORLD
YOU
4
GSRH RH GSV URIHG HZNKOV
IZM BMVU SP UGP
RGTANP IZM KFVG UZ VPP
FA UGP KZWCQ
XYZ ABCDEFG
XZY ABD
Sample Output
Z***VU*SR**ON**K*IHG******
TSRQP*NGF**CBAZ**WVUM*K*I*
#No solution#
#More than one solution#
谜题了
第26届ACM/ICPC的科学委员会成员设计了竞赛问题，他们使用以下加密算法通过互联网安全地传达问题草案。要加密文本，每个字母的所有出现都将被替换为另一个字母(可能是它本身)，这样就不会有两个字母被加密为同一个字母。原始的和加密的文本都只包含大写字母和空格。空格不会被加密，并且会在加密的文本中完全重复。例如，字符串GSRH RH GSV URIHG HZNKOV是加密的形式，这是根据加密表(A→Z, B→Y, C→X，…，Z→A)加密的第一个样本。
问题草案的接收者丢失了加密表，但他有一个字典，其中包含了所有可能出现在问题中的单词。您要帮助他设置解密表，使他能够从加密的问题草案恢复原始问题草案。给定一个包含文本中使用的原始单词和加密文本的字典，我们希望找到正确的加密表，这样在解密给定的加密文本后返回到原始的文本，所有单词都可以在字典中找到。
输入
输入的第一部分是所有测试用例常见的英语单词字典。文件的第一行是d (1 <= d <= 50000);字典中的单词数，后跟d行，每个行包含字典中的一个单词。字典中的单词是按字母顺序排序的，并且都是大写的。每个单词最多有20个字符，但是可以假设字典中所有单词的长度之和不超过350,000。下一行包含一个单一的整数t (1 <= t <= 10)，测试用例的数量，后面是每个测试用例的输入数据。每个测试用例前面都有一个空行，它由输入文件中的多行组成，形成加密的文本。每行有一个只包含大写字母和空白的字符串。您可以假设在单词中间不出现换行，并且在每行的末尾可能有任意数量的空白字符。输入行最大长度为80行。
输出
输出包含了t行，每一行都对应于一个测试用例。每一行应该包含一个26个字符的字符串，根据测试用例中使用的加密表，它是字符串ABCDEFGHIJKLMNOPQRSTUVWXYZ的加密。输出字符串中的字母应该是大写的。有可能一些字母根本没有出现在加密的文本中。在这种情况下，在未出现在解密版本的输入文本中的字母处使用*标记。如果测试用例没有解决方案，那么输出行应该包含# no solution#。如果一个测试用例有多个可能的加密表，那么输出行应该包含#多个解决方案#。
Sample Input
14
BE
CHANGE
FIRST
IN
IS
MUST
SAMPLE
SEE
THE
THIS
TO
WISH
WORLD
YOU
4
GSRH RH GSV URIHG HZNKOV
IZM BMVU SP UGP
RGTANP IZM KFVG UZ VPP
FA UGP KZWCQ
XYZ ABCDEFG
XZY ABD
Sample Output
Z***VU*SR**ON**K*IHG******
TSRQP*NGF**CBAZ**WVUM*K*I*
#No solution#
#More than one solution#
代码：
#include
#include
#include
#include
using namespace std;
struct node{
int right,child;
char ch;
bool end;
}tree[350010];
int index = 1,cnt = 0,mat[100],tl[100];
char answer[128],key[125],list[100][30];
bool used[128],findans,matched[100];
void insert(int p,char *word){
if (tree[p].ch){
if (tree[p].ch == *word){
if (!*(word + 1)) tree[p].end = 1;
else{
if(!tree[p].child) tree[p].child = ++index;
insert(tree[p].child,word + 1);
}
}
else{
if (tree[p].right) insert(tree[p].right,word);
else {
tree[p].right = ++ index;
insert(tree[p].right,word);
}
}
}
else{
tree[p].ch = *word;
if (!*(word + 1)) tree[p].end = 1;
else{
tree[p].child = ++ index;
insert(tree[p].child,word + 1);
}
}
}
int findwordmat(){
for (int i = 0;i < cnt;i ++){
mat[i] = 0;
for (int j = 0;j < tl[i];j ++)
if (key[list[i][j]])
++ mat[i];
}
}
int subsearch(int cur,int wi,int num,int tnum);
int search(int cur){
if (cur == cnt){
if (findans) return 2;
findans = 1;
for (int i = 'A';i <= 'Z';i ++) answer[key[i]] = i;
return 1;
}
findwordmat();
int m = -1,wi;
for (int i = 0;i < cnt;i ++)
if (!matched[i] && mat[i] > m){
m = mat[i];
wi = i;
}
return subsearch(cur,wi,0,1);
}
int subsearch(int cur,int wi,int num,int tnum){
if (num == tl[wi]){
matched[wi] = true;
int tmp = search(cur + 1);
matched[wi] = false;
return tmp;
}
if (!tnum) return 0;
char cc = list[wi][num];
if (key[cc]){
for (;tnum;tnum = tree[tnum].right)
if (tree[tnum].ch == key[cc]){
if (num + 1 == tl[wi] && !tree[tnum].end) return 0;
return subsearch(cur,wi,num + 1,tree[tnum].child);
}
return 0;
}else{
int find = 0;
for (;tnum;tnum = tree[tnum].right)
if (!used[tree[tnum].ch]){
if (num + 1 == tl[wi] && !tree[tnum].end) continue;
used[tree[tnum].ch] = true;
key[cc] = tree[tnum].ch;
int tmp = subsearch(cur,wi,num + 1,tree[tnum].child);
key[cc] = 0;
used[tree[tnum].ch] = false;
if (tmp == 2) return tmp;
if (tmp == 1) find = tmp;
}
return find;
}
}
int main(){
char word[130];
int w,t,tmp,pd,T;
scanf("%d",&w);
for (int i = 1;i <= w;i ++){
scanf("%s",word);
insert(1,word);
}
scanf("%d",&T);
while (T --){
memset(list,0,sizeof list);
cnt = 0,tmp = 0,pd = 0;
findans = 0;
memset(key,0,sizeof key);
memset(answer,0,sizeof answer);
char c;
while (c = getchar(),c < 'A' || c > 'z');
for (;;){
if (c >= 'A' && c <= 'Z'){
pd = false; list[cnt][tmp ++] = c;
}
else if (c == ' '){
pd = false;
if (tmp){
tl[cnt] = tmp;list[cnt ++][tmp] = 0;
tmp = 0;
}
}
else if (c == '\n'){
if (tmp){
tl[cnt] = tmp;list[cnt ++][tmp] = 0;
tmp = 0;
}
if (pd) break;
pd = 1;
}
if (scanf("%c",&c) == EOF){
if (tmp){
tl[cnt] = tmp;list[cnt ++][tmp] = 0;
tmp = 0;break;
}
}
}
int tmp = search(0);
if (tmp == 0) puts("#No solution#");
else if (tmp == 1){
for (int i = 'A';i <= 'Z';i ++){
if (answer[i]) printf("%c",answer[i]);
else printf("*");
}
printf("\n");
}else{
puts("#More than one solution#");
}
}
return 0;
}