上海市计算机学会竞赛平台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;
}

原文地址：https://blog.csdn.net/a121677_/article/details/145114148

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！