题意这题如果硬搜是肯定过不了的,一开始我的做法是,先搜'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,现传上官方报告]代码如下:
code
1/**//*
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;
14bool hash[51071];
15unsigned int ELFHash( char str[])
16
{
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{
33 int i,j,len;
34 char tmp[100];
35 len = strlen(str);
36 for(i = 0;i < 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+1;j < 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 <span style="COLOR