我希望你是我独家记忆

一段永远封存的记忆,随风而去
posts - 263, comments - 31, trackbacks - 0, articles - 3
   :: 首页 :: 新随笔 ::  :: 聚合  :: 管理

USACO--414--(ELFHash)

Posted on 2008-07-31 01:16 Hero 阅读(1437) 评论(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 ;

    
forint 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中
    forint 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 
= "" ;
    
forint i=0; i<c; i++ )        trans += sour[i] ;
    
forint i=o+1; i<w; i++ )    trans += sour[i] ;
    
forint i=c+1; i<o; i++ )    trans += sour[i] ;
    
forint 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 ;

    
iffalse == substr_in_dest( sour ) )    return false ;

    
forint o=1; o<sour.size(); o++ ) {//枚举--然后深度优先搜索
        if'O' == sour[o] ) {
            
forint c=0; c<o; c++ ) {
                
if'C' == sour[c] ) {
                    
forint 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 ;
    
forint 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 
<< "" << 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 Ryan Hardy
很厉害

# re: USACO--414--(ELFHash)  回复  更多评论   

2009-03-30 10:33 by tvt
有问题。
Hash完全没有碰撞处理,而且空间开的很小,最后几个点有很多串都是实际上未处理完全靠碰撞蒙过去的。
把Hash表开大减小碰撞几率的话马上就通不过。
另外如果测试点多几个正确数据很可能由于正确性而出问题。这是牺牲正确性的投机写法

# re: USACO--414--(ELFHash)  回复  更多评论   

2010-12-11 23:24 by klion26
@tvt
这个没处理冲突确实是个问题,不过你说的开大点就过不了,感觉不对.应该是小一点不对.我刚做了这题,数组开的非常大.也用的ELFHash,没处理冲突,过了[这里最多加密9此],如果数组开小点到时很有可能错误,还有如果不加substr_in_dest这个函数的判断,也会导致冲突.

# re: USACO--414--(ELFHash)  回复  更多评论   

2011-01-27 10:32 by st8676746
tvt确实没说错~他的意思是hash开大就会超时。
一旦把hash数组开大后,处理的字符串就会变多(因为你没处理冲突,所以在hash较小时很多字符串其实被你跳过了)。
我把你的hash开为1000003在第九个数据就超时了~

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理