[BZOJ 2321][BeiJing2011集训]星器
转载请注明出处：http://danihao123.is-programmer.com/
物理题可还行（其实我是想学势能方法，然后误入了……）
给每个星星（假设他在的位置是\((i, j)\)）定义势能\(E_p = i^2 + j^2\)，定义势函数\(\Phi(S)\)来表示状态\(S\)时所有星星势能的和。
然后我们发现，当两个星星互相吸引时（假设他们同行，坐标分别为\((i, j)\)和\((i, k)\)，且$j<k$），他们的坐标会变为\((i, j + 1)\)和\((i, k - 1)\)，势能的总减少量（也就是势函数的减小量）为\(2(k - j - 1)\)。
因此，整个过程中势函数的总减小量，就是答案的两倍。因此算出操作前后的势能做差即可……
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
typedef long long ll;
int main() {
int n, m; scanf("%d%d", &n, &m);
ll E = 0LL;
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++) {
ll delta = i * i + j * j; ll x;
scanf("%lld", &x); delta *= x;
E += delta;
}
}
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++) {
ll delta = i * i + j * j; ll x;
scanf("%lld", &x); delta *= x;
E -= delta;
}
}
E /= 2LL;
printf("%lld\n", E);
return 0;
}
评论 (0)
