那么這題的思路如下:
1首先搜索順序是先O再C和W
2用字符串hash函數(shù)hash判重
3如果發(fā)現(xiàn)有兩個(gè)相鄰的編碼字符之間的字符串不是目標(biāo)串的字串的話,就剪枝
這樣可以把所有的數(shù)據(jù)都1s內(nèi)搞定
[此解法有一定的偶然性,原因是ELFHash造成的(當(dāng)我把hash表開到100000,而且模的那個(gè)數(shù)也是100000的時(shí)候,第8個(gè)數(shù)據(jù)過(guò)不去).所以下面的也可以說(shuō)是cheat過(guò)去的.正在看官方的,看懂后我會(huì)再發(fā)出來(lái),官方的也是用到hash,不過(guò)hash的時(shí)候都是模一個(gè)大素?cái)?shù)的,不然沖突的可能性會(huì)很大.還有第二種方法似乎沒(méi)用到hash,現(xiàn)傳上官方報(bào)告]
代碼如下:
  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
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 28 | 29 | 30 | 1 | 2 | 3 | 4 | | 5 | 6 | 7 | 8 | 9 | 10 | 11 | | 12 | 13 | 14 | 15 | 16 | 17 | 18 | | 19 | 20 | 21 | 22 | 23 | 24 | 25 | | 26 | 27 | 28 | 29 | 30 | 31 | 1 | | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|
常用鏈接
留言簿(1)
隨筆分類(99)
隨筆檔案(71)
好友鏈接
搜索
最新評(píng)論
閱讀排行榜
評(píng)論排行榜
|
|