#cspjf2026t3. 按位与(and)
按位与(and)
按位与(and)
题目描述
小 R 有 n 个非负整数 。
小 X 给了小 R 一个正整数 m,并要求小 R 从这 n 个非负整数中选出恰好 m 个,使得选出的 m 个数的二进制按位与的值最大。
你需要帮助小 R 求出,他能选出的 m 个数的按位与的最大值。
输入格式
从文件 and.in 中读入数据。
输入的第一行包含两个正整数 n,m。
输入的第二行包含 n 个非负整数,依次表示小 R 的 n 个非负整数。
输出格式
输出到文件 and.out 中。
输出一行一个非负整数,表示小 R 能选出的 m 个数的按位与的最大值。
输入输出样例 #1
4 2
3 15 12 12
12
输入输出样例 #2
5 3
31 3 1 15 7
7
说明/提示
样例 1 解释
小 R 有 4 个非负整数:3,15,12,12。
- 若小 R 选择 3,15,则按位与的值为 3 and 15=3;
- 若小 R 选择 3,12,则按位与的值为 3 and 12=0;
- 若小 R 选择 15,12,则按位与的值为 15 and 12=12;
- 若小 R 选择 12,12,则按位与的值为 12 and 12=12。
因此,小 R 能选出的 m 个数的按位与的最大值为 12。
样例 2 解释
若小 R 选择 31,15,7,则按位与的值为 31 and 15 and 7=7。可以证明,小 R 能选出的 m 个数的按位与的最大值为 7。
样例 3
见题目目录下的 and/3.in 与 and/3.ans。
该样例满足测试点 8∼10 的约束条件。
样例 4
见题目目录下的 and/4.in 与 and/4.ans。
该样例满足测试点 14,15 的约束条件。
样例 5
见题目目录下的 and/5.in 与 and/5.ans。
该样例满足测试点 18,19 的约束条件。
【数据范围】
对于所有测试数据,均有:
- ;
- 对于所有 ,均有 。
| 测试点编号 | n≤ | m | 特殊性质 | |
|---|---|---|---|---|
| 1∼5 | 20 | ≤n | 无 | |
| 6 | 2000 | =1 | ||
| 7 | =n | |||
| 8∼10 | =2 | |||
| 11,12 | =n−1 | |||
| 13 | ≤n | A | ||
| 14,15 | B | |||
| 16,17 | 4 | 无 | ||
| 18,19 | ||||
| 20 |
特殊性质 A:对于所有,均存在非负整数 满足 。s
特殊性质 B:存在非负整数 k 满足 ,且对所有,均有