CodeForces - 1151B thinking

The question

There is one n That's ok m Columns of the matrix , Ask if you can take a number from each line , bring n The number exclusive or is not followed by 0

Record

4 A month ago, I did it with pure violence , Never , The reason is that at that time, there was no deep connection on the court .

Let's look at this topic again today , The previous violence did not optimize duplicate numbers , Try to optimize the violence at this point .

Although from the perspective of XOR , No available , But found 4 A continuous number exclusive or is followed by 0.（ from 0 From the beginning ）

Look at the online solutions , It's really wonderful , This is a thinking problem .

Positive solution

< One > thinking

If the values of the first column are exclusive or and >1, Direct full input 1 that will do , If it is equal to 0, We just need to find the first element in any row that is not equal to this row , Because other numbers are exclusive or the first number in this line is 0, Then the other number XOR, which is not equal to the first number, must be greater than 1.

There are many codes for this solution on the Internet , Don't stick .

< Two > violence

After de duplication , Search directly .

#include "cstdio"
#include "iostream"
using namespace std;
const int N=509;
const int M=509;
int use[N][N];
int have[N][M];
int num[N];
int ans[N];

int dfs(int ceng,int val)
{
    if(ceng==0)return val;
    for(int i=1;i<=num[ceng];++i)
    {
        if( dfs(ceng-1,val^have[ceng][i]))
        {
           ans[ceng]=have[ceng][i];
            return 1;
        }
    }
    return 0;
}
int main()
{
//    freopen("in.text","r",stdin);
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i)
        for(int d=1,a;d<=m;++d)
        {
            scanf("%d",&a);
            if(use[i][a]==0)
            {
                use[i][a]=d;
                have[i][++num[i]]=a;
            }
        }
    int suc=0;

    if(dfs(n,0)) {
        printf("TAK\n");
        for (int i = 1; i <= n; ++i) {
            printf("%d ", use[i][ans[i]]);
//            printf("%d\n",ans[i]);
        }
    }
    else printf("NIE\n");
    return 0;
}