题目传送门

题意分析

从 \(a_1,a_2,\cdots,a_n\) 里选择 \(m\) 个，使得按位与的答案最大。记按位与为 \(\&\)。

对于二进制，显然高位为 \(1\) 一定比其余所有低位都为 \(1\) 的答案更大，因此考虑从高位到低位贪心。

\(i\) 枚举 \(2^{30},2^{29},\cdots,2^0\) 每一位位权，记答案为 \(\textit{ans}\)，令 \(\textit{ans}\leftarrow \textit{ans}\mid2^i\)， 如果有大于等于 \(m\) 个数使得 \(a_i\&\textit{ans}=\textit{ans}\)，说明这是可行的。否则不可行，说明 \(\textit{ans}\) 不含 \(2^i\)。

时间复杂度 \(\mathcal O(n\log V)\)，\(V=2^{30}\) 为值域。

AC 代码

//#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
constexpr const int N=2e5,M=2e5,V=30;
int n,m,a[N+1];
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}int ans=0;for(int i=V;0<=i;i--){int x=ans|(1<=m){ans=x;}}cout<