[BZOJ 2321][BeiJing2011集训]星器

danihao123 posted @ 2018年5月28日 21:21 in 题解 with tags BZOJ 势能方法 , 485 阅读
转载请注明出处: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;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter