上海计算机学会2024年12月月赛C++丙组T4找子序列
发布时间
阅读量：
阅读量
找子序列
内存限制: 256 Mb时间限制: 1000 ms
题目描述
Dave 有一个长度为 n 的非负整数序列 a1∼n 和一个非负整数 m。
他关心是否存在一个 a 的非空子序列 s（s ≠ ∅），使得 s 中所有元素进行按位与运算的结果等于 m？
换言之，他想知道是否存在一个下标序列 i1∼k（k≥1），满足 1≤i1<i2<⋯<ik≤n，且 ai1&ai2&⋯&aik=m。
输入格式
第一行一个整数 T 表示数据组数。对于每组数据：
第一行两个整数 n,m。
第二行 n 个非负整数 a1∼n。
输出格式
在每一组数据中, 如果包含这样的非空子序列, 则返回Yes; 否则返回No.
数据范围
对于 30% 的数据，1≤∑n≤20，0≤ai,m<32。
对于 60% 的数据，1≤∑n≤103，0≤ai,m<210。
对于 100% 的数据，1≤T≤105，1≤∑n≤5×105，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，则对应的m中的该位必定是1；而那些在二进制中是0的位置，在数值m中也必定是0。
所有满足x & m = m的整数x，在经过一次按位与操作后若结果仍为m，则其中必定存在至少一个非空子序列使得该子序列的所有元素进行按位与运算后的结果仍为m。
详见代码：
#include<bits/stdc++.h>
using namespace std;
int t, m, n;
int a[500005];
int main() {
cin >> t;
while(t--) {
cin >> n >> m;
int k = 0xffffffff;
for(int i = 1; i <= n; i++) {
cin >> a[i];
if ((a[i]&m) == m) {
k = (k & a[i]);
}
}
if (k == m) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
return 0;
}全部评论 (0)
还没有任何评论哟~