2020-2021:teams:die_java:front_page_summertrain4
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:die_java:front_page_summertrain4 [2020/07/24 23:33] wxg [H.Harder Gcd Problem] |
2020-2021:teams:die_java:front_page_summertrain4 [2020/07/24 23:40] (当前版本) wxg [训练总结] |
||
|---|---|---|---|
| 行 243: | 行 243: | ||
| === 题意 === | === 题意 === | ||
| + | 给了一个函数。让一段字符串每一位变成前面最大的字母。问连续调用两次函数后不同字串个数。 | ||
| === 题解 === | === 题解 === | ||
| + | |||
| + | 调用一次后发现字符串一定变成递增的串，所以再次调用只要本质不同的字符串一定不同，题目变成了求 f(s,i,n)的所有本质不同的字串。 | ||
| + | 而这些串的 trie 的大小不会超过 10n ，直接暴力建出后缀自动机统计不同字串。 | ||
| <hidden 代码> | <hidden 代码> | ||
| <code cpp> | <code cpp> | ||
| + | #include<iostream> | ||
| + | #include<cstdio> | ||
| + | #include<algorithm> | ||
| + | #include<cstring> | ||
| + | #include<stack> | ||
| + | #define ll long long | ||
| + | using namespace std; | ||
| + | int read() | ||
| + | { | ||
| + | int k=0,f=1;char c=getchar(); | ||
| + | for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; | ||
| + | for(;isdigit(c);c=getchar()) k=k*10+c-'0';return k*f; | ||
| + | } | ||
| + | const int N=2000055; | ||
| + | int n,m,ch[N][26],a[N],c[N],pos[N]; | ||
| + | int last,tot,link[N],len[N],size[N]; | ||
| + | char s[N]; | ||
| + | void init() | ||
| + | { | ||
| + | last=tot=0;len[0]=0;link[0]=-1; | ||
| + | } | ||
| + | void extend(int c) | ||
| + | { | ||
| + | int cur=++tot,p=last;len[cur]=len[last]+1;size[cur]=1; | ||
| + | for(;p!=-1&&!ch[p][c];p=link[p]) ch[p][c]=cur; | ||
| + | if(p==-1) link[cur]=0; | ||
| + | else | ||
| + | { | ||
| + | int q=ch[p][c]; | ||
| + | if(len[p]+1==len[q]) link[cur]=q; | ||
| + | else | ||
| + | { | ||
| + | int clone=++tot; | ||
| + | len[clone]=len[p]+1; | ||
| + | link[clone]=link[q]; | ||
| + | memcpy(ch[clone],ch[q],sizeof(ch[q])); | ||
| + | for(;p!=-1&&ch[p][c]==q;p=link[p]) | ||
| + | ch[p][c]=clone; | ||
| + | link[q]=clone;link[cur]=clone; | ||
| + | } | ||
| + | } | ||
| + | last=cur; | ||
| + | } | ||
| + | stack<int> st; | ||
| + | int main() | ||
| + | { | ||
| + | scanf("%s",s); | ||
| + | n=strlen(s); | ||
| + | init(); | ||
| + | pos[n]=0; | ||
| + | for(int i=n-1;i>=0;i--) | ||
| + | { | ||
| + | while(!st.empty()&&s[st.top()]<s[i]) st.pop(); | ||
| + | int k; | ||
| + | if(st.empty()) k=n; | ||
| + | else k=st.top(); | ||
| + | last=pos[k]; | ||
| + | for(int j=i;j<k;j++) | ||
| + | extend(s[i]-'a'); | ||
| + | pos[i]=last; | ||
| + | st.push(i); | ||
| + | } | ||
| + | ll ans=0; | ||
| + | for(int i=1;i<=tot;i++) | ||
| + | ans+=len[i]-len[link[i]]; | ||
| + | printf("%lld\n",ans); | ||
| + | return 0; | ||
| + | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
| 行 455: | 行 525: | ||
| =====训练总结===== | =====训练总结===== | ||
| wxg: | wxg: | ||
| + | 本场有点拖大，虽然写出了H题，写加想快用了两个小时，后面又强行卡常A的错误做法，造成了成绩惨淡。 | ||
| hxm: | hxm: | ||
| fyh:本场我发挥得跟**一样，签到F题就脑子抽了耽误了一些时间，以后应该多打cf，保证第一题的又快又对。然后在wxg和hxm讨论H的时候我觉得没有参与讨论的意义了就没有参与，又耽误了一些时间，把大部分时间耽误在想一道不可做的J题上，之后和王兴罡讨论D，一道不难的题基本上已经想到做法了却在讨论后给否定了。目前想到的改进措施是把当时脑子里的想法以及注意的细节尽可能写在纸上，脑子有时候可能转不动。 | fyh:本场我发挥得跟**一样，签到F题就脑子抽了耽误了一些时间，以后应该多打cf，保证第一题的又快又对。然后在wxg和hxm讨论H的时候我觉得没有参与讨论的意义了就没有参与，又耽误了一些时间，把大部分时间耽误在想一道不可做的J题上，之后和王兴罡讨论D，一道不难的题基本上已经想到做法了却在讨论后给否定了。目前想到的改进措施是把当时脑子里的想法以及注意的细节尽可能写在纸上，脑子有时候可能转不动。 | ||
2020-2021/teams/die_java/front_page_summertrain4.1595604822.txt.gz · 最后更改: 2020/07/24 23:33 由 wxg
