题解 CF1151B 【Dima and a Bad XOR】

· · 题解

这题还是有一些难度的，不过要了解异或的性质也就好说了。

审题

题目要求我们每一行选出一个数，异或和“严格大于零”，其实就是大于零。因为全部是正数，所以只能是等于零或者大于零。

随机方法

一看，大于零的数（此处有1023个）远远比零的个数多（只有一个啊），那就随机选取，极大概率选出的数异或后非零。

因为数据总会有NIE的，那就多随机几次，怎么随机都不行的那就不行。（除非你脸真的太黑）

正确，有保证的方法

要想异或得到的数大于零，其实只要二进制下任意一位数字不是0就行。

那么我们每次都把矩阵扫描一遍，统计他的最后一位，并且除以二（向右位移）

对于每一行，我们都统计最后一位数字是1的数字的个数，如果为0（叫做A类）或m（叫做B类），那这一行相当于没得选择，默认选第一个。

如果只有上述两种，且B类有奇数个，就可以得出一个方案并输出。否则下一次循环（所有数字都变成0才能结束，不要冲动）。

当然还有这一行最后一位数字是1的个数大于0小于m的情况（叫做C类），这样就有自主选择的机会，一定有解了。其他所有行默认选第一个，这一行根据选择得到1的个数调配奇偶即可。

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n,m,a[N][N],b[N][N],tj[N];
bool check(){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i][j])return true;
    return false;
}
void shuchu(int x){
    int cnt=0;
    int ans[N];
    for(int i=1;i<=n;i++)
        if(i!=x){
            if(b[i][1]&1)cnt++;
            ans[i]=1;
        }
    if(cnt&1){
        for(int i=1;i<=m;i++){
            if((b[x][i]&1)==0){
                ans[x]=i;
                break;
            }
        }
    }
    else{
        for(int i=1;i<=m;i++)
            if(b[x][i]&1){
                ans[x]=i;
                break;
            }
    }
    printf("TAK\n");
    for(int i=1;i<=n;i++)printf("%d ",ans[i]);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
            b[i][j]=a[i][j];
        }
    while(check()){
        for(int i=1;i<=n;i++)tj[i]=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                tj[i]+=a[i][j]&1;
                a[i][j]>>=1;
            }
        }
        int cnt=0;
        for(int i=1;i<=n;i++){
            if(tj[i]>0&&tj[i]<m){
                shuchu(i);
                return 0;
            }
            else if(tj[i]==m)cnt++;
        }
        if(cnt%2==1){
            printf("TAK\n");
            for(int i=1;i<=n;i++)printf("1 ");
            return 0;
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)b[i][j]>>=1;
    }
    printf("NIE\n");
    return 0;
}