P1861 星之器

linfourxu · 2021-06-26 11:55:38 · 题解

容易发现，答案只与初态末态有关且唯一，那么考虑设一个势能函数使得每移动一次，势能的减少量等于答案的增加量。值得注意的是，这种思想在“鞅的停时问题”中也非常常用。

考虑设 f(x,y) 表示位于 (x,y) 的一颗“星”的势能，容易发现势能是每颗星的势能的加和，且 x 维度上的势能与 y 维度上的势能相互独立且等价。这些也是“鞅的停时问题”中设势能函数相当常用也相当容易发现的结论。

那么就可以化简势能函数为 f(x) 表示某一维上位于 x 位置的一颗"星"的势能，根据变化不难列出 f(x_1)+f(x_2)-f(x_1+1)-f(x_2-1)=x2-x1-1 其中 x1<x2，该式子含义即为”驱动“位于 x_1 的一颗星与位于 x_2 的一颗星。

简单移项可得 f(x_1+1)-f(x_1)-(x_1+1)=f(x_2)-f(x_2-1)-x2 所以我们设的势能函数只需要满足 f(x)-f(x-1)-x 为定值即可，不妨令这个定值与 f(0) 都为 0，当然你令这两个值为多少都行。

那么不难得到 f(x) 的通项为 \frac{x^2+x}{2}，当然这个通项与你 f(0) 和定值的取值有关。

那么这题中每颗星总的势能即可表示为 \frac{x^2+y^2+x+y}{2}，答案即为初态的总势能减去末态的总势能。

rint n=read<int>(),m=read<int>();rll ans=0;
for(rint i=1;i<=n;i++)
    for(rint j=1;j<=m;j++)
        ans+=read<int>()*(i*(i+1)/2+j*(j+1)/2);
for(rint i=1;i<=n;i++)
    for(rint j=1;j<=m;j++)
        ans-=read<int>()*(i*(i+1)/2+j*(j+1)/2);
printf("%lld\n",ans);