BZOJ 2321: [BeiJing2011集训]星器 神仙题

title

BZOJ 2321

LUOGU 1861

Description

analysis

• 答案与移动方式无关，只与初态，终态有关。

• 。因为移动的方式比较复杂，所以考虑用别的方法来计算。

  • 观察两个在同一列的星 \((x_1,y),(x_2,y)(x_1<x_2)\) 靠近时，获得的魔力为$ x_2-x_1$ ，想办法给星一个 "势能" ，使得它们靠近时产生的魔力等于势能的减小量（神仙思路）；

  • 一颗星 \((x,y)\) 的势能为 \(\frac{x^2+y^2}{2}\) 。

  • 然后用上面的情况试一下：

  • \[\begin{array}{lcl}E_0=\frac{x_1^2+y_1^2+x_2^2+y_2^2}{2}\\E_1=\frac{(x_1+1)^2+y_1^2+(x_2-1)^2+y_2^2}{2}\\\Delta E=x_2-x_1\end{array}\]

  • 就证明了按 \(x^2+y^2\) 定势能满足 靠近时产生的魔力等于势能的减小量 。

  • 最后的答案为 初态总势能减去终态总势能 ，所以此题完结（无奈，逃。

code

#include<bits/stdc++.h>

#define file(s) freopen(s".in","r",stdin), freopen(s".out","w",stdout)

#define G ch=getchar()
#define DeBug(x) std::cout<<#x<<':'<<x<<std::endl

typedef long long ll;

namespace IO
{
    char buf[1<<15],*fs,*ft;
    inline char getc() { return (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs))?0:*fs++; }
    template<typename T>inline void read(T &x)
    {
        x=0;
        T f=1, G;
        while (!isdigit(ch) && ch^'-') G;
        if (ch=='-') f=-1, G;
        while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), G;
        x*=f;
    }

    char Out[1<<24],*fe=Out;
    inline void flush() { fwrite(Out,1,fe-Out,stdout); fe=Out; }
    template<typename T>inline void write(T x,char str)
    {
        if (!x) *fe++=48;
        if (x<0) *fe++='-', x=-x;
        T num=0, ch[20];
        while (x) ch[++num]=x%10+48, x/=10;
        while (num) *fe++=ch[num--];
        *fe++=str;
    }
}

using IO::read;
using IO::write;

int main()
{
    int n, m;
    read(n), read(m);
    ll sum1=0, sum2=0;
    for (int i=1; i<=n; ++i)
        for (int j=1, x; j<=m; ++j) read(x), sum1+=(i*i+j*j)*x;
    for (int i=1; i<=n; ++i)
        for (int j=1, x; j<=m; ++j) read(x), sum2+=(i*i+j*j)*x;
    write((sum1-sum2)>>1,'\n');
    IO::flush();
    return 0;
}