思路&题解

PC/UVA 110204/843
本题。DFS。但是由于过多的使用set。导致TLE。。话说。我第一次在挑战编程的那个网站上看到有这个状态。。

//author: CHC
//First Edit Time:	2014-01-22 11:17
//Last Edit Time:	2014-01-22 12:14
//Filename:3.cpp
#include <iostream>
#include <cstdio>
#include <string.h>
#include <queue>
#include <set>
#include <sstream>
#include <algorithm>
using namespace std;
int n,ok;
int s_len[20];
char s_word[20][1010][20];
char m_word[1010][20];
int  m_len[1010];
char ha[20][1010],v[256];
char vis[256];
char t[1010];
int dfs(int cur,int end)
{
    if(ok)return 1;
    if(cur==end)  return ok=1;
    int len=m_len[cur];
    for(int i=0;i<s_len[len];i++){
        if(!ha[len][i]){
            int ok=1,ha2[256]={ 0 },ha3[256]={ 0 };
            int lnum=0;
            for(int j=0;j<len&&ok;j++){
                int c=s_word[len][i][j],d=m_word[cur][j];
                if(!vis[d]&&!v[c]){
                    vis[d]=c;
                    v[c]=1;
                    ha2[lnum]=c;
                    ha3[lnum]=d;
                    lnum++;
                }
                else if(vis[d]!=c)ok=0;
            }
            if(ok){
                ha[i][len]=1;
                if(dfs(cur+1,end))return 1;
                ha[i][len]=0;
            }
            for(int j=0;j<lnum;j++)
                vis[ha3[j]]=v[ha2[j]]=0;
        }
    }
    return 0;
}
int main()
{
    //while(~scanf("%d",&n)){
    scanf("%d",&n);
        memset(s_len,0,sizeof(s_len));
        memset(s_word,0,sizeof(s_word));
        for(int i=0;i<n;i++){
            scanf(" %s",t);
            int len=strlen(t);
            strcpy(s_word[len][s_len[len]++],t);
        }
        getchar();
        while(gets(t)!=NULL)//&&strcmp(t,"")!=0)
        {
            istringstream cci(t);
            int m_num=0;
            ok=1;
            memset(ha,0,sizeof(ha));
            memset(vis,0,sizeof(vis));
            memset(v,0,sizeof(v));
            memset(m_len,0,sizeof(m_len));
            set <string> s;
            while(cci>>m_word[m_num])
            {
                if(s.find(m_word[m_num])!=s.end()){ continue; }
                int len=strlen(m_word[m_num]);
                if(!s_len[len]){
                    ok=0;
                    break;
                }
                s.insert(m_word[m_num]);
                m_len[m_num]=len;
                m_num++;
            }
            if(ok){
               ok=0;
               dfs(0,m_num);
            }
            //printf("ok:%d  %s\n",ok,t);
            for(int i=0;t[i];i++){
                if(t[i]==' ')putchar(' ');
                else putchar(ok?vis[t[i]]:'*');
            }
            puts("");
        }
    //}
    return 0;
}

Crypt Kicker

A common but insecure method of encrypting text is to permute the letters of the alphabet. In other words, each letter of the alphabet is consistently replaced in the text by some other letter. To ensure that the encryption is reversible, no two letters are replaced by the same letter.
Your task is to decrypt several encoded lines of text, assuming that each line uses a different set of replacements, and that all words in the decrypted text are from a dictionary of known words.

Input

The input consists of a line containing an integer n, followed by n lowercase words, one perline, in alphabetical order. These n words compose the dictionary of words which may appear in the decrypted text. Following the dictionary are several lines of input. Each line is encrypted as described above.
There are no more than 1,000 words in the dictionary. No word exceeds 16 letters. The encrypted lines contain only lower case letters and spaces and do not exceed 80 characters in length.

Output

Decrypt each line and print it to standard output. If there are multiple solutions, any one will do. If there is no solution, replace every letter of the alphabet by an asterisk.

Sample Input

6  
and  
dick  
jane  
puff  
spot  
yertle  
bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn  
xxxx yyy zzzz www yyyy aaa bbbb ccc dddddd

Sample Output

dick and jane and puff and spot and yertle  
**** *** **** *** **** *** **** *** ******