P9583 涂色 题解

Paris_Commune · 2023-08-27 09:46:32 · 题解

前言

被 hack 了，更改了数组大小。

赛时忘了 k 的倍数也会变成空白，事实上也写得不对。

正解

用 h_i，l_i 存第 i 行或列被涂了几次。

如果涂了 i 层，则涂了 i\bmod k 行。

再用 v_i 表示有多少个涂了 i 层的行。

AC 代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,q,k,l[500005],h[500005],v[500005],ans;
signed main(){
//  freopen("paint2.in","r",stdin);
    cin>>n>>m>>q>>k;
    for(int i=1;i<=q;i++){
        int op,x;
        cin>>op>>x;
        if(op==1){
            h[x]++;
        }
        else l[x]++;
    }
    for(int i=1;i<=n;i++){
        v[h[i]%k]++;
    }
    for(int i=1;i<=m;i++){
        if(l[i]%k==0)ans+=n-v[0];
        else ans+=n-v[k-l[i]%k];
    }
    cout<<ans;
    return 0;
}