上海市计算机学会竞赛平台2024年12月月赛丙组找子序列
发布时间
阅读量：
阅读量
题目描述
Dave 有一个长度为 nn 的非负整数序列 a1∼na1∼n 和一个非负整数 mm。
他希望知道是否有一个 aa 的非空子序列，使得子序列中所有元素的按位与（bitwise AND）结果为 mm。
换言之，他想知道是否存在一个下标序列 i1∼ki1∼k（k≥1k≥1），满足 1≤i1<i2<⋯<ik≤n1≤i1<i2<⋯<ik≤n，且 ai1&ai2&⋯&aik=mai1&ai2&⋯&aik=m。
输入格式
第一行一个整数 TT 表示数据组数。对于每组数据：
第一行两个整数 n,mn,m。
第二行 nn 个非负整数 a1∼na1∼n。
输出格式
对于每组数据，如果存在这样的非空子序列，输出一行 Yes，否则输出一行 No。
数据范围
对于 30%30% 的数据，1≤∑n≤201≤∑n≤20，0≤ai,m<320≤ai,m<32。
对于 60%60% 的数据，1≤∑n≤1031≤∑n≤103，0≤ai,m<2100≤ai,m<210。
对于 100%100% 的数据，1≤T≤1051≤T≤105，1≤∑n≤5×1051≤∑n≤5×105，0≤ai,m<2300≤ai,m<230。
样例数据
输入:
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
说明:
在第四组数据中，整个序列即为所求子序列。
详见代码:
#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)
还没有任何评论哟~