AT2068题解

Withers · 2022-05-02 12:09:52 · 题解

题目传送门

题目大意

就是一个 N 行 W 列的矩形，每次输入一个格子，把它染色，变成黑色。然后要求的是所有九宫格里不同黑格子数量个数，简而言之就要求有 0,1,2\dots9 个黑格子的个数

思路

我们正常的想法肯定是开数组模拟，但一看数据范围，H,W 都到了 10^9 肯定会 MLE 和 TLE，那怎么办呢

这时候就要想到贡献法，就是每输入一个格子，计算它对包含它的九宫格的贡献（记得判边界）

所以我们只需维护一个答案数组，每次计算新格子对它的影响就行了

但是，又有个新问题：如何记录新加进来的格子所在的九宫格原来黑格子的个数呢？

显然我们可以用 map 来解决，用它来维护以 x,y 为中心的九宫格黑格子个数

完结撒花！

代码

#include<bits/stdc++.h>
using namespace std;
long long  ans[10];
typedef pair<int,int> pii;//用pair来维护二元组 
map<pii,int> mp;
int main()
{
    long long h,w;
    int n;
    cin>>h>>w>>n;
    ans[0]=(h-2)*(w-2);//初始化，一开始一个黑格子都没有 
    for(int i=1;i<=n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        for(int j=-1;j<=1;j++)
        {
            for(int k=-1;k<=1;k++)//遍历计算影响 
            {
                int x=a+j,y=b+k;//九宫格的中心 
                if(x>1&&x<h&&y>1&&y<w)//判断边界 
                {
                    int now;//now表示现在这个九宫格的黑格子的数量 
                    now=++mp[{x,y}];
                    ans[now]++,ans[now-1]--;
                }
            }
        }
    }
    for(int i=0;i<10;i++) cout<<ans[i]<<endl;
}