求调,马蜂良好
查看原帖
求调,马蜂良好
731213
I_KUN楼主2024/10/3 20:55

ps:之前做过这题,现在想用一个更简洁的代码

选用的是数学的做法,

yx=zyy-x=z-y可以推出x,zx,z奇偶性相同,所以可以进行按颜色和奇偶性进行分组;假设在一组中这些格子数为kk,内容分别是u1,u2,...,uku_1,u_2,...,u_k,在整个纸带上的编号分别是d1,d2,...,dkd_1,d_2,...,d_k则可以推出这一组的总分数为

(u1+u2)(d1+d2)+(u1+u3)(d1+d3)+...+(u1+uk)(d1+dk)+(u2+u3)(d2+d3)+(u2+u4)(d2+d4)+...+(u2+uk)(d2+dk)+...+(uk1+uk)(dk1+dk)=(u_1+u_2)(d_1+d_2)+(u_1+u_3)(d_1+d_3)+...+(u_1+u_k)(d_1+d_k)+\\(u_2+u_3)(d_2+d_3)+(u_2+u_4)(d_2+d_4)+...+(u_2+u_k)(d_2+d_k)+\\...+\\(u_{k-1}+u_k)(d_{k-1}+d_k)\\=\\ \color{red}u_1d_1+u_1d_2$$+$$\color{blue}u_2d_1+u_2d_2$$+$$\color{red}u_1d_1+u_1d_3$$+u_3d_1+u_3d_3+...+$$\color{red}u_1d_1+u_1d_k$$+$$\color{green}u_kd_1+u_kd_k$$+\\$$\color{blue}u_2d_2+u_2d_3$$+u_3d_2+u_3d_3+$$\color{blue}u_2d_2+u_2d_4$$+u_4d_2+u_4d_4+...+$$\color{blue}u_2d_2+u_2d_k$$+$$\color{green}u_kd_2+u_kd_k$$+\\...+\\u_{k-1}d_{k-1}+u_{k-1}d_k+$$\color{green}u_kd_{k-1}+u_kd_k$$\\=\\u_1(d_1+d_2+d_1+d_3+...+d_1+d_k)+\\u_2(d_2+d_1+d_2+d_3+...+d_2+d_k)+\\...+\\u_k(d_k+d_1+d_k+d_2+...+d_k+d_{k-1})\\=\\u_1(d_1(k-2)+d_1+d_2+...+d_k)+\\u_2(d_2(k-2)+d_1+d_2+...+d_k)+\\...+\\u_k(d_k(k-2)+d_1+d_2+...+d_k)

可以发现只需事先将每一组的d\sum dkk算好,再遍历numberinumber_i就可以算出答案,思路应该没错,不过为什么过不了qwq

#include<bits/stdc++.h>
using namespace std;
long long k[100005][2],sum_d[100005][2],c[100005],x[100005];
long long n,m,ans;
int main(){
	scanf("%lld%lld",&n,&m);
	for (int i=1;i<=n;i++)scanf("%lld",x+i);
	for (int i=1;i<=n;i++){
		scanf("%lld",c+i);
		k[c[i]][i%2]++;
		sum_d[c[i]][i%2]+=i;
	}
	for (int i=1;i<=n;i++)
		ans+=x[i]*(i*(k[c[i]][i%2]-2)%10007+sum_d[c[i]][i%2])%10007;
	printf ("%lld",ans);
	return 0;
}
2024/10/3 20:55
加载中...