P9583题解

· · 个人记录

45pts 做法

很简单，只需要暴力遍历每一个格子就好了

时间复杂度为O(nm+q)

特殊性质A

只需要扫描每一个横行

如果横行的操作数 \mod k=0

那么这一行都没有涂上颜色

由于只用扫描横行 所以时间复杂度为O(n+q)

特殊性质B还没想到怎么不用正解的方法做

100pts 做法

题目要求的是统计涂上颜色的格子的个数，并不是问在哪里

又因为，每一个横行和每一个数列都有且仅有1个交点

每一个格子的颜色是这样的：

gezi[i][j]=(heng[i]+shu[j])%k

那我们只需要知道哪一个横行的操作数和哪一个数列的操作数和为k的倍数即可

因此，我们可以用桶去装每一个横行的操作数，这样我们就省去了遍历m条边的时间

时间复杂度为O(n+p) 可以通过此题 code：

#include<bits/stdc++.h>
using namespace std;
long long hang[200005]/*记录对横行的操作*/,shu[200005]/*记录对竖列的操作*/,n,m,q,k,op,x,ans,tona[500005];
int main() {
    cin>>n>>m>>q>>k;
    ans=n*m;//假设它们全都被涂上颜色了 
    for(int i=1; i<=q; i++) {
        scanf("%d%d",&op,&x);
        if(op==1) hang[x]=(hang[x]+1)%k;//记录横行 
        else shu[x]=(shu[x]+1)%k;//记录竖列
    }
    for(int i=1; i<=n; i++) {
        tona[hang[i]]++;
    }
    /*
    因为每一个横行和每一个竖行都有一个交点 
    so,我们用一个桶去记录操作的次数
    毕竟我们不需要知道是哪个格子没有颜色
    然后，我们再次遍历一次每个竖列，求出这个数列上没有颜色的格子的个数
    用ans去减去这个数 
    */ 
    for(int i=1;i<=m;i++){
        int xz=k-shu[i];//算出使其中的格子变成没有颜色的对应横行的涂色次数 
        if(shu[i]==0) xz=0;//其实这行可以替换为xz%=k; 
        ans-=tona[xz];//ans减去这个竖列上没有颜色的格子的个数 
    }
    cout<<ans;
    return 0;
}

轻松AC！！！