1012 重复序列

题目要求字符串重复次数最多的后缀。标算据说是kmp但是我一点都不会，就只好用字符串哈希水了一下。直接算出哈希暴力条k次比较是否重复，由于长度是增长的，所以复杂度最差也就O(n(logn))，而且多个重复字符串的情况很少发生，所以实际时间应该远小于最差时间。

1013 挖掘机

题目要求对序列进行多次区间修改后求方差，主要时间费在修改上。因此这是一道典型的区间修改求单点值的题，但因为没有动态询问所以不需要数据结构维护，使用O(n)时间即可解决。一次序列的区间减去k相当于是将差分后的序列头部-k尾部+k，所以等差分序列所有操作完成后再加起来就是最终的数列。

建议用此题练习一下线段树，出了问题对拍比较方便。

[cc lang=”cpp” escaped=”true” line_numbers=”on”]

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int a[100005],f[100005];

int main()
{
int n;
while (cin>>n)
{
for (int i=0;i<n;i++) cin>>a[i];
int m; cin>>m;
memset(f,0,sizeof(f));
for (int i=0;i<m;i++)
{
int l,r,k;
cin>>l>>r>>k;
f[l]-=k;
f[r]+=k;
}
int s=0;
double sum=0;ll avg=0,var=0;
for (int i=0;i<n;i++)
{
s+=f[i];
a[i]+=s;
sum+=a[i];
}
sum/=n;
avg=(sum>=0?(ll)sum:-(ll)(-sum));
for (int i=0;i<n;i++)
var+=(avg-a[i])*(avg-a[i]);
cout<<var<<‘\n’;
}
return 0;
}

[/cc]