题解 - 找子序列（2024.12上海月赛丙组T4）

题目描述

Dave 有一个长度为 n 的非负整数序列 a1-n, 和一个非负整数 m 。
他希望知道是否有一个 a 的非空子序列，使得子序列中所有元素的按位与(bitwise AND)结果为 m。
换言之，他想知道是否存在一个下标序列 i1-k(k ≥ 1),满足 1 ≤ i1 < i2 < ··· < ik ≤ n，且 ai1 & ai2 & … & ak =m。
输入格式
第一行一个整数 T， 表示数据组数。对于每组数据:
第一行两个整数 n,m。
第二行 n 个非负整数 a1~n。
输出格式
对于每组数据，如果存在这样的非空子序列，输出一行Yes，否则输出一行 No。
数据范围
对于 30% 的数据，1 ≤ ∑n ≤ 20，0 ≤ ai,m < 32。
对于 60% 的数据，1≤∑n≤ 1000 , 0≤ ai,m <2^10
对于 100% 的数据，1<T<105,1≤∑n≤5x100000,0≤ai,m< 2^30

样例数据
输入:
4
5 6
0 0 0 2 2
5 21
29 29 29 29 31
5 11
27 27 31 27 27
5 9
13 15 27 11 27
输出:
No
No
No
Yes
说明:
在第四组数据中，整个序列即为所求子序列。

分析

考虑 & 运算的性质，1&0=0，0&0=0，所以我们考虑每一位的答案，如果m的第i位为1，那么k个数的第i位必须都是1，因此可以先通过这个条件筛选掉一批数。
假设m共有x位0，那么再在符合条件的数中，看能否找出x个数来分别对应m的每一位0即可。

代码

#include<bits/stdc++.h>using namespace std;const int N = 5e5 + 10;int n,m;
int a[N][40],b[40];
bool st[40];
int cnt1;void init(){for(int i = 1;i <= n;i++)for(int j = 0;j < 40;j++)a[i][j] = 0;for(int j = 0;j < 40;j++) b[j] = st[j] = 0;cnt1 = 0;
}void solve(){cin >> n >> m;for(int i = 1,k;i <= n;i++){cin >> k;for(int j = 0;k;j++){a[i][j] = k % 2;k /= 2;}}for(int i = 0;m;i++){b[i] = m % 2;m /= 2;if(b[i]) st[i] = true,cnt1++;} set<int> tmp;for(int i = 1;i <= n;i++){bool flag1 = true;for(int j = 0;j < 30;j++)if(st[j] && !a[i][j]){flag1 = false;break;}if(!flag1) continue;bool flag2 = true;for(int j = 0;j < 30;j++)if(!st[j] && !a[i][j])tmp.insert(j);}if(cnt1 + (int)tmp.size() == 30) cout << "Yes\n";else cout << "No\n";init();
}int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t;cin >> t;while(t--){solve();}return 0;
}