题目大意
找到一个字符串中所有前半等于后半的字符串,如abab,按长度从短到长删除其左半部分,如果长度相等,则先删最左边的。
输出删除后剩余的字符串。
输入文件第一行包含整数 n,表示字符串的长度。 下面一行包含 n 个由空格隔开的在 0 到 10^9 范围内的数字,数字表示字符串中的字符。 数据保证每个字符在字符串中最多出现 10 次。
1<=n<=100000
显然我需要先找到所有符合条件的字符串,然后删除。
怎么判断一个字符串是否合法?
当然是哈希啦。
然后每个字符出现次数不超过10,我可以存下来,然后直接找。
找到每个合法字符的复杂度大概是O(n)的。
然后排个序,按顺序模拟就行了。
为什么我当时忘了每个字符出现次数不超过10的限制,给O(n^2)判了。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <iostream>
using namespace std;
typedef unsigned long long ull;
const int N=100005;
const int bas=107;
const int INF=1e9+7;
int k;
ull hs[N],base[N];
int s[N],ss[N],s1[N];int tot;
int n;
int ans[N],res;
int st[N][15];
inline void dis()
{
sort(ss+1,ss+1+n);
for(int i=1;i<=n;++i) if(i==1||ss[i]!=ss[i-1]) s1[++tot]=ss[i];
}
inline int f(int x){return lower_bound(s1+1,s1+1+tot,x)-s1;}
struct data
{
int l,r,len;
friend bool operator <(data x,data y)
{
if(x.len==y.len) return x.l<y.l;
return x.len<y.len;
}
}a[N];int cnt;
int main()
{
base[0]=1;
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&s[i]),ss[i]=s[i];
dis();
for(int i=1;i<=n;++i)
{
int val=f(s[i]);
st[val][0]++;st[val][st[val][0]]=i;
}
for(int i=1;i<=n;++i) base[i]=base[i-1]*bas;
for(int i=1;i<=n;++i) hs[i]=hs[i-1]*bas+s[i];
for(int i=1;i<=n;++i)
{
int val=f(s[i]);
for(int j=1;j<=st[val][0];++j)
{
int nxt=st[val][j];if(nxt<=i) continue;
int len=nxt-i-1;
ull x=hs[i+len]-hs[i-1]*base[len+1];
ull y=hs[nxt+len]-hs[nxt-1]*base[len+1];
if(x==y)
{
a[++cnt].l=i;a[cnt].r=nxt;a[cnt].len=nxt+len-i+1;
break;
}
}
}
sort(a+1,a+1+cnt);
int pos=0;
for(int i=1;i<=cnt;++i)
{
int l=a[i].l;
if(l<pos) continue;
pos=a[i].r;
}
printf("%d\n",n-pos+1);
for(int i=pos;i<=n;++i) printf("%d ",s[i]);
}
这是考试题啊,快醒醒
我这是懒的写了。