|
|
Posted on 2008-07-31 01:16 Hero 阅读(1457) 评论(4) 编辑 收藏 引用 所属分类: 代码如诗－－ACM
/*
ID: wangzha4
LANG: C++
TASK: cryptcow
*/
/*
Executing
Test 1: TEST OK [0.011 secs, 2900 KB]
Test 2: TEST OK [0.000 secs, 2900 KB]
Test 3: TEST OK [0.000 secs, 2900 KB]
Test 4: TEST OK [0.011 secs, 2896 KB]
Test 5: TEST OK [0.000 secs, 2896 KB]
Test 6: TEST OK [0.119 secs, 2896 KB]
Test 7: TEST OK [0.022 secs, 2900 KB]
Test 8: TEST OK [0.097 secs, 2900 KB]
Test 9: TEST OK [0.270 secs, 2896 KB]
Test 10: TEST OK [0.335 secs, 2896 KB]
*/
//这道题目的搜索其实就是类似于深度优先搜索－－暴搜
//判断是否是加密过的过程其实是DFS的过程
//主要在于剪枝( 参考了nocow的讲解 )
/*
1. 由于添加的COW是一起的，因此给出的字符串的字符个数应该等于47（目标字符串的长度）+3*k。如果不满足就可直接判断无解。
2. 除了COW三个字符外，其他的字符的个数应该和目标串相一致。如果不一致也可直接判断无解。
搜索中间肯定会出现很多相同的情况，因此需要开一个hash来记录搜索到过哪些字符串，每搜索到一个字符串，就判重。
如果重复直接剪枝。这里的字符串的hash函数可以采用ELFhash，但由于ELFhash的数值太大，
所以用函数值对一个大质数（我用的是35023）取余，这样可以避免hash开得太大，同时又可以减少冲突。
3. 对搜索到的字符串，设不包含COW的最长前缀为n前缀（同样也可以定义n后缀），那么如果n前缀不等于目标串的长度相同的前缀，
那么当前字符串一定无解，剪枝。N后缀也可采取相同的判断方法。
4. 一个有解的字符串中，COW三个字母最早出现的应该是C，最后出现的应该是W，如果不满足则剪枝。
5 . 当前字符串中任意两个相邻的COW字母中间所夹的字符串一定在目标串中出现过。如果不符合可立即剪枝。
6. 需要优化搜索顺序。经过试验我们可以发现，O的位置对于整个COW至关重要。可以说，O的位置决定了整个串是否会有解。
因此，我们在搜索时，应该先枚举O的位置，然后再枚举C和W的位置。其中W要倒序枚举。这样比依次枚举COW至少要快20~30倍。
7. 在判断当前串的子串是否包含在目标串中的时候，可以先做一个预处理：记录每一个字母曾经出现过的位置，然后可以直接枚举子串的第一个字母的位置。这样比用pos要快2倍左右。
*/
#include <iostream>
#include <string>
#include <algorithm>
using namespace std ;
#define llong unsigned long long
#define unint unsigned int
#define printline printf( "\n" )
const int INF = 1000000 ;
const int size = 155 ;
const int hashsize = 51071 ;
bool hasHashed[hashsize] = { false } ;
const string dest = "Begin the Escape execution at the Break of Dawn" ;
string text ; string trans ;
unsigned int ELFHash( string str )
{
unsigned int hash = 0 ;
unsigned int x = 0 ;
for( int i=0; i<str.length(); i++ ) {
hash = ( hash << 4 ) + ( str[i] ) ;
if( ( x = hash & 0xF0000000L ) != 0 ) {
hash ^= ( x >> 24 ) ;
hash &= ~x ;
}
}
return ( hash & 0x7FFFFFFF ) ;
}
bool substr_in_dest( string &sour)
{//判断夹在COW之间的字符串是否存在dest中
for( int i=0; i<sour.size(); i++ ) {
if( sour[i]=='C' || sour[i]=='O' || sour[i]=='W' ) continue ;
int j = i + 1 ;
for( j=i+1; j<sour.size(); j++ ) {
if( 'C'==sour[j] || 'O'==sour[j] || 'W'==sour[j] ) break ;
}
if( dest.find( sour.substr( i, j-i ) ) == string::npos ) return false ;
i = j ;
}
return true ;
}
string Transform( string &sour, int c, int o, int w )
{
trans = "" ;
for( int i=0; i<c; i++ ) trans += sour[i] ;
for( int i=o+1; i<w; i++ ) trans += sour[i] ;
for( int i=c+1; i<o; i++ ) trans += sour[i] ;
for( int i=w+1; i<sour.size(); i++ ) trans += sour[i] ;
//trans += '\0' ;//trans != trans + '\0'
//cout << trans << endl ;
return trans ;
}
bool IsEncrypted( string sour )
{
unsigned int hashval = ELFHash( sour ) % hashsize ;
if( hasHashed[hashval] ) return false ;
hasHashed[hashval] = true ;
if( sour == dest ) return true ;
if( false == substr_in_dest( sour ) ) return false ;
for( int o=1; o<sour.size(); o++ ) {//枚举－－然后深度优先搜索
if( 'O' == sour[o] ) {
for( int c=0; c<o; c++ ) {
if( 'C' == sour[c] ) {
for( int w=sour.size()-1; w>o; w-- ) {
if( 'W' == sour[w] )
if( IsEncrypted( Transform( sour, c, o, w ) ) ) return true ;
}//递归判断是否有一个合理的转换解，如果有直接return true; 相当于深度优先搜索
}
}
}
}
return false ;
}
int main()
{
//freopen( "in.txt", "r", stdin ) ;
freopen( "cryptcow.in", "r", stdin ) ;
freopen( "cryptcow.out","w",stdout ) ;
getline( cin, text ) ; //cout << text << endl ;
if( ( text.size()-dest.size() ) % 3 != 0 )
{ printf( "0 0\n" ) ; return 0 ; }
int numc, numo, numw ; numc = numo = numw = 0 ;
for( int i=0; i<text.size(); i++ ) {
if( 'C' == text[i] ) numc++ ;
if( 'O' == text[i] ) numo++ ;
if( 'W' == text[i] ) numw++ ;
}
if( numc!=numo || numc != numw || numo != numw )
{ printf( "0 0\n" ) ; return 0 ; }
if( IsEncrypted( text ) ) {
cout << "1 " << count( text.begin(),text.end(),'C' ) << endl ;
}
else {
printf( "0 0\n" ) ;
}
return 0 ;
}
Feedback
# re: USACO－－414－－(ELFHash) 回复 更多评论
2009-02-13 21:35 by
很厉害
# re: USACO－－414－－(ELFHash) 回复 更多评论
2009-03-30 10:33 by
有问题。
Hash完全没有碰撞处理，而且空间开的很小，最后几个点有很多串都是实际上未处理完全靠碰撞蒙过去的。
把Hash表开大减小碰撞几率的话马上就通不过。
另外如果测试点多几个正确数据很可能由于正确性而出问题。这是牺牲正确性的投机写法
# re: USACO－－414－－(ELFHash) 回复 更多评论
2010-12-11 23:24 by
@tvt
这个没处理冲突确实是个问题,不过你说的开大点就过不了,感觉不对.应该是小一点不对.我刚做了这题,数组开的非常大.也用的ELFHash,没处理冲突,过了[这里最多加密9此],如果数组开小点到时很有可能错误,还有如果不加substr_in_dest这个函数的判断,也会导致冲突.
# re: USACO－－414－－(ELFHash) 回复 更多评论
2011-01-27 10:32 by
tvt确实没说错~他的意思是hash开大就会超时。
一旦把hash数组开大后，处理的字符串就会变多（因为你没处理冲突，所以在hash较小时很多字符串其实被你跳过了）。
我把你的hash开为1000003在第九个数据就超时了~
|