T1
看到最大值最小，考虑二分答案。接下来考虑如何构造 \(b\) 数组。因为 \(b\) 数组单调不减，所以当前的 \(b\) 越小，对后面的影响越小。所以构造时尽量小地构造 \(b\) ，如果无法构造，说明当前的二分值不合法；如果构造成功，说明合法。
\(code:\)
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
ll n,sa,sb,sc,sd,a[5000005],f[5000005],sum[5000005],maxn,minn,mod;
ll fun(ll x){
return (sa*x%mod*x%mod*x%mod+sb*x%mod*x%mod+sc*x%mod+sd)%mod;
}
int main(){
freopen("Bell.in","r",stdin);
freopen("Bell.out","w",stdout);
scanf("%lld%lld%lld%lld%lld%lld%lld",&n,&sa,&sb,&sc,&sd,&a[1],&mod);
sum[1]=maxn=minn=a[1];
for(int i=2;i<=n;++i){
a[i]=(fun(a[i-1])+fun(a[i-2]))%mod;
maxn=max(maxn,a[i]);
minn=min(minn,a[i]);
sum[i]=(sum[i-1]+a[i])%mod;
}
ll l=minn,r=maxn,mid;
while(l<r){
mid=(l+r)>>1;
f[1]=a[1]-mid;
bool ok=1;int pos;
for(int i=2;i<=n;++i){
f[i]=f[i-1];
if(a[i]-f[i]>mid){
f[i]=a[i]-mid;
}
else if(f[i]-a[i]>mid){
ok=0;pos=i;break;
}
}
if(ok)
r=mid;
else
l=mid+1;
}
printf("%lld\n",r);
fclose(stdin);fclose(stdout);
return 0;
}
T2
首先开一个桶，对于当前的 \(a[i]\) ，令\(t[a[i]]++\)。然后发现，如果\(t\)数组以 \(a[i]\) 为中心是回文的，那么对于任意一对满足 \(a[i]-a[j]=a[k]-a[i]\) 的 \(j\)，\(k\) 都一定满足\(j<k<i\)或者\(i<j<k<=n\)，即一定不满足题意。
如何判断是否回文？只需要开一个值域树状数组，然后哈希处理即可。
\(code:\)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#define ll long long
using namespace std;
const ll mod=1e9+7;
ll n,a[500005],pos[500005],h[500005],c[500005][2];
void add(ll x,ll w,ll id){
while(x<=n)
c[x][id]=(c[x][id]+w)%mod,x+=x&(-x);
}
ll ask(ll x,ll id){
ll re=0;
while(x)
re=(re+c[x][id])%mod,x-=x&(-x);
return re;
}
int main(){
//freopen("Odd.in","r",stdin);
//freopen("Odd.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;++i)
scanf("%lld",&a[i]);
h[0]=1;
for(int i=1;i<=n;++i)
h[i]=h[i-1]*233%mod;
for(int i=1;i<=n;++i){
ll len=min(a[i],n-a[i]+1);
ll w1=(ask(a[i],0)-ask(a[i]-len,0)+mod)%mod;
ll w2=(ask(a[i]+len-1,1)-ask(a[i]-1,1)+mod)%mod;
add(a[i],h[a[i]],0);add(a[i],h[n-a[i]+1],1);
if(w1*h[n-a[i]-len+2]%mod!=w2*h[a[i]-len+1]%mod){
printf("YES\n");return 0;
}
}
printf("NO\n");
fclose(stdin);fclose(stdout);
}
T3
较为简单的斜率优化DP （虽然说我在考场上也没写出来吧）
首先推柿子：（假设平均数为\(mid\)）
\(v\times m^2=(\sum_{i=1}^m(x_i-mid)^2/m\times m^2\)
\(=(\sum_{i=1}^m(x_i^2+mid^2-2x_i\times mid))/m\times m^2\)
\(=(\sum_{i=1}^mx_i^2+m\times mid^2-2\times m\times mid\times mid)/m\times m^2\)
\(=(\sum_{i=1}^mx_i^2-m\times mid^2)/m\times m^2\)
\(=\sum_{i=1}^mx_i^2\times m^2-(\sum_{i=1}^mx_i)^2\)
所以只需要将原序列分成 \(m\) 段，求出每段的和的平方即可。
设\(f[i][j]\)表示前 \(i\) 个数，分成 \(j\) 段，所有段的和的平方的最小值。
\(f[i][j]=f[k][j-1]+(sum[i]-sum[k])^2(1<k<i)\)
然后斜率优化就\(OK\)了
\(code:\)
#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,ans,f[3005][3005],a[5005],sum[3005],sum2,r[3005],l[3005];int q[3005][3005];
long long dy(long long a,long long b,long long j){
return f[q[a][j]][j]+sum[q[a][j]]*sum[q[a][j]]-f[q[b][j]][j]-sum[q[b][j]]*sum[q[b][j]];
}
long long dx(long long a,long long b,long long j){
return sum[q[a][j]]-sum[q[b][j]];
}
long long dy2(long long i,long long b,long long j){
return f[i][j]+sum[i]*sum[i]-f[q[b][j]][j]-sum[q[b][j]]*sum[q[b][j]];
}
long long dx2(long long i,long long b,long long j){
return sum[i]-sum[q[b][j]];
}
void work2(){
for(int i=1;i<=n;++i)
for(int j=0;j<=m;++j)
f[i][j]=1e18;
f[0][0]=0;
for(int i=1;i<=m;++i)
q[l[i]=r[i]=1][0]=0;
for(int j=1;j<=m;++j)
for(int i=j;i<=n;++i){
while(l[j-1]<r[j-1]&&(dy(l[j-1]+1,l[j-1],j-1)<=2*sum[i]*dx(l[j-1]+1,l[j-1],j-1)))
++l[j-1];
f[i][j]=f[q[l[j-1]][j-1]][j-1]+(sum[i]-sum[q[l[j-1]][j-1]])*(sum[i]-sum[q[l[j-1]][j-1]]);
while(l[j]<r[j]&&dy(r[j],r[j]-1,j)*dx2(i,r[j],j)>=dy2(i,r[j],j)*dx(r[j],r[j]-1,j))
--r[j];
q[++r[j]][j]=i;
}
ans=m*f[n][m]-sum[n]*sum[n];
}
int main(){
//freopen("journey.in","r",stdin);
//freopen("journey.out","w",stdout);
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
sum[i]=sum[i-1]+a[i];
sum2+=a[i]*a[i];
}
work2();
printf("%lld\n",ans);
fclose(stdin);fclose(stdout);
return 0;
}