专项测试(字符串2)
所以这是Niuma题嘛？？
开场第一题没看懂题面，然后愣了一会
溜了一眼第二题，发现前两个都是子串问题，然后心态崩了，去看第三题
于是沉浸于小故事中，于是第三题也不会做，打了个背包就跑了
回来看第一题，看看\(OJ\)上的图片，明白了题意
然后仍旧不会做，就去看第二题了，然后切了第二题
此时剩下两个小时，只有\(110pts\)，虽然最后也只有这些分
第一题有思路，就开打了，测样例的时候发现根本对不上
然后我认为是样例错了，开玩了
临近结束\(15min\)的时候，发现第一题应该是子串而不是后缀，于是我假了，于是不想做了
T1 CF1063F
依旧是\(DP\)，枚举起点，有一大堆性质，然后保证了复杂度是\(\mathcal{O(nlogn)}\)
用反串建立后缀树，用线段树+\(DFS\)序维护子树最大值，因为一个点代表的串是它子树内的串的前缀
于是这个题做完了
然而卡常的\(OJ\)并不想让你就这样过了，于是你需要一个\(\mathcal{O(n\sqrt{n})}\)的高级做法
直接哈希判断是否相等，因为数据是随的，于是连\(log\)都跑不满，就过了
nlogn
#include<bits/stdc++.h>
using namespace std;
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
inline int read(){
int s=0,t=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
return s*t;
}
const int N=5e5+5;
int n,ans;
char a[N];
struct SAM{
struct POT{
int len,fail,son[27];
}tr[N*2];
int seg,las;
SAM(){seg=las=1;tr[0].len=-1;}
struct XDS{
#define ls x<<1
#define rs x<<1|1
int mx[N*8];
void pushup(int x){mx[x]=max(mx[ls],mx[rs]);}
void ins(int x,int l,int r,int pos,int v){
if(l==r)return mx[x]=v,void();
int mid=l+r>>1;
if(pos<=mid)ins(ls,l,mid,pos,v);
else ins(rs,mid+1,r,pos,v);
pushup(x);return ;
}
int query(int x,int l,int r,int ql,int qr){
if(ql>qr)return -1;
if(ql<=l&&r<=qr)return mx[x];
int mid=l+r>>1,ret=0;
if(ql<=mid)ret=max(ret,query(ls,l,mid,ql,qr));
if(qr>mid)ret=max(ret,query(rs,mid+1,r,ql,qr));
return ret;
}
#undef ls
#undef rs
}xds;
int whe[N];
void ins(int c,int id){
int p=las,np=++seg;
las=np;tr[np].len=tr[p].len+1;
while(p&&!tr[p].son[c])tr[p].son[c]=np,p=tr[p].fail;
if(!p)tr[np].fail=1;
else {
int q=tr[p].son[c];
if(tr[q].len==tr[p].len+1)tr[np].fail=q;
else {
int nq=++seg;
tr[nq]=tr[q];
tr[nq].len=tr[p].len+1;
tr[q].fail=tr[np].fail=nq;
while(p&&tr[p].son[c]==q)tr[p].son[c]=nq,p=tr[p].fail;
}
}
whe[id]=las;
}
int to[N*2],nxt[N*2],head[N*2],rp;
void add_edg(int x,int y){
to[++rp]=y;
nxt[rp]=head[x];
head[x]=rp;
}
int fa[N*2][21],dep[N*2],dfn[N*2],dfm[N*2],idf[N*2],cnt;
void dfs(int x){
dfn[x]=++cnt;idf[cnt]=x;
fo(i,1,20)fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
fa[y][0]=x;dep[y]=dep[x]+1;
dfs(y);
}
dfm[x]=cnt;
}
int find(int x,int len){
if(!x)return 0;
fu(i,20,0)if(tr[fa[x][i]].len>=len)x=fa[x][i];
return x;
}
int dp[N];
bool chk(int x){
int pos1=find(whe[x],dp[x]-1);
int pos2=find(whe[x-1],dp[x]-1);
if(pos1&&xds.query(1,1,seg,dfn[pos1],dfm[pos1])>=dp[x]-1)return true;
if(pos2&&xds.query(1,1,seg,dfn[pos2],dfm[pos2])>=dp[x]-1)return true;
return false;
}
void work(){
reverse(a+1,a+n+1);
fo(i,1,n)ins(a[i]-'a',i);
fo(i,2,seg)add_edg(tr[i].fail,i);
dfs(1);int cur=0;
fo(i,1,n){
dp[i]=dp[i-1]+1;
while(!chk(i)){
dp[i]--;cur++;
xds.ins(1,1,seg,dfn[whe[cur]],dp[cur]);
}
ans=max(ans,dp[i]);
}
printf("%d",ans);
}
}sam;
signed main(){
scanf("%s",a+1);
n=strlen(a+1);
sam.work();
return 0;
}
AC_code(n根号n)
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
inline int read(){
int s=0,t=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
return s*t;
}
const int N=5e5+5;
const ull bas=131;
ull hs[N],ba[N];
unordered_map<ull,bool> mp;
int sq,n;
char a[N];
int dp[N],ans;
bool query(int l,int len){
int r=l+len-1;
return mp.count(hs[r]-hs[l-1]*ba[len]);
}
signed main(){
scanf("%s",a+1);
n=strlen(a+1);ba[0]=1;
fo(i,1,n)hs[i]=hs[i-1]*bas+a[i]-'a'+1,ba[i]=ba[i-1]*bas;
mp[0]=1;int len=0;
fu(i,n,1){
len++;
while(!query(i,len-1)&&!query(i+1,len-1)){
len--;int r=i+len;
fu(j,dp[r],1){
if(mp.count(hs[r+j-1]-hs[r-1]*ba[j]))break;
mp[hs[r+j-1]-hs[r-1]*ba[j]]=1;
}
}
dp[i]=len;
ans=max(ans,dp[i]);
}
printf("%d",ans);
return 0;
}
T2 虚空恶魔
可以直接在后缀树上维护每个点的\(endpos\)的最小和最大值，直接统计答案
AC_code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
inline int read(){
int s=0,t=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
return s*t;
}
const int N=2e6+5;
int n;ll ans;
char a[N];
struct SAM{
struct POT{
int len,fail,son[26];
}tr[N*2];
int seg,las;
int mn[N*2],mx[N*2];
SAM(){
seg=las=1;
memset(mn,0x3f,sizeof(mn));
}
void ins(int c,int i){
int p=las,np=++seg;
las=np;tr[np].len=tr[p].len+1;
mn[np]=mx[np]=i;
while(p&&!tr[p].son[c])tr[p].son[c]=np,p=tr[p].fail;
if(!p)tr[np].fail=1;
else {
int q=tr[p].son[c];
if(tr[q].len==tr[p].len+1)tr[np].fail=q;
else {
int nq=++seg;
tr[nq]=tr[q];
tr[nq].len=tr[p].len+1;
tr[q].fail=tr[np].fail=nq;
while(p&&tr[p].son[c]==q)tr[p].son[c]=nq,p=tr[p].fail;
}
}
}
int buc[N*2],who[N*2];
void work(){
fo(i,1,n)ins(a[i]-'a',i);
fo(i,1,seg)buc[tr[i].len]++;
fo(i,1,n)buc[i]+=buc[i-1];
fu(i,seg,1)who[buc[tr[i].len]--]=i;
fu(i,seg,1){
int u=who[i],f=tr[u].fail;
mn[f]=min(mn[f],mn[u]);
mx[f]=max(mx[f],mx[u]);
if(mx[u]-mn[u]>=tr[u].len)ans=max(ans,1ll*tr[u].len*max(n-mn[u],mx[u]-tr[u].len));
else if(mx[u]-mn[u]>tr[f].len)ans=max(ans,1ll*(mx[u]-mn[u])*max(n-mn[u],mn[u]));
}
printf("%lld",ans);
}
}sam;
signed main(){
// cout<<(sizeof(sam)>>20)<<endl;
scanf("%s",a+1);
n=strlen(a+1);
sam.work();
return 0;
}
这题码真短！！！
T3 UOJ172
原题把多测删了
同余最短路，这个边数太大，于是过不了，然而我考场上连这个都没有想到(其实是我不会同余最短路)
但是我想到了\(border\)是由\(logn\)个等差数列组成的
然而不会用......
然后搞一堆单调队列啊啥的直接做就行了
AC_code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
inline int read(){
int s=0,t=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
return s*t;
}
const int inf=0x3f3f3f3f3f3f3f3f;
const int N=2e6+5;
int n,m,nxt[N],ans;
char a[N];
int sum[N],num;
int dis[N],ris[N];
int cir[N],c,len;
bool vis[N];
int sta[N],top,bot;
signed main(){
// cout<<(sizeof(dp)*5>>20)<<endl;
n=read();m=read();
scanf("%s",a+1);
for(int i=2,j=0;i<=n;i++){
while(j&&a[i]!=a[j+1])j=nxt[j];
if(a[i]==a[j+1])j++;
nxt[i]=j;
}
int now=n,cha=n;
sum[++num]=0;
while(now){
sum[++num]=n-nxt[now];
now=nxt[now];
}memset(dis,0x3f,sizeof(dis));dis[0]=0;
int lst,v=0,d=0;
fo(pp,1,num-1){
lst=v;d=sum[pp+1]-sum[pp];v=sum[pp+1];
if(pp!=1){
memcpy(ris,dis,sizeof(dis));memset(dis,0x3f,sizeof(dis));
fo(i,0,lst-1)if(ris[i]!=inf)dis[ris[i]%v]=min(dis[ris[i]%v],ris[i]);
}
memset(vis,false,sizeof(vis));len=2;
fo(i,0,v-1){
if(vis[i])continue;
int beg=i;now=i;
while((now+lst)%v!=i){
if(dis[now]<dis[beg])beg=now;
vis[now]=true;now=(now+lst)%v;
}vis[now]=true;
if(dis[now]<dis[beg])beg=now;
now=beg;c=0;
while((beg+lst)%v!=now)cir[++c]=beg,beg=(beg+lst)%v;
cir[++c]=beg;
top=0;bot=1;
fo(j,2,c)dis[cir[j]]=min(dis[cir[j]],dis[cir[j-1]]+lst);
}
len=0;
while(sum[pp+1]-sum[pp]==d)pp++,len++;pp--;
if(len==1)d=0;
memset(vis,false,sizeof(vis));
fo(i,0,v-1){
if(vis[i])continue;
int beg=i;now=i;
while((now+d)%v!=i){
if(dis[now]<dis[beg])beg=now;
vis[now]=true;now=(now+d)%v;
}vis[now]=true;
if(dis[now]<dis[beg])beg=now;
now=beg;c=0;
while((beg+d)%v!=now)cir[++c]=beg,beg=(beg+d)%v;
cir[++c]=beg;
top=0;bot=1;
fo(j,1,c){
while(bot<=top&&j-sta[bot]>=len)bot++;
if(bot<=top)dis[cir[j]]=min(dis[cir[j]],dis[cir[sta[bot]]]+v+d*(j-sta[bot]));
while(bot<=top&&dis[cir[sta[top]]]+d*(j-sta[top])>=dis[cir[j]])top--;
sta[++top]=j;
}
}
}
fo(i,0,v-1)if(dis[i]<m-n)ans+=(m-n-dis[i])/v+1;
printf("%lld",ans);
return 0;
}