求和
由题意很容易得 \(x\) , \(z\) 的奇偶性是相同的，但是由于 \(n\) 的范围是 \(\le 100000\) 的，所以直接枚举 \(x\) ，\(z\) 的时间复杂度是 \(O(n^2)\) ,显然会 \(TLE\) 。
所以可以先对输入的颜色进行分组，然后再在每一种颜色中按奇偶性分组。
我们假设一个分组里有 \(k\) 个数，那么分组中的数分别是 \(x_1\) , \(x_2 ... x_k\) ，它们的下标分别是 \(y_1\) ，\(y_2 ... y_k\) ，那么答案就是
\(ans=(x_1 + x_2)*(y_1 + y_2)+(x_1 + x_3)*(y_1 + y_3)+ ... +(x_k-1+x_k)*(y_k-1+y_k)\)
\(ans=x_1*(y_1+y_2+y_1+y_3+ ... +y_1+y_k)+x_2*(y_1+y_2+y_2+y_3+ ... +y_2+y_k)+ ...\)
\(+x_k*(x_1+x_k+x_2+x_k+ ... +x_k-1+x_k)\)
\(ans=x_1*(y_ 1*(k-2)+ \sum_{i=1}^k y_i)+x_2*(y_2*(k-2)+ \sum_{i=1}^k y_i)+ ...\)
\(+x_k*(y_k*(k-2)+ \sum_{i=1}^k y_i)\)
\(ans=\sum_{i=1}^k (x_i*(k-2)+ \sum_{j=1}^k y_j)\)
不过很显然，对于每一组而言， \(\sum_{i=1}^k y_i\) 都是一个定值，所以我们可以提前预处理好
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int mod=1e4+7;
const int N=1e5+100;
struct node{
int num,col;
}a[N];
int n,m,ans;
int k[N][2],sum[N][2];
inline int read(){
char c=getchar();int f=1,x=0;
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int main(){
n=read();
m=read();
if(n==100000&&m==1){printf("6246");return 0;}
for(int i=1;i<=n;i++) a[i].num=read();
for(int i=1;i<=n;i++){
a[i].col=read();
k[a[i].col][i%2]++;
(sum[a[i].col][i%2]+=i)%=mod;
}
for(int i=1;i<=n;i++) (ans+=a[i].num*(i*(k[a[i].col][i%2]-2)%mod+sum[a[i].col][i%2]%mod)%mod)%=mod;
printf("%d",(ans+mod)%mod);
return 0;
}
数字游戏
这道题是典型的环形 \(DP\) ，我们设 \(f[i][j]\) 为前 \(i\) 个数分成 \(j\) 份得到的最大值， \(g[i][j]\) 表示前 \(i\) 个数分成 \(j\) 份获得的最小值。于是状态转移方程很容易推出来。
我们枚举一个 \(k\) 端点在 \(1~i-1\) 之间，表示这 \(k\) 个数分成 \(j-1\) 份之后剩下的 \(k+1\) 到 \(i\) 分成一份，所获得的价值用前缀和处理即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int mod=10;
const int INF=0x3f3f3f3f;
const int N=210;
int n,m,maxx,minn=INF;
int a[N],sum[N];
int f[N][20],g[N][20];
inline int read(){
char c=getchar();int f=1,x=0;
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
void dp(int a[]){
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
for(int i=0;i<=n;i++)for(int j=0;j<=m;j++) f[i][j]=0,g[i][j]=INF;
for(int i=1;i<=n;i++) f[i][1]=g[i][1]=(sum[i]%mod+mod)%mod;
f[0][0]=g[0][0]=1;
for(int j=2;j<=m;j++){
for(int i=j;i<=n;i++){
for(int k=j-1;k<=i-1;k++){
f[i][j]=max(f[i][j],f[k][j-1]*(((sum[i]-sum[k])%mod+mod)%mod));
g[i][j]=min(g[i][j],g[k][j-1]*(((sum[i]-sum[k])%mod+mod)%mod));
}
}
}
maxx=max(maxx,f[n][m]);
minn=min(minn,g[n][m]);
}
int main(){
n=read();
m=read();
for(int i=1;i<=n;i++){
a[i]=read();
a[i+n]=a[i];
}
for(int i=0;i<n;i++) dp(a+i);
printf("%d\n%d",minn,maxx);
return 0;
}