|
|
Posted on 2008-07-31 01:16 Hero 閱讀(1489) 評論(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在第九個數據就超時了~
|