题解 P1861 【星之器】

Vidoliga · 2020-12-19 21:37:32 · 题解

这真是一到水死了的题

废话不多说→_→，我们来康康吧

这题暴力枚举是不可能的，那该怎么办呢(⊙o⊙)！

我们需要找到一开始的“星”与结束时候的“星”的关系，我们需要考虑到一个权值能把开始的“星”到结束的“星”的将得到的魔力值算出来。 而关键是怎么找到这种权值！！

我们仔细观察，不难发现 每克“星”的权值为\frac{x × x + y × y}{2}

这是怎么证明的呢？

设某2克开始时的“星”的坐标为 (x1,y1) 和 (x2,y1),2克结束时的“星” 的坐标为(x3,y1)和(x4,y1) 同x轴或y轴都一样，我们考虑同y轴 我们可以得出总共增加了(x1-x2)+ ......+(x3-x4) = (x1-x2+x3-x4) × \frac{x1-x3+1}{2}

而这个权值（开始的“星”的权值减结束的“星”的权值）： 经检验可得 两式相等

代码:

#include<iostream>
using namespace std;
int n,m;
long long all;
long long h;
int main(){
    cin>>n>>m;
    int s,x = 0;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cin>>s;
            all += (i * i + j * j) * s;
        }
    }
    all = all / 2;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cin>>s;
            h += (i * i + j * j) * s;
        }
    }
    h = h / 2;
    cout<<all - h; 
    return 0; 
}