codeforces1119C. Ramesses and Corner Inversion 构造_codeforces inverse 构造

广告位招租

给出一个矩阵A，你现在可以对这个矩阵进行操作：从A中选取一个子矩阵，将子矩阵的四个角的位置取反，求是否能从A通过这个操作转换到矩阵B。

因为遵循上述变换时，矩阵变换前后每一行和每一列‘1’个数的奇偶性不变，根据这个性质，我们可以先预判两矩阵奇偶性。
构造转换方案。对于每一个矩阵A中a_ij=1(i，j>1),选取矩阵(1,1,i,j)，按上述将a_ij置为0，在根据矩阵B考虑是否变为A。在这样操作之后，矩阵中只有第一行与第一列不同。
对于某一列c，假设这一列中，k_A和k_B为矩阵A和矩阵B中这一列中‘1’的个数，在根据上述方法变换后，无论A_1c为何值，

1. 仅当A_1c=B_1c时
   这一位上被翻转的次数都为偶数，如果k_A和k_B同奇偶，则k_A+k_B为偶，k_A-1+k_B-1为偶。
2. 仅当A_1c!=B_1c时
   k_A-1+k_B为奇数，所以按上述操作完成后，这两位也将相同

故我们只需要判断每一行与每一列‘1’个数的奇偶性即可

最后，卡罗尔我吹爆！！！

#include <stdio.h>
#include <climits>
#include <cstring>
#include <time.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <vector>
#include <string>

#define INF 0x3f3f3f3f
#define ll long long
#define Pair pair<int,int>
#define re return

#define getLen(name,index) name[index].size()
#define mem(a,b) memset(a,b,sizeof(a))
#define Make(a,b) make_pair(a,b)
#define Push(num) push_back(num)
#define rep(index,star,finish) for(register int index=star;index<finish;index++)
#define drep(index,finish,star) for(register int index=finish;index>=star;index--)
using namespace std;

int N,M;
int A[512][512],B[512][512];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n1=0,n2=0;
    cin>>N>>M;
    rep(i,0,N)
        rep(j,0,M){
            cin>>A[i][j];
            if(A[i][j])
                n1++;
        }
    rep(i,0,N)
        rep(j,0,M){
            cin>>B[i][j];
            if(B[i][j])
                n2++;
        }

    if(n1%2 != n2%2){
        cout<<"No\n";
    }else{
        bool safe=true;
        int stc1=0,stc2=0;
        //statistics row
        rep(i,0,N){
            stc1=0,stc2=0;
            rep(j,0,M){
                if(A[i][j])
                    stc1++;
                if(B[i][j])
                    stc2++;
            }
            if(stc1%2 != stc2%2){
                safe=false;
                break;
            }
        }
        if(!safe){
            cout<<"No\n";
            re 0;
        }

        //statistics in column
        rep(i,0,M){
            stc1=0,stc2=0;
            rep(j,0,N){
                if(A[j][i])
                    stc1++;
                if(B[j][i])
                    stc2++;
            }
            if(stc1%2 != stc2%2){
                safe=false;
                break;
            }
        }
        if(safe){
            cout<<"Yes\n";
        }else
            cout<<"No\n";
    }

    re 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96