首页 > 代码库 > USACO 6.3 Cryptcowgraphy

USACO 6.3 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

——————————————————————————————————————————题解
本来水了过去想看看题解
嗯,第一个题解464行,第二个题解465行
除掉一堆注释回车的话至少也200多
然后有点害怕,照着nocow的一堆剪枝写了写……
本来有个错误的想法是最后一次更新的C应该在最前面,也不知道我是怎么想的……水过4个点

这道题HASH会有冲突,可能舍掉一些不知道是不是正解的可能性解,但是这棵树太大了,胡乱砍掉的一些东西结果没有什么影响……题解里用的是hash挂链表
用ELFhash函数……一个看起来很玄妙的hash函数

然后再剪枝就是针对一个串C肯定是第一个出现,W肯定是最后一个出现,这些C,O,W出现的子串一定在目标串里出现过,暴力匹配

顺序也很重要,我们先中间后两边,O->C->W,其中W倒序搜索
  1 /*
  2 ID: ivorysi
  3 LANG: C++
  4 PROG: cryptcow
  5 */
  6 #include <iostream>
  7 #include <cstdio>
  8 #include <cstring>
  9 #include <queue>
 10 #include <set>
 11 #include <vector>
 12 #include <algorithm>
 13 #define siji(i,x,y) for(int i=(x);i<=(y);++i)
 14 #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
 15 #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
 16 #define sigongzi(j,x,y) for(int j=(x);j>(y);--j)
 17 #define inf 0x5f5f5f5f
 18 #define ivorysi
 19 #define mo 97797977
 20 #define hash 974711
 21 #define base 47
 22 #define fi first
 23 #define se second
 24 #define pii pair<int,int>
 25 #define esp 1e-8
 26 typedef long long ll;
 27 using namespace std;
 28 string os="Begin the Escape execution at the Break of Dawn";
 29 string a;
 30 int st[60][10],pt[60];
 31 bool flag;
 32 bool ha[hash+3];
 33 int id(char c) {
 34     if(a<=c && c<=z) return c-a+1;
 35     if(A<=c && c<=Z) return c-A+1+26;
 36     else return 53;
 37 }
 38 int ELFhash() {
 39     int l=0,len=a.length();
 40     unsigned int h=0,g;
 41     while(l!=len) {
 42         h=(h<<4)+a[l];//右移四位加上一个字符
 43         if(g=h&0xF0000000L) {//最高四位不为0
 44             h^=(g>>24);//最高四位和5~8位异或
 45             h &= ~g;//删除最高四位
 46         }
 47         ++l;
 48     }
 49     return h&0x7FFFFFFF;//处理成非负数
 50 }
 51 void get_st() {
 52     int len=os.length();
 53     xiaosiji(i,0,len) {
 54         st[id(os[i])][++pt[id(os[i])]]=i;
 55     }
 56 }
 57 bool check_substr() {
 58     int len=a.length();
 59     int s=0,t=0;
 60     for(int i=0;i<len;++i) {
 61         if(a[i]!=C && a[i]!=O && a[i]!=W) {
 62             if(a[i]!=os[i]) return 0;
 63         }
 64         else {
 65             if(a[i]!=C) return 0;
 66             else {s=i;break;}
 67         }
 68     }
 69     for(int i=len-1,los=os.length()-1;i>=0;--i,--los) {
 70         if(a[i]!=C && a[i]!=O && a[i]!=W) {
 71             if(a[i]!=os[los]) return 0;
 72         }
 73         else {
 74             if(a[i]!=W) return 0;
 75             else {t=i;break;}
 76         }
 77     }
 78     for(int i=s+1;i<t;++i) {
 79         
 80         int rt=i,to;
 81         while(rt!=len &&(a[rt]==C || a[rt]==O || a[rt]==W) )++rt;
 82         if(rt==len) break;
 83         to=rt;
 84         while(to!=len && a[to]!=C && a[to]!=O && a[to]!=W) ++to;
 85         --to;
 86         bool f=0;
 87         int pos=id(a[rt]);
 88         siji(k,1,pt[pos]) {
 89             siji(j,rt,to) {
 90                 if(st[pos][k]+j-rt>=os.length() ||
 91                     a[j]!=os[st[pos][k]+j-rt]) goto fail;
 92             }
 93             f=1;
 94             break;
 95             fail:;
 96         }
 97         if(!f) return 0;
 98         i=to;
 99     }
100     return 1;
101 }
102 bool dfs() {
103     if(a==os) return true;
104     int h=ELFhash()%hash;
105     if(ha[h]!=0) return false;
106     ha[h]=1;
107     int len=a.length(); 
108     siji(i,1,len-1) {
109         if(a[i]==O) {
110             siji(j,0,i) {
111                 if(a[j]==C) {
112                     gongzi(k,len-1,i+1) {
113                         if(a[k]==W) {
114                             string temp=a;
115                             a.replace(j,k-j+1,temp.substr(i+1,k-i-1)+temp.substr(j+1,i-j-1));
116                             if(check_substr() && dfs()) return true;
117                             a=temp;
118                         }
119                     }
120                 }
121             }
122         
123         }
124     }
125     return false;
126 }
127 void solve() {
128     getline(cin,a);
129     get_st();
130     int len=a.length();
131     flag=1;
132     int c=0,o=0,w=0;
133     xiaosiji(i,0,len) {
134         if(a[i]==W) ++w;
135         if(a[i]==C) ++c;
136         if(a[i]==O) ++o;
137     }
138     if(c!=o || c!=w || w!=o) flag=0;
139     if(len-c*3!=os.length()) flag=0;
140     if(flag) flag=check_substr();
141     
142     if(!flag) {printf("0 0\n");return;}
143     flag=dfs();
144     if(flag) printf("1 %d\n",c);
145     else printf("0 0\n");
146 }
147 int main(int argc, char const *argv[])
148 {
149 #ifdef ivorysi
150     freopen("cryptcow.in","r",stdin);
151     freopen("cryptcow.out","w",stdout);
152 #else
153     freopen("f1.in","r",stdin);
154 #endif
155     solve();
156     return 0;
157 }

 

 

USACO 6.3 Cryptcowgraphy