首页 > 代码库 > codeforces 165E - Compatible Numbers 【位运算】

codeforces 165E - Compatible Numbers 【位运算】

题目: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 【位运算】