【hash】Three friends

【来源】：bzoj3916

【参考博客】

ＢＺＯＪ3916: [Baltic2014]friends

【哈希和哈希表】Three Friends

【Baltic2014】【BZOJ3916】friends

【题解】

首先hash整个串，然后分成三种情况，分别是前半段，中间，后半段，三段的字母试图去掉看能否拼起来。

如果可以，那么还需要考虑是否为唯一的。

唯一的意思是：串S，如果有选择两个不同的串S也能构成这个原串。

代码还是参考别人写的。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 const int N = 2e6+10;
 7 typedef unsigned long long ull ;
 8 const ull base = 13313;
 9 
10 ull Pow[N],Hash[N];
11 ull Lstr , Rstr , S;
12 char str[N],Ans[N];
13 int n,Mid,pos=-1;
14 
15 // NOT POSSIBLE = Odd or Not found a S
16 // NOT UNIQUE = exist least two S
17 // Else = The answer S
18 
19 // 切割字符串返回hash值
20 ull Cut_str( int L ,int R ){
21     ull ans = Hash[R] - Hash[L-1] * Pow[R-L+1] ;
22     return ans ;
23 }
24 
25 bool check (int i){
26     //如果未被标记过，则标记 返回true
27     //如果标记过，同时这个字符串和暂存的串不一样则返回false
28     if( pos == -1 || S == Lstr ){
29         pos = i ;
30         S = Lstr ;
31         return true ;
32     }else{
33         return false ;
34     }
35 }
36 int main()
37 {
38     scanf("%d%s",&n,str+1);
39     Mid = n >> 1 ;
40 
41     //偶数情况下无法构成
42     if( n%2==0 )    return puts("NOT POSSIBLE"),0;
43 
44     Pow[0] = 1;
45     for(int i=1;i<=n;i++){
46         Pow[i] = Pow[i-1] * base ;
47         Hash[i] = Hash[i-1] * base + (ull)(str[i]-'A'+1);
48         //所有字符串只包含大写英文字母
49     }
50 
51     // delete one character in [1,Mid]
52     for(int i=1 ; i<=Mid ; i++ ){
53         Lstr = Cut_str(1,i-1) * Pow[Mid+1-i] + Cut_str(i+1,Mid+1);
54         Rstr = Cut_str(Mid+2,n);
55         if( Lstr == Rstr ) if( !check(i) ) return puts("NOT UNIQUE"),0;
56     }
57 
58     // delete Mid + 1
59     Lstr = Hash[Mid] ;
60     Rstr = Hash[n] - Hash[Mid+1] * Pow[Mid];
61     if( Lstr == Rstr ) if( !check(Mid+1) ) return puts("NOT UNIQUE"),0;
62 
63     // delete [Mid+2,n]
64 
65     for(int i=Mid+2 ; i<=n; i++ ){
66         Lstr = Hash[Mid];
67         Rstr = Cut_str(Mid+1,i-1) * Pow[n-i] + Cut_str(i+1,n);
68         if( Lstr == Rstr ) if( !check(i) ) return puts("NOT UNIQUE"),0;
69     }
70 
71     if( pos == -1 ){
72         return puts("NOT POSSIBLE"),0;
73     }
74 
75     int len = n/2,cnt = 0 ;
76     for(int i=1; i<=n && len ; i++ ){
77         if( pos == i ) continue;
78         Ans[cnt++] = str[i] ;
79         len -- ;
80     }
81     Ans[cnt] = '';
82     printf("%s
",Ans);
83     return 0 ;
84 }
85 
86 /*
87 
88 7
89 ABXCABC
90 
91 */

View Code

【hash】Three friends

ＢＺＯＪ3916: [Baltic2014]friends

【 哈希和哈希表】Three Friends

【Baltic2014】【BZOJ3916】friends

【哈希和哈希表】Three Friends