codeforces 165E - Compatible Numbers 【位运算】

港控/mmm° 2022-08-13 02:58 18阅读 0赞

题目：[codeforces 165E - Compatible Numbers][]

题意：给出n个数，然后每个数对应输出一个当前数组中与 Ai 与运算为 0 的数，没有的话输出-1

分析：简单的位运算题目，技巧性题目

首先，我们知道与运算的性质，就是只有同时为 1的时候才是1，那么假如 x&y=0 ,就是至少 x 的为1的为 y 全为0，其他为自由，假设为 1 ，那么 y = x^（(1<<22)-1）。但是这样并不是全部的，这些位还可能是0，所以我们可以枚举这些位，然后处理。

具体看代码：

#include <cstdio>
    #include <cstring>
    #include <string>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <map>
    #include <queue>
    #define Del(a,b) memset(a,b,sizeof(a))
    using namespace std;
    const long long inf = 0x3f3f3f3f;
    const long long N = 1000100;
    const int M = 23;
    int a[N],dp[1<<23];
    int main()
    {
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            dp[a[i]^((1<<M)-1)] = a[i];
        }
        for(int st = (1<<M)-1; st>=0 ;st--)
        {
            if(!dp[st])
            {
                for(int i=0;i<M;i++)
                {
                    if(dp[st|(1<<i)])  //枚举变化其他位
                        dp[st]=dp[st|(1<<i)];
                }
            }
        }
        for(int i=0;i<n;i++)
        {
            if(dp[a[i]])
                printf("%d",dp[a[i]]);
            else
                printf("-1");
            printf("%c",i==(n-1)?'\n':' ');
        }
        return 0;
    }

[codeforces 165E - Compatible Numbers]: http://codeforces.com/problemset/problem/165/E