那么這題的思路如下:
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
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 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)
好友鏈接
搜索
最新評論
閱讀排行榜
評論排行榜
|
|