P9583 涂色题解

· · 题解

题目大意

原本所有方格都是空白的，每次涂色给一行或一列的所有方格都添加 1 层颜色，每次涂色结束后，把所有被涂上 k 层颜色的方格的颜色都擦掉，让这些方格都变成空白的。问最终共有多少方格被涂上了颜色。

思路

首先我们可以想到一种办法：二维差分。但是当我们看 n 和 m 的范围时我们会发现如果开二维数组会爆，所以我们可以开两个一维数组 h 和 s 来分别储存行和列被涂过的次数。

但开两个一维数组似乎只能使用暴力，因为我们需要求出每个方格被涂过的次数然后看看能否整除 k，这样还会超时。

是否能在此想法上优化？当然可以。我们可以用 c 来保存如需把放个方格变成空白的 h_i \bmod k 的值，而 c=c-(s_i \bmod k) \bmod k，所以我们可以使用循环来计算满足 h_i \bmod k = c 的数量，而一段满足条件的 h_i 可以使用二分查找数量，使用二分前要将 h 从小到大排序，该部分代码如下（其中 ans 的初始值为 n \times m，让 ans 减去空白方格的数量就可以得出最终答案）：

for(int i=1;i<=m;i++)
{
    c=s[i]%k;
    for(int j=(k-c)%k;j<=h[n];j+=k)//每次加k优化
    {
        ans=ans-(find_right(j)-find_left(j)+1);
            //find_right(j)-find_left(j)+1是符合要求的数量
    }
}

当我们使用这种方法去写时，运行第四个样例时我们会发现它超时了。我们把超时的原因锁定在二分上，新的问题出现了：如何优化二分？

我们可以想想我们使用二分是用来干什么的？对，是求 h_i = c 数量，所以我们可以使用数组计数进行优化。优化后的部分代码如下：

for(int i=1;i<=m;i++)
{
    c=s[i]%k;
    for(int j=(k-c)%k;j<=h[n];j+=k)
    {
        ans=ans-ss[j];//ss[j]是符合要求的数量
    }
}

完整 AC 代码如下：

#include<bits/stdc++.h>
using namespace std;
long long n,m,nm,k,as,x,h[200010],s[200010],ans=0,c,ss[500010];
int main()
{
    cin>>n>>m>>nm>>k;
    ss[0]=n;//初始化，开始时每个格子都没涂，所以没涂的行数有n 
    for(int i=1;i<=nm;i++)
    {
        cin>>as>>x;
        if(as==1) 
        {
            h[x]++;
            ss[h[x]-1]--;//涂过h[x]-1次的行数减1 
            ss[h[x]]++;//涂过h[x]次的行数加1 
        } 
        else s[x]++;
    }
    sort(h+1,h+n+1);//从小到大排序 
    ans=n*m;//答案初始化 
    for(int i=1;i<=m;i++)
    {
        c=s[i]%k;
        for(int j=(k-c)%k;j<=h[n];j+=k)
        {
            ans=ans-ss[j];
        }
    }//该部分解释同上推理过程 
    cout<<ans;//输出结果 

    return 0;
}

注意事项

使用 int 会爆，所以请使用 long long。