【势能分析】BZOJ2321 [BeiJing2011集训]星器

题面在这里

​

发现无论怎么操作，最后的答案都是一样的

考虑如何计算答案

定义一颗星\((x,y)\)具有势能\(x^2+y^2\)

假设对\((x,y)\)和\((x,z)\)两颗星使用魔法，有： \[ E=2x^2+y^2+z^2 \\ E'=2x^2+(y+1)^2+(z-1)^2 \\ E-E'=2(z-y-1) \] 而\((z-y-1)\)就是这次产生的魔力

所以初始势能-末态势能除以二就是答案了

​

示例程序：

#include<cstdio>
typedef long long ll;

int n,m; ll E1=0,E2=0;
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	 for (int j=1;j<=m;j++){
	 	int x;scanf("%d",&x);
	 	E1+=x*(i*i+j*j);
	 }
	for (int i=1;i<=n;i++)
	 for (int j=1;j<=m;j++){
	 	int x;scanf("%d",&x);
	 	E2+=x*(i*i+j*j);
	 }
	printf("%lld",(E1-E2)/2);
	return 0;
}