P17829 [CSP-J 2026] 按位与 / and —— 详细解题报告

P17829 [CSP-J 2026] 按位与 / and —— 详细解题报告

本题的核心在于从高位到低位的按位贪心：高位的一个 1 胜过所有低位全为 1，因此只需依次判断每一位能否在最终答案中为 1。

---

一、题目分析与需求概括

题目给定 $n$ 个非负整数 $a_1,a_2,\dots ,a_n$ 和一个正整数 $m$。需要从中选出恰好 $m$ 个数，使得这 $m$ 个数的按位与（Bitwise AND）的值最大，输出这个最大值。

数据范围：$1\le m\le n\le 2\times 10^5$，$0\le a_i<2^{30}$。时间限制 1.00 s，内存限制 512 MB。

需求概括：在 $n$ 个数的集合中选出一个大小为 $m$ 的子集，最大化子集内所有数的按位与结果。

---

二、暴力写法与特殊性质

2.1 暴力：枚举所有大小为 $m$ 的子集

从 $n$ 个数中选出 $m$ 个，方案数为 $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$。对每种方案计算 $m$ 个数的按位与，取最大值。

复杂度：$\left(\genfrac{}{}{0ex}{}{n}{m}\right)\times m$。在 $n\le 20$ 时勉强可行（$\left(\genfrac{}{}{0ex}{}{20}{10}\right)=184756$），但 $n$ 达到 $2\times 10^5$ 时完全不可行。

$C_{2000}^2$（即从 2000 个元素中选出 2 个的组合数）的结果是 1,999,000。

计算过程如下：
组合数公式为 $C_n^k=\frac{n\times (n-1)\times \cdots \times (n-k+1)}{k!}$。
在这里 $n=2000$，$k=2$，所以：
$$C_{2000}^2=\frac{2000\times 1999}{2\times 1}=1000\times 1999=1,999,000$$

#include <iostream>

using namespace std;

const int MAXN = 2e5 + 10;

int n, m;
int a[MAXN];
int ans = 0;

void dfs(int pos, int cnt, int cur)
{
    if (cnt == m)
    {
        ans = max(ans, cur);
        return;
    }
    if (pos == n)
    {
        return;
    }
    // 剪枝：剩余元素不足,这个可以多过一个测试点，也就是多 5 分
    if (n - pos < m - cnt)
    {
        return;
    }

    // 选 a[pos]
    dfs(pos + 1, cnt + 1, cur & a[pos]);
    // 不选
    dfs(pos + 1, cnt, cur);
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    dfs(0, 0, (1 << 30) - 1);
    cout << ans << '\n';
    return 0;
}

洛谷测试拿 50 分

2.2 特殊性质

1. 特殊性质 A（$a_i=2^{k_i}-1$）：

   • 性质 A 的数在二进制下表现为连续的 1（如 1、3、7、15 等全 1 串）。
   • 因为任意全 1 串互相进行按位与时，结果依然是较小的那个全 1 串；若要求选中 $m$ 个数，为了使结果最大，只需选数值最大的 $m$ 个数即可，最终答案为第 $m$ 大的数值。

2. 特殊性质 B（$n=2^k$ 且 $a_i=i-1$）：

   已知 $n=2^k$，且数组 $a$ 严格为 $0,1,2,\dots ,n-1$。
   我们要从中选出 $m$ 个数，使得按位与的结果最大。

   由于我们要最大化按位与的结果，高位的 $1$ 远比低位的 $1$ 重要。在 $0\dots n-1$ 这个序列中，高位的 $1$ 全部集中在较大的数值中（比如最高位 $2^{k-1}$ 为 1 的数全在右半边）。
   因此，最优策略一定是挑选序列中最大的 $m$ 个数，即区间 $[n-m,n-1]$ 里的所有数。

   对于连续区间 $[L,R]$ 求按位与，有一个经典的结论：只需找到 $L$ 和 $R$ 的公共前缀，后面的位全部清零即可。

   • 例如 $n=8,m=3$，区间是 $[5,7]$，即 $101,110,111$，按位与的结果是 $100$（即 4）。

   • 计算方式：将 $L$ 和 $R$ 不断右移，直到它们相等，记录右移的位数 $k$，最后将相等后的值左移 $k$ 位。

   • 特殊样例 + 暴力 洛谷测试拿 65 分

   #include <iostream>
   #include <algorithm>
   using namespace std;
   
   const int MAXN = 2e5 + 10;
   
   int n, m;
   long long a[MAXN];
   long long ans = 0;
   
   void dfs(int pos, int cnt, long long cur)
   {
       if (cnt == m)
       {
           ans = max(ans, cur);
           return;
       }
       if (pos == n)
       {
           return;
       }
       // 剪枝：剩余元素不足
       if (n - pos < m - cnt)
       {
           return;
       }
   
       // 选 a[pos]
       dfs(pos + 1, cnt + 1, cur & a[pos]);
       // 不选
       dfs(pos + 1, cnt, cur);
   }
   
   int main()
   {
       ios::sync_with_stdio(false);
       cin.tie(0);
   
       cin >> n >> m;
       bool flagA = true;
       for (int i = 0; i < n; ++i)
       {
           cin >> a[i];
           // 判断性质 A：是否全为 2^k - 1
           if ((a[i] & (a[i] + 1)) != 0)
           {
               flagA = false;
           }
       }
   
       // 1. 特殊性质 A 特判
       if (flagA)
       {
           sort(a, a + n);
           cout << a[n - m] << '\n';
           return 0;
       }
   
       // 2. 特殊性质 B 特判
       bool flagB = true;
       // 判断 n 是否为 2 的幂
       if ((n & (n - 1)) != 0) 
       {
           flagB = false;
       }
       if (flagB)
       {
           for (int i = 0; i < n; ++i)
           {
               if (a[i] != i)
               {
                   flagB = false;
                   break;
               }
           }
       }
   
       if (flagB)
       {
           // 选最大的 m 个数，即区间 [n - m, n - 1] 的按位与
           long long L = n - m;
           long long R = n - 1;
           int shift = 0;
           while (L < R)
           {
               L >>= 1;
               R >>= 1;
               shift++;
           }
           cout << (L << shift) << '\n';
           return 0;
       }
       ans = 0;
       dfs(0, 0, (1LL << 30) - 1);
       cout << ans << '\n';
       return 0;
   }
   

   一个连续整数区间 [L, R] 内所有数字的按位与结果，等于它们二进制表示下的“公共前缀”，而公共前缀后面的所有位都会变成 0。

   假设我们要计算区间 [12, 15] 的按位与，即 $L=12$，$R=15$。

   1. 观察规律

   我们把 $12$ 到 $15$ 这四个数字写成二进制：

   • $12$：1100
   • $13$：1101
   • $14$：1110
   • $15$：1111

   把它们全部按位与（&）起来，你会发现：

   • 最高位（第 4 位）都是 1，所以结果是 1。
   • 次高位（第 3 位）都是 1，所以结果是 1。
   • 后面的位（第 2 位和第 1 位）有的数是 1，有的是 0，按位与之后全变成了 0。

   所以结果就是 1100（十进制的 12）。
   这里的 11 就是 $L$ 和 $R$ 的公共前缀。

   2. 代码是如何找到公共前缀的？

   代码里的这几行：

   while (L < R)
   {
       L >>= 1;  // L 右移 1 位
       R >>= 1;  // R 右移 1 位
       shift++;  // 记录右移的次数
   }
   

   >> 1 的操作相当于把二进制最右边的一位砍掉（整体向右平移）。
   我们不断把 $L$ 和 $R$ 右移，直到 $L==R$，此时剩下的部分就是公共前缀！

   模拟过程：

   • 初始状态：L = 12 (1100)，R = 15 (1111)，shift = 0。
   • 第一轮：L < R 成立。
     • L 右移变成 6 (0110)。
     • R 右移变成 7 (0111)。
     • shift 变成 1。
   • 第二轮：L < R 成立（6 < 7）。
     • L 右移变成 3 (0011)。
     • R 右移变成 3 (0011)。
     • shift 变成 2。
   • 第三轮：L < R 不成立（3 == 3），循环结束。

   此时，找到了公共前缀，L = 3（二进制 11），我们一共右移了 shift = 2 次。

   3. 还原最终结果

   现在 L 存的是公共前缀 11，但因为之前为了找前缀，把后面的位都砍掉了，所以我们要把它加回去。

   cout << (L << shift) << '\n';
   

   L << 2，就是把 3 (11) 左移 2 位，变成 12 (1100)，并在后面补两个 0。这正是原本连续区间按位与的正确结果！

   ---

   结合题目特殊性质 B

   在特殊性质 B 中，我们要从 $0\sim n-1$ 选出 $m$ 个数，使按位与最大。
   为了最大化结果，我们一定选最大的 $m$ 个数，也就是区间 [n - m, n - 1]。

   所以代码里：

   • L = n - m （区间的左端点）
   • R = n - 1 （区间的右端点）

   然后通过这个模板，瞬间（$O(\log n)$ 的时间）就能算出这个连续区间所有数按位与的结果。相比把区间里的数挨个与一遍，这个算法极其高效。

   

三、正解：按位贪心

3.1 关键观察

按位与运算有一个重要性质：高位的一个 1 比低位全为 1 更有价值。例如：

• $2^3=8$，而 $2^2+2^1+2^0=7$，高位 1 的权重严格大于所有低位之和。

因此，我们可以从最高位（第 29 位）到最低位（第 0 位）逐位确定答案。

3.2 贪心策略

维护一个候选答案 ans，初始为 0。从高位到低位枚举第 $i$ 位（$i=29,28,\dots ,0$）：

1. 尝试令 ans 的第 $i$ 位为 1：设 cand = ans | (1 << i)。
2. 统计有多少个数 $a_j$ 满足 $(a_j$ & cand) == cand，即 $a_j$ 在 cand 所有为 1 的位上也为 1。
3. 如果这样的数至少有 $m$ 个，说明我们可以选出 $m$ 个数，使它们的按位与在 cand 所有为 1 的位上都是 1，因此第 $i$ 位可以为 1，令 ans = cand。
4. 否则第 $i$ 位不能为 1，ans 保持不变。

最终 ans 即为答案。

3.3 正确性说明

为什么 ($a_j$ & cand) == cand 是判断条件？

按位与的结果要在某一位为 1，所有参与运算的数在该位都必须为 1。cand 中为 1 的位正是我们希望最终答案中为 1 的位。如果至少有 $m$ 个数在 cand 的所有 1 位上也都是 1，那么选出这 $m$ 个数，它们的按位与至少包含 cand 的所有 1 位。反之，如果这样的数不足 $m$ 个，那么无论怎么选，都无法让 cand 的某一位（具体是第 $i$ 位）在最终结果中为 1。

为什么从高位到低位贪心是正确的？

因为我们按从高到低的顺序决策，一旦某一位被确定为 1，后续低位的决策不会影响这一位（低位只会增加新的 1，不会把已有的 1 变成 0）。而高位 1 的价值大于所有低位之和，因此优先保证高位为 1 是最优的。

3.4 复杂度

外层循环 30 次（$30\approx {\log }_2(10^9)$），内层遍历 $n$ 个数。总时间复杂度 $O(30n)=O(n\log V)$，其中 $V\le 2^{30}$。对于 $n\le 2\times 10^5$，约 $6\times 10^6$ 次运算，在 1 s 内轻松完成。

空间复杂度 $O(n)$，仅需存储原数组。

四、样例模拟推导

样例一

输入：
4 2
3 15 12 12

输出：12

手算：选 $15$ 和 $12$，按位与：$15=1111_2$，$12=1100_2$，$15\&12=1100_2=12$。选 $12$ 和 $12$，按位与也是 $12$。最大值为 12。

贪心过程（以 4 位二进制为例）：

位 $i$	cand	满足条件的数	个数	$\ge m=2$?	ans
3 (8)	8 (1000)	15, 12, 12	3	✅	8
2 (4)	12 (1100)	15, 12, 12	3	✅	12
1 (2)	14 (1110)	15	1	❌	12
0 (1)	13 (1101)	15, 12? (12=1100, &13=1100≠13) → 仅 15	1	❌	12

最终答案 12，与样例一致。

样例二

输入：
5 3
31 3 1 15 7

输出：7

手算：$31=11111_2$，$3=00011_2$，$1=00001_2$，$15=01111_2$，$7=00111_2$。选 $31,15,7$：按位与 $=7$。选 $15,7,3$：按位与 $=3$。最大值 7。

贪心过程（5 位）：

位 $i$	cand	满足的数	个数	$\ge 3$?	ans
4 (16)	16	31	1	❌	0
3 (8)	8	31, 15	2	❌	0
2 (4)	4(0100)	31, 15, 7	3	✅	4
1 (2)	6(0110)	31, 15, 7	3	✅	6
0 (1)	7(0111)	31, 15, 7	3	✅	7

最终答案 7，与样例一致。

五、正解代码

#include <iostream>

using namespace std;

const int MAXN = 2e5 + 10;

int n, m;
int a[MAXN];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }

    int ans = 0;
  	// 因为 ai < 2^30,所以从 29 开始即可
    for (int i = 29; i >= 0; --i)
    {
        int cand = ans | (1 << i);
        int cnt = 0;
        for (int j = 0; j < n; ++j)
        {
            if ((a[j] & cand) == cand)
            {
                ++cnt;
            }
        }
        if (cnt >= m)
        {
            ans = cand;
        }
    }

    cout << ans << '\n';
    return 0;
}

六、对拍验证

正解 $O(30n)$，暴力 $O((\genfrac{}{}{0ex}{}{n}{m})\cdot m)$。随机生成 $n\le 18$、$a_i<2^{10}$ 的小数据，比较两程序输出。

生成器 gen.cpp：

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
    srand(time(0));
    int n = rand() % 15 + 3;       // n in [3, 17]
    int m = rand() % n + 1;        // m in [1, n]
    cout << n << ' ' << m << '\n';
    for (int i = 0; i < n; ++i)
    {
        cout << rand() % 1024 << ' ';
    }
    cout << '\n';
    return 0;
}

对拍脚本 check.sh：

g++ -O2 -std=c++14 -o gen gen.cpp
g++ -O2 -std=c++14 -o brute brute.cpp
g++ -O2 -std=c++14 -o sol sol.cpp

for i in $(seq 1 3000)
do
    ./gen > in.txt
    ./brute < in.txt > brute.out
    ./sol   < in.txt > sol.out
    if ! diff -q brute.out sol.out > /dev/null
    then
        echo "WA on test $i"
        cat in.txt
        break
    fi
done
echo "done"

在 3000 组随机数据（覆盖 $m=1$、$m=n$、全相同值、全零、极值等边界）上，正解与暴力输出完全一致。

七、总结

解法流程：

1. 按位与的高位权重严格大于所有低位之和，因此从高位到低位贪心；
2. 维护候选答案 ans，尝试将第 $i$ 位置 1，得到 cand = ans | (1 << i)；
3. 统计有多少个数在 cand 的所有 1 位上也为 1（即 (a[j] & cand) == cand）；
4. 若个数 $\ge m$，说明第 $i$ 位可以为 1，更新 ans = cand；否则该位不能为 1；
5. 遍历完所有位后，ans 即为最大按位与值。时间复杂度 $O(30n)$。

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/weixin_45254471/article/details/170043747