牛客练习赛 B异或图（位运算 异或）附 异或运算性质

题目

思路：

来自大佬 与大佬交流后来写
1 对于某个异或图中的一条边，边两点的权值a^ b肯定等于k,那么输入的时候如果判断得a[x]^a[y] = k,则直接输出1
2 如果a[x]^a[y]!=k, 如果这条边不存在于这个异或图中。
3 接下来再判断这两个点是否在异或图中，通过中间点连接
4了解一个性质a^ b = c 则 b^ c = a, 则c^a = b
5 只有当a[x] = a[y] 并且k^a[x] = a[i] 时才有可能x到y有路径。否则输出-1

6 不可能存在距离在2以上的路径，证明如下（读者可以任意举一个例子证明）
假设有这样的异或图

则2^ x = x^ y ,所以2 ^ x ^x = x ^ y ^x，所以2=y。同理可证x和y都是2，则这个异或图的k值为0。则任意两个2中间都有边。
即

AC代码：

#include <iostream>

using namespace std;
const int maxn = 1e7+7;
int a[maxn];
int v[maxn];
int main()
{
   
    int n,q;
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++)
    {
   
        scanf("%d",&a[i]);
        //printf("%d ",a[i]);
        v[a[i]]++;
    }
    while(q--)
    {
   
        int k,x,y;
        scanf("%d %d %d",&k,&x,&y);
        if((a[x]^a[y])==k)
        {
   
            printf("1\n");
        }
        else
        {
   
            if(a[x]==a[y]&&v[k^a[x]])
            {
   
                printf("2\n");
            }
            else
            {
   
                 printf("-1\n");
            }
        }
    }
    return 0;
}

异或性质：

1异或：我们是不是不一样，不同为1，相同为0
参考另一位大佬博客