Nowcoder练习赛26 D xor序列

2018-09-07 21:46:01


题意:给定序列a,多次询问x,y,问x与序列中的任意个数异或后能否变成y

提到异或,首先想到的就是线性基

把序列中的数插入线性基中

每次询问的时候就看 $(x xor y)$ 和线性基中可异或的数异或后是否为0

如果为0则YES,否则为NO

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=35;
int n;
ll a[N];
inline void insert(int x)
{
    for (int i=30;~i;i--)
      if (x&(1<<i))
        if (!a[i]) {a[i]=x; return;}
        else x^=a[i];
}
inline bool check(int x)
{
    for (int i=30;~i;i--)
      if (x&(1<<i)) x^=a[i];
    return x==0;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        int x; scanf("%d",&x); insert(x);
    }
    int m; scanf("%d",&m);
    while (m--)
    {
        int x,y; scanf("%d%d",&x,&y);
        if (check(x^y)) puts("YES");
        else puts("NO");
    }
    return 0;
}