事情为什么会发展成这样.jpg
题目链接 一开始感觉是求最短不包含重复段的后缀 卡了好久qwq 后来发现forfor就完事了 本来想写sa hash 暴力三种写法的 结果写完暴力发现比sa还快 瞬间索然无味 我写sa干嘛呢 离散化一下然后枚举就行 就当复习sa了555
后缀数组
248 ms 25400 KB
代码语言：javascript复制#include<bits/stdc .h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5 5;
int s[maxn];
int sa[maxn],rk[maxn];
int height[maxn];
int t1[maxn],t2[maxn],c[maxn];
int best[20][maxn];
int a[maxn],b[maxn];
vector<int>vv[maxn];
void getsa(int *s,int n,int m){
int *x=t1,*y=t2;
rep(i,0,m) c[i]=0;
rep(i,0,n) c[x[i]=s[i]] ;
rep(i,1,m) c[i] =c[i-1];
dep(i,n-1,0) sa[--c[x[i]]]=i;
for(int k=1;k<=n;k<<=1){
int p=0;
rep(i,n-k,n) y[p ]=i;
rep(i,0,n) if(sa[i]>=k) y[p ]=sa[i]-k;
rep(i,0,m) c[i]=0;
rep(i,0,n) c[x[y[i]]] ;
rep(i,1,m) c[i] =c[i-1];
dep(i,n-1,0) sa[--c[x[y[i]]]]=y[i];
swap(x,y);
p=1; x[sa[0]]=0;
rep(i,1,n) x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1] k]==y[sa[i] k]?p-1:p ;
if(p>=n) break; m=p;
}
}
void getheight(int n){
int k=0;
rep(i,1,n 1) rk[sa[i]]=i;
rep(i,0,n){
if(k) k--;
int j=sa[rk[i]-1];
while(s[i k]==s[j k]) k ;
height[rk[i]]=k;
}
}
void RMQ(int n){
int lg=(int)(log(n*1.0)/log(2.0));
rep(i,1,n 1) best[0][i]=height[i];
rep(i,1,lg 1) for(int j=1;j (1<<i)-1<=n;j )
best[i][j]=min(best[i-1][j],best[i-1][j (1<<i>>1)]);
}
int lcp(int x,int y){
x=rk[x]; y=rk[y];
if(x>y) swap(x,y); x ;
int lg=(int)(log(1.0*(y-x 1))/log(2.0));
return min(best[lg][x],best[lg][y-(1<<lg) 1]);
} // 贴板子
struct node{ int l,r,len; }p[maxn*10]; // 十倍是因为题目的"保证重复不过十次"
int cmp(node a,node b){ return a.len<b.len||a.len==b.len&&a.l<b.l; } // 按题意sort
int solve(){
int n,cnt(0),ans(0); sc(n); rep(i,0,n) sc(a[i]),b[i]=a[i];
sort(b,b n); int bn=unique(b,b n)-b; rep(i,0,n){
s[i]=lower_bound(b,b bn,a[i])-b 1;
vv[s[i]].push_back(i);
} getsa(s,n 1,maxn); getheight(n); RMQ(n);
rep(i,0,maxn) rep(j,0,vv[i].size()) rep(k,j 1,vv[i].size()){
if(vv[i][k]-vv[i][j]>n-vv[i][k]) continue;
if(vv[i][k]-vv[i][j]<=lcp(vv[i][j],vv[i][k]))
p[cnt ]={vv[i][j],vv[i][k],vv[i][k]-vv[i][j]};
// 只要算一下这一段是不是重复的就可以 改成hash也差不多
} sort(p,p cnt,cmp); rep(i,0,cnt) if(p[i].l>=ans) ans=p[i].r;
pf("%dn",n-ans); rep(i,ans,n) pf("%d ",a[i]); return 0;
}
int main(){
/* int _; sc(_); while(_--) */ solve();
}暴力
186 ms 5000 KB 思路差不多的 不过算是优化了一下qwq
代码语言：javascript复制#include<bits/stdc .h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5 5;
map<int,int>aaa;
vector<int>vv[maxn];
int a[maxn],q[maxn];
int solve(){
int n,cnt(0),ans(0); sc(n); rep(i,0,n){
sc(a[i]); if(!aaa.count(a[i])) aaa[a[i]]= cnt;
q[i]=aaa[a[i]]; vv[aaa[a[i]]].push_back(i);
} rep(i,0,n) for(auto x:vv[q[i]]){
if(x>=i) break; if(i-x>n-i||x<ans) continue;
int ff(0); rep(j,0,i-x) if(a[i j]!=a[x j]){ ff ; break; }
if(!ff){ ans=i; break; }
} pf("%dn",n-ans); rep(i,ans,n) pf("%d ",a[i]);
}
int main(){
/* int _; sc(_); while(_--) */ solve();
}upd:ylh把我暴力卡了 更没意思了 数据:
代码语言：javascript复制#include<bits/stdc .h>
#define rep(i,s,e) for(int i=s; i<e; i)
using namespace std;
int main(){
cout<<100000<<'n';
rep(i,0,10) rep(j,0,10000) cout<<(j==9999?10001 i:j 1)<<'n';
}
