codeforces1151B题解(异或的性质)

蔚落 2022-02-14 15:13 220阅读 0赞

输入n行，m列。从每一行取一个值，使他们的异或和>0，输出TAK和n个满足条件的每一行的列数，如果不能构成，输出NIE。

/*
     * Created by hao on 2019/4/19.
     * 输入n行，m列。从每一行取一个值，使他们的异或和>0。
     * 输出TAK和n个满足条件的每一行的列数，如果不能构成，输出NIE。
     * 异或的一些性质
     * 0^0=0,0^1=1,1^0=1,1^1=0
     * 相同取0，相异取1
     * 输入A取0,则输出p=输入B
     * 输入A取1,则输出p=输入B的反
     */
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <iostream>
    #include <algorithm>
    #include <set>
    #include <vector>
    using namespace std;
    #define ll long long
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
        int h, w;
        cin >> h >> w;
        int a[505][505];
        int cur = 0;
    
        //读入数据，cur对每一行第一个异或(^)
        for (int i = 0; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                cin >> a[i][j];
            }
            cur ^= a[i][0];
        }
        //定义初始值，去判断是否有符合条件的存在。
        int px = -1, py = -1;
        for (int i = 0; i < h && px == -1; ++i) {
            for (int j = 0; j < w; ++j) {
                //让当前值和每一行的第一个进行异或，如果满足和>0即可跳出，记录行数和列数，方便输出
                int nxt = cur ^ a[i][0] ^ a[i][j];
                if (nxt > 0) {
                    px = i, py = j+1;
                    break;
                }
            }
        }
        //根据前面的判断分情况输出
        if (px >= 0 && py >= 0) {
            cout << "TAK" << endl;
            for (int i = 0; i < h; ++i) {
                if (i) cout << ' ';
                cout << (i == px ? py : 1);
            }
            cout << endl;
        }
        else {
            cout << "NIE" << endl;
        }
        return 0;
    }