海关网站建设方案,wordpress专业,红安县建设局网站,可以下载新闻视频的网站解析
做出来了就是胜利#xff01;
个人感觉虽然我这个nxt树的码量会大一点#xff0c;但是思路其实比较自然。#xff08;看题解区也有#xff09; 也是一个相当可取的做法。
现在来讲讲巧妙的dp做法。 考虑直接嗯设#xff1a;fif_ifi 表示覆盖 [1,i][1,i ][1,i] 的…解析
做出来了就是胜利
个人感觉虽然我这个nxt树的码量会大一点但是思路其实比较自然。看题解区也有 也是一个相当可取的做法。
现在来讲讲巧妙的dp做法。 考虑直接嗯设fif_ifi 表示覆盖 [1,i][1,i ][1,i] 的最小印章。
一个比较显然的结论是fif_ifi 要么是一个border要么是前缀 i 本身。 当作本身显然是一个极其备胎的选择关键就是找到是否有可以替代的最短border。
注意到fnxtif_{nxt_i}fnxti 已经可以覆盖 [1,nxti][1,nxt_i][1,nxti]那么它只要也可以覆盖后面的部分那么就可以直接令 fi←fnxtif_i\gets f_{nxt_i}fi←fnxti。 而对于小于 fnxtif_{nxt_i}fnxti 的border根据定义其连 [1,nxti][1,nxt_i][1,nxti] 都无法覆盖所以必然是非法的。 对于大于 fnxtif_{nxt_i}fnxti 的border假设其合法那么注意到 fnxtif_{nxt_i}fnxti 必然也可以印出这个border那么它就可以“仿印”出大 border 的效果fnxtif_{nxt_i}fnxti 必然也是合法的。所以较大的border即使合法也必然不会成为最优答案。
所以只需要考虑 fnxtif_{nxt_i}fnxti 是否可以赋值给 fif_ifi 就行了。 可以开桶简单维护。 然而懒得写还是贴的自己nxt树的做法。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned ll
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
inline ll read() {ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-) f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}const int N5e5100;
const int mod998244353;inline ll ksm(ll x,ll k){ll res(1);while(k){if(k1) resres*x%mod;xx*x%mod;k1;}return res;
}int n,m,q;char s[N];
int p[N];
void kmp(char *s,int n){p[1]0;for(int i1,j0;in;i){while(js[j1]!s[i1]) jp[j];if(s[j1]s[i1]) j;p[i1]j;}return;
}
int a[N],num,tag[N];
vectorinte[N],v[N];
int fa[N],vis[N],siz[N],cur;
int find(int x){return fa[x]x?x:fa[x]find(fa[x]);
}
inline void merge(int x,int y){xfind(x);yfind(y);if(siz[x]siz[y]) swap(x,y);fa[x]y;siz[y]siz[x];return;
}
void dfs(int x,int rt){v[rt].push_back(x);tag[x]1;for(int to:e[x]){if(tag[to]) continue;dfs(to,rt);}return;
}
inline void ins(int x){vis[x]1;if(vis[x-1]) merge(x-1,x);if(vis[x1]) merge(x1,x);curmax(cur,siz[find(x)]);
}signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifscanf(%s,s1);nstrlen(s1);kmp(s,n);for(int xn;x;xp[x]){tag[x]1;a[num]x;}for(int i1;in;i){e[p[i]].push_back(i);fa[i]i;siz[i]1;}reverse(a1,a1num);//printf(%s\n,s1);for(int i1;inum;i) dfs(a[i],a[i]);for(int i1;in;i){if(!tag[i]) ins(i);}for(int i1;inum;i){int xa[i];if(xcur){printf(%d\n,x);return 0;} for(int o:v[x]) ins(o); }return 0;
}
/**/
