牛客练习赛 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
参考另一位大佬博客

全部评论

相关推荐

05-09 12:23
已编辑
华南理工大学 Java
野猪不是猪🐗:给他装的,双九+有实习的能看的上这种厂我直接吃⑨✌们拿它练练面试愣是给他整出幻觉了
点赞 评论 收藏
分享
迟缓的斜杠青年巴比Q了:简历被投过的公司卖出去了,我前两天遇到过更离谱的,打电话来问我有没有意向报班学Java学习,服了,还拿我学校一个学长在他们那报班学了之后干了华为OD当招牌
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务