题解：P11543 [Code+#5] 二分图判定

思路

要判断是否可以通过行翻转和列翻转将矩阵 \mathbf{A} 转换为矩阵 \mathbf{B}，我们可用异或（XOR）实现。即：

1. 首先计算矩阵 \mathbf{A} 和 \mathbf{B} 的差异矩阵 \mathbf{D}，其中 \mathbf{D}[i][j]=\mathbf{A}[i][j]\oplus\mathbf{B}[i][j]。

2. 假设第一行不进行翻转（即 r[0]=0），然后根据差异矩阵确定每一列是否需要翻转。

3. 对于每一行，计算翻转状态 r[i]，并检查所有列的翻转状态是否一致。如果不一致，则尝试另一种初始假设（即 r[0]=1）。

   代码

   #include <bits/stdc++.h>
   #define ll long long
   using namespace std;
   int main(){
   ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
   int n,m;
   cin>>n>>m;
   vector<vector<int>> A(n,vector<int>(m)),B(n, vector<int>(m));
   for(auto &row:A){
       for(auto &x:row){
           cin>>x;
       }
   }
   for(auto &row:B){
       for(auto &x:row){
           cin >> x;
       }
   }
   vector<vector<int>> D(n, vector<int>(m, 0));
   for(int i=0;i<n;i++){
       for(int j=0;j<m;j++){
           D[i][j] = A[i][j] ^ B[i][j];
       }
   }
   for(int r0=0;r0<=1;r0++){
       vector<int> c(m, 0);
       for(int j=0;j<m;j++){
           c[j]=D[0][j]^r0;
       }
       bool ok=1;
       vector<int> r(n, 0);
       r[0]=r0;
       for(int i=1;i<n;i++){
           r[i] = D[i][0]^c[0];
           for(int j=1;j<m;j++) {
               if((D[i][j]^c[j]) != r[i] ){
                   ok=0;
                   break;
               }
           }
           if(!ok) break;
       }
       if(ok){
           cout<<"Koyi";
           return 0;
       }
   }
   cout<<"Budexing";
   }