安大校赛/异或运算一题。

该题怒跪,原因:1,对异或运算还不太本质理解;2,异或优先级低于“!=”,“==”都不知道!!。

题意:给一个矩阵,c[i][j]=(a[i]^b[j]),矩阵给定,求a[i],b[j],(a[i]的字典序最小),无解则输出。

先了解下异或吧:

性质

1、交换律

2、结合律(即(a^b)^c == a^(b^c))

3、对于任何数x,都有x^x=0,x^0=x

4、自反性 A XOR B XOR B = A xor  0 = A。

异或本质是不进位的加法,各位不影响。而且1,0本质是一样的,(代号而已, 即将表达式全部的1换成0,全部的0换为1xor运算到结果不变)。

这题,令,a[0]=0,由c[][]求出所有a[],b[],判断,无解则必无解;

证明:假设 a[0]=11100001(随便一个非0的),若其有解,对应把各位全换成0,(其他对应变换),由1,0的等价性和各位独立性,知,a[0]=00000000也必有解,矛盾,故不成立!

其实,该题还可以用2-sat求解。

ps:切记!!异或优先级啊!

#include<iostream>
#include<cstdio>
using namespace std;
int a[1130][1130];
int aa[1130];
int bb[1130];
int main()
{
    int t,i,j;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        for(i=0;i<n;i++)
            aa[i]=0;
        for(j=0;j<m;j++)
            bb[j]=0;
        for(i=0;i<n;i++)
            for(j=0;j<m;j++)
             scanf("%d",&a[i][j]);
         int mark=0;
          for(j=0;j<m;j++)  //得到b[]
             bb[j]=a[0][j];
        for(i=0;i<n;i++)
            aa[i]=bb[0]^a[i][0];  //得到a【】
         for(i=0;i<n;i++)
         {
             if(mark)break;
             for(j=0;j<m;j++)
             {
                 if((aa[i]^bb[j])!=a[i][j])   //怒跪于此!,异或运算优先级低于“==”,"!="!!
                 {
                     mark=1;
                     break;
                 }
             }
             if(mark)break;
         }
         if(mark==0)
         {
              for(i=0;i<n;i++)
              {
                 if(i!=n-1)cout<<aa[i]<<" ";
                 else cout<<aa[i]<<endl;
              }
               for(i=0;i<m;i++)
              {
                 if(i!=m-1)cout<<bb[i]<<" ";
                 else cout<<bb[i]<<endl;
              }
         }
        else
            cout<<"I bet Tyrion made a mistake."<<endl;
     }
     return 0;
}






原文地址:https://www.cnblogs.com/yezekun/p/3925736.html