P17829 [CSP-J 2026] 按位与 / and

题目:

小 R 有个非负整数。

小 X 给了小 R 一个正整数，并要求小 R 从这个非负整数中选出恰好个，使得选出的个数的二进制按位与的值最大。

你需要帮助小 R 求出，他能选出的个数的按位与的最大值。

输入格式

从文件 and.in 中读入数据。

输入的第一行包含两个正整数。

输入的第二行包含个非负整数，依次表示小 R 的个非负整数。

输出格式

输出到文件 and.out 中。

输出一行一个非负整数，表示小 R 能选出的个数的按位与的最大值。

输入输出样例 #1

输入 #1

4 2
3 15 12 12

输出 #1

输入输出样例 #2

输入 #2

5 3
31 3 1 15 7

输出 #2

说明/提示

样例 1 解释

小 R 有个非负整数：。

若小 R 选择，则按位与的值为；
若小 R 选择，则按位与的值为；
若小 R 选择，则按位与的值为；
若小 R 选择，则按位与的值为。

因此，小 R 能选出的个数的按位与的最大值为。

样例 2 解释

若小 R 选择，则按位与的值为。可以证明，小 R 能选出的个数的按位与的最大值为。

样例 3

见题目目录下的 and/3.in 与 and/3.ans。

该样例满足测试点的约束条件。

样例 4

见题目目录下的 and/4.in 与 and/4.ans。

该样例满足测试点的约束条件。

样例 5

见题目目录下的 and/5.in 与 and/5.ans。

该样例满足测试点的约束条件。

数据范围

对于所有测试数据，均有：

；
对于所有（），均有。

::cute-table{tuack}

测试点编号				特殊性质
				无
				无
				无
				无
				无
				A
				B
				无
				无
				无

特殊性质 A：对于所有（），均存在非负整数满足。

特殊性质 B：存在非负整数满足，且对所有（），均有。

题解：

#include<iostream>
using namespace std;
string func(int x) 
{
    string t="000000000000000000000000000000"; 
    int p=29;
    while(x>0)
    {
        t[p]=char(x%2+'0');
        x/=2;
        p--;
    }
    return t;
}
string a[200010];
string b[200010];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        int t;
        cin>>t;
        a[i]=func(t);
    }
    string ans = "000000000000000000000000000000";
    for(int bit=29;bit>=0;bit--)
    {
        int cnt=0;
        int k=0;
        for(int i=0;i<n;i++)
        {
            if(a[i][29-bit]=='1')
            {
                b[k]=a[i];
                cnt++;
                k++;
            }
        }
        if(cnt>=m)
        {
            ans[29-bit]='1'; 
            for(int i=0;i<k;i++)
            {
                a[i]=b[i];
            }
            n=k;
        }
    }
    int v=0;
    for(int i=0;i<30;i++)
    {
        v=v*2+(ans[i]-'0');
    }
    cout<<v<<endl;
    return 0;
}

题目中，二进制下，某一位想为 1，必须这 m 个数在这一位都为 1。
因此从高位到低位贪心判断：当前位能不能保留，要看“当前候选集合里有多少个数这一位是 1”。

步骤：
先把所有数都看成 30 位二进制字符串（因为 ai < 2^30）
从第 29 位到第 0 位枚举
统计当前候选集合中，当前位是 1 的数有多少个
若这个数目 >= m
说明这一位可以保留为 1
把答案这一位设为 1
并且只保留当前位为 1 的数，继续处理更低位
若这个数目 < m
这一位不能保留，答案这一位为 0
最终把得到的二进制答案转换成十进制输出