2020-2021:teams:die_java:front_page_summertrain13
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:die_java:front_page_summertrain13 [2020/08/21 17:04] wxg [J.Just Skip The Problem] |
2020-2021:teams:die_java:front_page_summertrain13 [2020/08/21 17:07] (当前版本) wxg [训练总结] |
||
|---|---|---|---|
| 行 14: | 行 14: | ||
| === 题意 === | === 题意 === | ||
| + | 给了一个字符串，问你有多少子串，自身是回文串而且一半也是回文串 | ||
| === 题解 === | === 题解 === | ||
| + | 由回文自动机的性质知道一个串的本质不同的回文串最多有 $n$ 个，我们可以用回文自动机统计不同回文串的个数并标记位置，之后枚举每个串并用哈希判断他的一半是不是回文串就行 | ||
| <hidden 代码><code cpp> | <hidden 代码><code cpp> | ||
| + | #include<iostream> | ||
| + | #include<cstdio> | ||
| + | #include<algorithm> | ||
| + | #include<cstring> | ||
| + | #define ll long long | ||
| + | using namespace std; | ||
| + | const int N=300055; | ||
| + | char s[N]; | ||
| + | int fail[N],len[N],last,n,tot,ch[N][26],cnt[N],ps[N],ans[N]; | ||
| + | ll hs[N],pw[N],hs2[N]; | ||
| + | int newnode(int x) | ||
| + | { | ||
| + | len[++tot]=x;return tot; | ||
| + | } | ||
| + | void init() | ||
| + | { | ||
| + | tot=-1;last=0; | ||
| + | newnode(0);newnode(-1); | ||
| + | fail[0]=1;s[0]=-1; | ||
| + | } | ||
| + | |||
| + | int getfail(int pos,int x) | ||
| + | { | ||
| + | while(s[pos-len[x]-1]!=s[pos]) x=fail[x]; | ||
| + | return x; | ||
| + | } | ||
| + | |||
| + | void add(int x,int c) | ||
| + | { | ||
| + | int cur=getfail(x,last); | ||
| + | if(!ch[cur][c]) | ||
| + | { | ||
| + | int now=newnode(len[cur]+2); | ||
| + | fail[now]=ch[getfail(x,fail[cur])][c]; | ||
| + | ch[cur][c]=now; | ||
| + | } | ||
| + | cnt[last=ch[cur][c]]++;ps[last]=x; | ||
| + | } | ||
| + | ll query(int l,int r,int opt) | ||
| + | { | ||
| + | int len=r-l+1; | ||
| + | if(opt==1) | ||
| + | { | ||
| + | return hs[r]-hs[l-1]*pw[len]; | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | return hs2[l]-hs2[r+1]*pw[len]; | ||
| + | } | ||
| + | } | ||
| + | int chk(int l,int r) | ||
| + | { | ||
| + | int mid=l+r>>1,len=r-l+1; | ||
| + | if(len&1) | ||
| + | { | ||
| + | return query(l,mid,1)==query(mid,r,2); | ||
| + | } | ||
| + | else return query(l,mid,1)==query(mid+1,r,2); | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | pw[0]=1; | ||
| + | for(int i=1;i<N;i++) | ||
| + | pw[i]=pw[i-1]*31; | ||
| + | while(scanf("%s",s+1)!=EOF) | ||
| + | { | ||
| + | n=strlen(s+1);init(); | ||
| + | for(int i=1;i<=n;i++) | ||
| + | { | ||
| + | add(i,s[i]-'a');//if(i<=3) cout<<last<<endl; | ||
| + | hs[i]=hs[i-1]*31+(s[i]-'a'+1); | ||
| + | } | ||
| + | hs2[n+1]=0; | ||
| + | for(int i=n;i;i--) | ||
| + | hs2[i]=hs2[i+1]*31+(s[i]-'a'+1); | ||
| + | for(int i=tot;i>1;i--) | ||
| + | { | ||
| + | // cout<<len[i]<<" "<<cnt[i]<<" "<<ps[i]<<endl; | ||
| + | cnt[fail[i]]+=cnt[i]; | ||
| + | if(chk(ps[i]-len[i]+1,ps[i]-len[i]+(len[i]+1)/2)) | ||
| + | ans[len[i]]+=cnt[i]; | ||
| + | } | ||
| + | printf("%d",ans[1]);ans[1]=0; | ||
| + | for(int i=0;i<=tot;i++) | ||
| + | len[i]=fail[i]=cnt[i]=ps[i]=0,memset(ch[i],0,sizeof(ch[i])); | ||
| + | for(int i=2;i<=n;i++) | ||
| + | printf(" %d",ans[i]),ans[i]=0; | ||
| + | puts(""); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| </code></hidden> | </code></hidden> | ||
| ===== J.Just Skip The Problem ===== | ===== J.Just Skip The Problem ===== | ||
| 行 216: | 行 308: | ||
| ===== 训练总结 ===== | ===== 训练总结 ===== | ||
| - | wxg: | + | wxg: 网络流没有想出来模型，以后要多练练 |
| hxm:比较遗憾B最后差一点没写出 | hxm:比较遗憾B最后差一点没写出 | ||
2020-2021/teams/die_java/front_page_summertrain13.1598000686.txt.gz · 最后更改: 2020/08/21 17:04 由 wxg
