P9583 涂色 题解

· · 题解

大致题意

给定一个 n 行 m 列的矩阵，初始时矩阵所有格子均无色。

有 q 次操作，每次操作给出两个数 op 和 x，若 op 为 1，则第 x 行所有格子被涂一层色；若 op 为 2，则第 x 列所有格子被涂一层色。每个格子涂色后将涂色的层数对 k 取模。

求出 q 次操作后，最终有几个格子有色。

思路/解析

题目要求求出最终的有色方格数量，那我们不妨先求出无色方格数量，设无色方格数量为 tot，则最终的有色方格数量即为 n\times m-tot。

用两个数组 l 和 r 记录每行、每列被涂色的次数，枚举行的涂色次数 x 和列的涂色次数 y，只要满足 (x+y)\bmod k=0，就将 cnt 加上 y\bmod k即可。最终输出 n\times m-tot。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+10;
ll n,m,q,k,i,op,x,ans,l[N],r[N],f[N];
int main(){
    cin>>n>>m>>q>>k;
    while(q--){
        cin>>op>>x;
        if(op==2)l[x]++;
        else r[x]++;
    }
    for(i=1;i<=m;i++)f[l[i]%k]++;
    f[k]=f[0];
    for(i=1;i<=n;i++)ans+=f[k-r[i]%k];
    cout<<n*m-ans;
}