P9023 题解

zhuweiqi · 2023-02-06 08:15:47 · 题解

首先我们一看这个比较奇怪的数据范围，二维数组是肯定开不了的，那么我们就需要用两个一维数组来存储一下每行每列的反转情况了，由于同一行或者同一列被反转了偶数次之后等于没反转，所以我们就用 r_i=1 来表示第 i 行被反转了，用 c_j=1 来表示第 j 列被反转了，等 k 次反转结束之后，我们设当前坐标为 a_{i,j}：如果 r_i=0 并且 c_j=0，就说明第 i 行第 j 列都没有被真正的反转，所以 a_{i,j}=0；同理，如果 r_i=1 并且 c_j=1，就说明第 i 行第 j 列都被反转了，那么 a_{i,j} 就被反转了两次，反转了偶数次之后等于没反转，所以 a_{i,j}=0；另外，如果第 i 行和第 j 列中有且只有一个被反转了，那么 a_{i,j} 就被反转了一次，所以 a_{i,j}=1，最终得出结论：如果 r_i \neq c_j，a_{i,j}=1，我们只需要一个双重循环判断就可以了，上代码！

#include<bits/stdc++.h>
using namespace std;
int r[5000005],c[5000005];
int main(){
    std::ios::sync_with_stdio(0);
    int n,m,k,ans=0;
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++){
        char d;int x;
        cin>>d>>x;
        if(d=='R') r[x]=!r[x];
        else c[x]=!c[x];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(r[i]!=c[j]) ans++;
        }
    }
    cout<<ans;
    return 0;
}