Codeforces 19C. Deletion of Repeats

事情为什么会发展成这样.jpg

题目链接
一开始感觉是求最短不包含重复段的后缀 卡了好久qwq 后来发现forfor就完事了
本来想写sa hash 暴力三种写法的 结果写完暴力发现比sa还快 瞬间索然无味 我写sa干嘛呢
离散化一下然后枚举就行 就当复习sa了555

后缀数组

248 ms 25400 KB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#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("%d\n",n-ans); rep(i,ans,n) pf("%d ",a[i]); return 0;
}
int main(){
/* int _; sc(_); while(_--) */ solve();
}

暴力

186 ms 5000 KB
思路差不多的 不过算是优化了一下qwq

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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("%d\n",n-ans); rep(i,ans,n) pf("%d ",a[i]);
}
int main(){
/* int _; sc(_); while(_--) */ solve();
}

upd:ylh把我暴力卡了 更没意思了
数据:

1
2
3
4
5
6
7
#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';
}