788
[usaco] 4.1.4 PROB Cryptcowgraphy
Cryptcowgraphy
Brian Dean
The cows of Farmer Brown and Farmer John are planning a coordinated escape from their respective farms and have devised a method of encryption to protect their written communications.
Specifically, if one cow has a message, say, "International Olympiad in Informatics", it is altered by inserting the letters C, O, and W, in random location in the message, such that C appears before O, which appears before W. Then the cows take the part of the message between C and O, and the part between O and W, and swap them. Here are two examples:
International Olympiad in Informatics
->
CnOIWternational Olympiad in Informatics
International Olympiad in Informatics
->
International Cin InformaticsOOlympiad W
To make matters more difficult, the cows can apply their encryption scheme several times, by again encrypting the string that results from the previous encryption. One night, Farmer John's cows receive such a multiply-encrypted message. Write a program to compute whether or not the non-encrypted original message could have been the string:
Begin the Escape execution at the Break of Dawn
PROGRAM NAME: cryptcow
INPUT FORMAT
A single line (with both upper and lower case) with no more than 75 characters that represents the encrypted message.
SAMPLE INPUT (file cryptcow.in)
Begin the EscCution at the BreOape execWak of Dawn
OUTPUT FORMAT
Two integers on a single line. The first integer is 1 if the message decodes as an escape message; 0 otherwise. The second integer specifies the number of encryptions that were applied (or 0 if the first integer was 0).
SAMPLE OUTPUT (file cryptcow.out)
1 1
----------------------------------------------------
解法dfs+elfhash。
基本原理就是暴搜，但是要加上減枝。
以下減枝：
1. 由於添加的COW是一起的，因此給出的字符串的字符個數應該等於47（目標字符串的長度）+3*k。如果不滿足就可直接判斷無解。
2. 除了COW三個字符外，其他的字符的個數應該和目標串相一致。如果不一致也可直接判斷無解。
搜索中間肯定會出現很多相同的情況，因此需要開一個hash來記錄搜索到過哪些字符串，每搜索到一個字符串，就判重。
如果重複直接剪枝。這裏的字符串的hash函數可以采用ELFhash，但由於ELFhash的數值太大，
所以用函數值對一個大質數（我用的是35023）取餘，這樣可以避免hash開得太大，同時又可以減少衝突。
實驗證明，加上elfhash之後，最複雜的情況用時也隻有0.243.
3. 對搜索到的字符串，設不包含COW的最長前綴為n前綴（同樣也可以定義n後綴），那麼如果n前綴不等於目標串的長度相同的前綴，
那麼當前字符串一定無解，剪枝。N後綴也可采取相同的判斷方法。
4. 一個有解的字符串中，COW三個字母最早出現的應該是C，最後出現的應該是W，如果不滿足則剪枝。
5 . 當前字符串中任意兩個相鄰的COW字母中間所夾的字符串一定在目標串中出現過。如果不符合可立即剪枝。
6. 首先枚舉o的位置，那麼c的位置已經在0和O之間了，w的位置已經在o之後。
7. 在判斷當前串的子串是否包含在目標串中的時候，可以先做一個預處理：記錄每一個字母曾經出現過的位置，然後可以直接枚舉子串的第一個字母的位置。這樣比用pos要快2倍左右。
8. 判斷某個字符是否在原始串中。給每一個字符計算一個hash值，為其上一個字符左移n位加上當前字符的值。這樣就很容易個判斷是否含有這個字符串了
------------------------------------------
/*
ID:yunleis2
PROG:cryptcow
LANG:C++
*/
#include<iostream>
#include<fstream>
#include<string.h>
#include<ctime>
using namespace std;
char origin[]="Begin the Escape execution at the Break of Dawn";
int hashvalue[60];
#define HASHSIZE 871
int hashpos[3][HASHSIZE];
char encode[80];
int cnum,onum,wnum;
long begintime;
#define isencodechar(ch) (ch=='C'||ch=='O'||ch=='W')
int length;
int orilen;
#define MAXHASH 35023
bool hashsearch[MAXHASH];
inline bool exists(char enc[],int begin,int end){
for(int i=begin+1;i<=end;i++){
int hashvalue=enc[i-1]<<5;
hashvalue+=enc[i];
hashvalue%=HASHSIZE;
bool flag=false;
for(int j=0;j<3;j++){
int pos=hashpos[j][hashvalue];
if(pos==-1)
break;
if(pos!=-1&&origin[pos]==enc[i])
flag=true;
}
if(!flag)
return false;
}
return true;
}
fstream fin("cryptcow.in",ios::in );
fstream fout("cryptcow.out",ios::out);
void search(char * encode,int depth);
int main()
{
fin.getline(encode,80);
cout<<encode<<endl;
//check header;
cnum=onum=wnum=0;
for(int i=0;i<3*HASHSIZE;i++){
hashpos[i/HASHSIZE][i%HASHSIZE]=-1;
}
char value[70];
length=strlen(encode);
orilen=strlen(origin);
for(int i=0;i<length;i++){
if(encode[i]=='C')
++cnum;
if(encode[i]=='O')
++onum;
if(encode[i]=='W')
++wnum;
if(!isencodechar(encode[i])){
if(encode[i]==' ')
encode[i]=91;
encode[i]-=64;
}
if(i<orilen){
if(origin[i]==' ')
origin[i]=91;
origin[i]-=64;
int value=0;
if(i!=0){
value=origin[i-1]<<5;
}
value+=origin[i];
hashvalue[i]=value;
value%=HASHSIZE;
if(hashpos[0][value]==-1)
hashpos[0][value]=i;
else if(hashpos[1][value]==-1)
hashpos[1][value]=i;
else if(hashpos[2][value]==-1)
hashpos[2][value]=i;
else
cout<<"error"<<value<<" "<<i;
}
}
if((length-orilen)%3!=0){
fout<<0<<" "<<0<<endl;
return 0;
}
int last=-1;
for(int i=0;i<length;i++){
if(encode[i]=='C')
{
last=i;
}
if(encode[i]=='O')
{
if(!exists(encode,last+1,i-1)){
fout<<0<<" "<<0<<endl;
return 0;
}
last=i;
}
if(encode[i]=='W')
{
if(!exists(encode,last+1,i-1)){
fout<<0<<" "<<0<<endl;
return 0;
}
last=i;
}
}
if(cnum!=onum||cnum!=wnum){
fout<<0<<" "<<0<<endl;
return 0;
}
bool flag=true;
for(int i=0;i<length&&i<orilen;i++){
if(encode[i]=='C')
break;
else if(encode[i]!=origin[i])
{
fout<<0<<" "<<0<<endl;
return 0;
}
}
for(int i=0;i<length&&i<orilen;i++){
if(encode[length-i-1]=='W')
break;
else if(encode[length-i-1]!=origin[orilen-i-1]){
fout<<0<<" "<<0<<endl;
return 0;
}
}
#if 0
for(int i=0;i<length;i++){
cout<<(int)encode[i]<<" ";
}
cout<<endl;
for(int i=0;i<orilen;i++){
cout<<(int)origin[i]<<" ";
}
cout<<endl;
for(int i=0;i<orilen;i++){
cout<<hashvalue[i]<<" ";
}
#endif
begintime=clock();
search(encode,cnum);
fout<<0<<" "<<0<<endl;
//system("pause");
}
unsigned long
elf_hash( char *name)
{
unsigned long h = 0, g;
while (*name) {
h = (h << 4) + *name++;
if (g = h & 0xf0000000)
h ^= g >> 24;
h &= ~g;
}
return h;
}
void search(char * encode,int depth){
//cout<<<<endl;
long hash =elf_hash(encode)%MAXHASH;
if(hashsearch[hash])
{
cout<<encode<<endl;
return;
}
hashsearch[hash]=true;
char tmp[3];
char *decode=new char[strlen(encode)+1];
if(depth==0){
#if 0
for(int i=0;i<strlen(encode);i++){
if(encode[i]<65)
cout<<(char)(encode[i]+64);
else
cout<<encode[i];
}
cout<<endl;
#endif
if(exists(encode,0,strlen(encode)-1))
{
fout<<1<<" "<<cnum<<endl;
long end=clock();
cout<<end-begintime<<endl;
//system("pause");
exit(0);
}
}
if((strlen(encode)-orilen)%3!=0){
return ;
}
int cpos=-1,opos=-1,wpos=-1;
for(int j=0;j<strlen(encode);j++){
if(encode[j]=='O'){
opos=j;
for(int i=0;i<opos;i++){
if(encode[i]=='C'){
cpos=i;
bool flag=true;
if(cpos>opos)
continue;
if(cpos>0&&!isencodechar(encode[cpos-1])&&!(isencodechar(encode[opos+1]))){
tmp[0]=encode[cpos-1];
tmp[1]=encode[opos+1];
tmp[2]=0;
flag=exists(tmp,0,1);
if(!flag)
continue;
}
for(int s=strlen(encode)-1;s>opos;s--){
if(encode[s]=='W'){
wpos=s;
if((cpos<opos&&opos<wpos)){
bool flag=true;
if(cpos>0&&!isencodechar(encode[wpos-1])&&!(isencodechar(encode[cpos+1]))){
tmp[0]=encode[wpos-1];
tmp[1]=encode[cpos+1];
tmp[2]=0;
flag=exists(tmp,0,1);
if(!flag)
continue;
}
if(cpos>0&&!isencodechar(encode[opos-1])&&!(isencodechar(encode[wpos+1]))){
tmp[0]=encode[opos-1];
tmp[1]=encode[wpos+1];
tmp[2]=0;
flag=exists(tmp,0,1);
if(!flag)
continue;
}
int ptr=0;
//cout<<cpos<<" "<<opos<<" "<<wpos<<"\t";
for(int f=0;f<cpos;f++){
decode[ptr++]=encode[f];
}
for(int f=opos+1;f<wpos;f++)
decode[ptr++]=encode[f];
for(int f=cpos+1;f<opos;f++)
decode[ptr++]=encode[f];
for(int f=wpos+1;f<strlen(encode);f++)
decode[ptr++]=encode[f];
decode[ptr]=0;
search(decode,depth-1);
}
}
}
}
}
}
}
delete []decode;
}
Test 1: TEST OK [0.000 secs, 3076 KB]
Test 2: TEST OK [0.000 secs, 3076 KB]
Test 3: TEST OK [0.000 secs, 3076 KB]
Test 4: TEST OK [0.000 secs, 3076 KB]
Test 5: TEST OK [0.000 secs, 3076 KB]
Test 6: TEST OK [0.081 secs, 3076 KB]
Test 7: TEST OK [0.000 secs, 3076 KB]
Test 8: TEST OK [0.054 secs, 3076 KB]
Test 9: TEST OK [0.243 secs, 3076 KB]
Test 10: TEST OK [0.243 secs, 3076 KB]
最後更新：2017-04-02 06:51:55