USACO 4-1-4Cryptcowgraphy
题意
这题如果硬搜是肯定过不了的,一开始我的做法是,先搜’C’再搜’O’最后’W’,然后中间判断一些,如果不可能到达目标状态[原字符串],就剪枝剪掉,我的剪枝方法很简单,一是开个大数组记录所有已经出现过的字符串,然后如果再搜到这里的话,就直接推出就行了,不用再往下搜了[因为前面已经搜过一次不行了],还有一个就是没两个相邻的编码字符[C,O,W]之间的字符串一定是目标串的字串也行[因为交换不会改变这些字符串的顺序].可是这样还是超时了,然后问了下czw.他说直接hash,先搜O,然后再处理C和W,我想这样的话,那么我的就只用把搜索顺序改一下就行了,不过由于代码已经很混乱了,所以就直接重写了,而且还借用了网上的一个字符串hash函数ELFHash,然后写出来之后发现非常之蛋疼.我的结果不对,找来分代码来匹配,基本一样的,只不过我没有加我上面那第二个优化,后来加上之后发现过了,这样看来是hash函数冲突了,但是我没处理.所以导致程序挂了.
那么这题的思路如下:
1首先搜索顺序是先O再C和W
2用字符串hash函数hash判重
3如果发现有两个相邻的编码字符之间的字符串不是目标串的字串的话,就剪枝
这样可以把所有的数据都1s内搞定
[此解法有一定的偶然性,原因是ELFHash造成的(当我把hash表开到100000,而且模的那个数也是100000的时候,第8个数据过不去).所以下面的也可以说是cheat过去的.正在看官方的,看懂后我会再发出来.
官方的也是用到hash,不过hash的时候都是模一个大素数的,不然冲突的可能性会很大.还有第二种方法似乎没用到hash,现传上官方报告]
代码如下:
/
2 ID:qcx97811
3 LANG:C++
4 TASK:cryptcow
5 /
6#include <stdio.h>
7#include <string.h>
8#include <stdlib.h>
9#include <math.h>
10
11char ori_str[100] = “Begin the Escape execution at the Break of Dawn”//原字符串
12char in_str[100];//输入字符串
13int ii_c,ii_o,ii_w//c o w的个数
14bool hash[51071];//hash数组
15unsigned int ELFHash( char str[])
16{//ELFHash函数
17 unsigned int hash = 0 ;
18 unsigned int x = 0 ;
19 int len = strlen(str);
20 for( int i=0 i< len; i++ ) {
21 hash = ( hash << 4 ) + ( str[i] ) ;
22 if( ( x = hash 0xF0000000L ) != 0 ) {
23 hash ^= ( x >> 24 ) ;
24 hash = ~x ;
25 }
26 }
27
28 return (hash 0x7FFFFFFF);
29}
30
31bool could(char str[])
32{//看str是否能通过解码到达原串,也就是判断每两个编码字符中间的字串是不是原串的字串
33 int i,j,len
34 char tmp[100];
35 len = strlen(str);
36 for(i = 0i < len;i++)
37 {
38 if(‘C’ == str[i] || ‘W’ == str[i] || ‘O’ == str[i])
39 {
40 continue
41 }
42 j = i+1
43 for(j = i+1j < len;j++)
44 {
45 if(‘C’ == str[j] || ‘W’ == str[j] || ‘O’ == str[j])
46 {
47 break
48 }
49 }
50 strncpy(tmp,str+i,j-i);
51 tmp[j-i]=‘\0’
52 if(NULL == strstr(ori_str,tmp))
53 return false
54 i = j
55 }
56 return true
57}
58void tran(char str[],int c,int o,int w,char des[])
59{//解码过程
60 int i,j,len
61 len = strlen(str);
62 for(i = 0i < c;i++)
63 {
64 des[i] = str[i];
65 }
66 for(j = o+1j < w;j++,i++)
67 {
68 des[i] = str[j];
69 }
70 for(j = c+1j < o;j++,i++)
71 {
72 des[i] = str[j];
73 }
74 for(j = w+1j < len;j++,i++)
75 {
76 des[i] = str[j];
77 }
78 des[i] = ‘\0’
79 return ;
80}
81bool work(char str[])
82{//深搜
83 int c,o,w
84 char str_tmp[100];
85 int hs,len
86 hs = ELFHash(str)%51071
87 if(hash[hs])//已找过
88 return false
89 hash[hs] = true
90 if(false == could(str))//不加这句会错,应该是hash冲突了,而我没处理冲突
91 return false
92 if(0 == strcmp(str,ori_str))
93 {//已找到
94 return true
95 }
96 len = strlen(str);
97 for(o = 1o < len;o++)
98 {
99 if(‘O’ == str[o])
100 {
101 for(c = 0c < o;c++)
102 {
103 if(‘C’ == str[c])
104 {
105 for(w = len-1w >; o;w–)
106 {
107 if(‘W’ == str[w])
108 {
109 tran(str,c,o,w,str_tmp);
110 if(work(str_tmp))
111 return true
112 }
113 }
114 }
115 }
116 }
117 }
118 return false
119}
120void input()
121{//读入
122 freopen(“cryptcow.in”,“r”,stdin);
123 int i
124 int len
125 gets(in_str);
126 len = strlen(in_str);
127 ii_c = ii_o = ii_w = 0
128 for(i = 0i < len;i++)
129 {
130 if(‘C’ == in_str[i])
131 ii_c++
132 if(‘O’ == in_str[i])
133 ii_o++
134 if(‘W’ == in_str[i])
135 ii_w++
136 }
137 if((len-47)%3 != 0)
138 {
139 printf(“0 0\n“);
140 exit(0);
141 }
142 if(ii_c != ii_o || ii_o != ii_w || ii_w != ii_c)
143 {
144 printf(“0 0\n“);
145 exit(0);
146 }
147}
148int main(void)
149{
150 input();
151 freopen(“cryptcow.out”,“w”,stdout);
152 if(work(in_str))
153 printf(“1 %d\n“,ii_c);
154 else
155 {
156 printf(“0 0\n“);
157 }
158}
2 ID:qcx97811
3 LANG:C++
4 TASK:cryptcow
5 /
6#include <stdio.h>
7#include <string.h>
8#include <stdlib.h>
9#include <math.h>
10
11char ori_str[100] = “Begin the Escape execution at the Break of Dawn”//原字符串
12char in_str[100];//输入字符串
13int ii_c,ii_o,ii_w//c o w的个数
14bool hash[51071];//hash数组
15unsigned int ELFHash( char str[])
16{//ELFHash函数
17 unsigned int hash = 0 ;
18 unsigned int x = 0 ;
19 int len = strlen(str);
20 for( int i=0 i< len; i++ ) {
21 hash = ( hash << 4 ) + ( str[i] ) ;
22 if( ( x = hash 0xF0000000L ) != 0 ) {
23 hash ^= ( x >> 24 ) ;
24 hash = ~x ;
25 }
26 }
27
28 return (hash 0x7FFFFFFF);
29}
30
31bool could(char str[])
32{//看str是否能通过解码到达原串,也就是判断每两个编码字符中间的字串是不是原串的字串
33 int i,j,len
34 char tmp[100];
35 len = strlen(str);
36 for(i = 0i < len;i++)
37 {
38 if(‘C’ == str[i] || ‘W’ == str[i] || ‘O’ == str[i])
39 {
40 continue
41 }
42 j = i+1
43 for(j = i+1j < len;j++)
44 {
45 if(‘C’ == str[j] || ‘W’ == str[j] || ‘O’ == str[j])
46 {
47 break
48 }
49 }
50 strncpy(tmp,str+i,j-i);
51 tmp[j-i]=‘\0’
52 if(NULL == strstr(ori_str,tmp))
53 return false
54 i = j
55 }
56 return true
57}
58void tran(char str[],int c,int o,int w,char des[])
59{//解码过程
60 int i,j,len
61 len = strlen(str);
62 for(i = 0i < c;i++)
63 {
64 des[i] = str[i];
65 }
66 for(j = o+1j < w;j++,i++)
67 {
68 des[i] = str[j];
69 }
70 for(j = c+1j < o;j++,i++)
71 {
72 des[i] = str[j];
73 }
74 for(j = w+1j < len;j++,i++)
75 {
76 des[i] = str[j];
77 }
78 des[i] = ‘\0’
79 return ;
80}
81bool work(char str[])
82{//深搜
83 int c,o,w
84 char str_tmp[100];
85 int hs,len
86 hs = ELFHash(str)%51071
87 if(hash[hs])//已找过
88 return false
89 hash[hs] = true
90 if(false == could(str))//不加这句会错,应该是hash冲突了,而我没处理冲突
91 return false
92 if(0 == strcmp(str,ori_str))
93 {//已找到
94 return true
95 }
96 len = strlen(str);
97 for(o = 1o < len;o++)
98 {
99 if(‘O’ == str[o])
100 {
101 for(c = 0c < o;c++)
102 {
103 if(‘C’ == str[c])
104 {
105 for(w = len-1w >; o;w–)
106 {
107 if(‘W’ == str[w])
108 {
109 tran(str,c,o,w,str_tmp);
110 if(work(str_tmp))
111 return true
112 }
113 }
114 }
115 }
116 }
117 }
118 return false
119}
120void input()
121{//读入
122 freopen(“cryptcow.in”,“r”,stdin);
123 int i
124 int len
125 gets(in_str);
126 len = strlen(in_str);
127 ii_c = ii_o = ii_w = 0
128 for(i = 0i < len;i++)
129 {
130 if(‘C’ == in_str[i])
131 ii_c++
132 if(‘O’ == in_str[i])
133 ii_o++
134 if(‘W’ == in_str[i])
135 ii_w++
136 }
137 if((len-47)%3 != 0)
138 {
139 printf(“0 0\n“);
140 exit(0);
141 }
142 if(ii_c != ii_o || ii_o != ii_w || ii_w != ii_c)
143 {
144 printf(“0 0\n“);
145 exit(0);
146 }
147}
148int main(void)
149{
150 input();
151 freopen(“cryptcow.out”,“w”,stdout);
152 if(work(in_str))
153 printf(“1 %d\n“,ii_c);
154 else
155 {
156 printf(“0 0\n“);
157 }
158}
