[bzoj3790]神奇项链

可以发现一定只会填以某个字符为中心的最长回文串,然后用hash+二分/manacher求出以i为中心的最大的长度(即所有可能会填的回文串,共n个),将这些回文串根据左端点排序后贪心选择在当前位置之前最远的结束位置即可

[bzoj3790]神奇项链
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 100005
 4 #define mod 1000000007
 5 pair<int,int>hw[N];
 6 int n,ma,ans,s1[N],s2[N],mi[N];
 7 char s[N],ss[N]; 
 8 int hash1(int x,int y){
 9     return (s1[y]-1LL*s1[x]*mi[y-x]%mod+mod)%mod;
10 }
11 int hash2(int x,int y){
12     return (s2[y]-1LL*s2[x]*mi[x-y]%mod+mod)%mod;
13 }
14 int main(){
15     while (scanf("%s",ss)!=EOF){
16         n=0;
17         for(int i=0;ss[i];i++){
18             s[++n]='{';
19             s[++n]=ss[i];
20         }
21         s[++n]='{';
22         s2[n+1]=0;
23         mi[0]=1;
24         for(int i=1;i<=n;i++)mi[i]=mi[i-1]*29LL%mod;
25         for(int i=1;i<=n;i++)s1[i]=(s1[i-1]*29LL+s[i]-'a')%mod;
26         for(int i=n;i;i--)s2[i]=(s2[i+1]*29LL+s[i]-'a')%mod;
27         for(int i=1;i<=n;i++){
28             int l=0,r=min(i,n-i);
29             while (l<r){
30                 int mid=(l+r+1>>1);
31                 if (hash1(i,i+mid)==hash2(i,i-mid))l=mid;
32                 else r=mid-1;
33             }
34             hw[i]=make_pair(i-l,i+l);
35         }
36         sort(hw+1,hw+n+1);
37         ma=ans=0;
38         for(int i=1,j=1;i<=n;i++){
39             if (hw[i].first>j){
40                 j=ma;
41                 ma=0;
42                 ans++;
43             }
44             if (hw[i].second>j)ma=max(ma,hw[i].second);
45         }
46         printf("%d\n",ans-1);
47     }
48 }
View Code

 

上一篇:【NOIP2019模拟赛19.8.20】题解


下一篇:RMQ问题ST算法与模板