A174731.[CSP-J 2026] 按位与 / and(官方数据)

普及/提高-

CSP-J

通过率:0%

时间限制:1.00s

内存限制:1024MB

题目描述

小 R 有 nn 个非负整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

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

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

输入格式

输入的第一行包含两个正整数 n,mn,m。

输入的第二行包含 nn 个非负整数 a1,a2,…,ana_1,a_2,\ldots,a_n,依次表示小 R 的 nn 个非负整数。

输出格式

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

输入输出样例

  • 输入#1

    4 2
    3 15 12 12

    输出#1

    12
  • 输入#2

    5 3
    31 3 1 15 7

    输出#2

    7

说明/提示

样例 1 解释

小 R 有 44 个非负整数:3,15,12,123,15,12,12。

  • 若小 R 选择 3,153,15,则按位与的值为 3and15=33\mathbin{\mathrm{and}}15=3;
  • 若小 R 选择 3,123,12,则按位与的值为 3and12=03\mathbin{\mathrm{and}}12=0;
  • 若小 R 选择 15,1215,12,则按位与的值为 15and12=1215\mathbin{\mathrm{and}}12=12;
  • 若小 R 选择 12,1212,12,则按位与的值为 12and12=1212\mathbin{\mathrm{and}}12=12。

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

样例 2 解释

若小 R 选择 31,15,731,15,7,则按位与的值为 31and15and7=731\mathbin{\mathrm{and}}15\mathbin{\mathrm{and}}7=7。可以证明,小 R 能选出的 mm 个数的按位与的最大值为 77。

样例 3

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

该样例满足测试点 8∼108\sim 10 的约束条件。

样例 4

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

该样例满足测试点 14,1514,15 的约束条件。

样例 5

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

该样例满足测试点 18,1918,19 的约束条件。

数据范围

对于所有测试数据,均有:

  • 1≤m≤n≤2×1051\le m\le n\le 2\times 10^5;
  • 对于所有 ii(1≤i≤n1\le i\le n),均有 0≤ai<2300\le a_i<2^{30}。

::cute-table{tuack}

测试点编号 n≤n\le mm max⁡i=1nai<\max_{i=1}^{n}a_i< 特殊性质
1∼51\sim 5 2020 ≤n\le n 2202^{20} 无
66 20002000 =1=1 2202^{20} 无
77 20002000 =n=n 2202^{20} 无
8∼108\sim 10 20002000 =2=2 2202^{20} 无
11,1211,12 2×1052\times 10^5 =n−1=n-1 2202^{20} 无
1313 2×1052\times 10^5 ≤n\le n 2202^{20} A
14,1514,15 2×1052\times 10^5 ≤n\le n 2202^{20} B
16,1716,17 2×1052\times 10^5 ≤n\le n 44 无
18,1918,19 2×1052\times 10^5 ≤n\le n 2102^{10} 无
2020 2×1052\times 10^5 ≤n\le n 2302^{30} 无

特殊性质 A:对于所有 ii(1≤i≤n1\le i\le n),均存在非负整数 kik_i 满足 ai=2ki−1a_i=2^{k_i}-1。

特殊性质 B:存在非负整数 kk 满足 n=2kn=2^k,且对所有 ii(1≤i≤n1\le i\le n),均有 ai=i−1a_i=i-1。

and.zip

输入解题思路,AI测评打分。不知道怎么写?

首页