按位或

#include<iostream>
using namespace std;
int p[131072];
int mx = 131071;//二进制为17个1,题中范围内的数字,每位都是1
int q;
int main()
{
    /*对于每一次询问,我们肯定会选择所有y,满足y&x==y,即在二进制表达下,y是x的子集。
那么我们可以维护一个数组p[i],表示所有为i的子集的数字的Or值是多少。每次插入一个数字,如果它
没有重复出现过,就枚举它的超集更新答案。询问的时候只需要看p[x]是否等于x就好了。*/
    scanf("%d", &q);//几组数据
    while (q--)
    {
        int op, x; 
        scanf("%d%d", &op, &x);//op  1插入,2查询
        if (op == 1) 
        {
            if (p[x] == x) //此次插入数字已经存在,且插入0这里就终止了
                continue;
            int s = mx ^ x; //按位异或运算符,同0异1,相当于按位取反.
            for (int i = s; i; i = (i - 1) & s)//退出循环i==0.对插入的每一个数x,将二进制所有为1和x相同的记录
                p[i ^ x] |= x;
            p[x] = x;
        }
        else 
        {
            if (p[x] == x) 
                puts("YES");
            else 
                puts("NO");
        }
    }
    return 0;
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 17:28
25届每天都在焦虑找工作的事情0offer情绪一直很低落硬撑着面了一个岗位岗位有应酬的成分面试的时候hr给我出各种场景题问的问题比较犀利&nbsp;有点压力面的感觉感觉有点回答不上来本来就压抑的情绪瞬间爆发了呢一瞬间特别想哭觉得自己特别没用没绷住掉眼泪了事后想想觉得自己挺有病的&nbsp;真的破大防了
喜欢唱跳rap小刺猬...:我觉得没关系吧,之前有一次面试leader给我压力面,我顶住了压力,结果入职的时候发现组里氛围很差,果断跑路。其实从面试就能大概看出组的情况,面试体验好的组倒是不一定好,但是面试体验不好的组。。。就很难说
面试尴尬现场
点赞 评论 收藏
分享
07-02 13:52
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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