当前位置：首页 > news >正文

打卡信奥刷题（3060）用C++实现信奥题 P6824 「EZEC-4」可乐

news 2026/5/24 2:34:53

P6824 「EZEC-4」可乐

题目背景

很久以前，有一个 pigstd，非常迷恋美味的可乐。为了得到美味的可乐，他几乎用尽了所有的钱，他甚至对自己的 npy 也漠不关心~~其实是因为他没有 npy~~，更不爱好看戏。除非买了新可乐，才会坐上马车出门炫耀一番。每一天，每个钟头他都要喝上一瓶新可乐。

pigstd 最近又买了许多箱新可乐——当然，这些可乐只有聪明的人才能喝到。

题目描述

pigstd 现在有n nn箱可乐，第i ii箱可乐上标着一个正整数a i a_{i}ai。

若 pigstd 的聪明值为一个非负整数x xx，对于第i ii箱可乐，如果( a i ⊕ x ) ≤ k (a_{i} \oplus x )\le k(ai⊕x)≤k，那么 pigstd 就能喝到这箱可乐。

现在 pigstd 告诉了你k kk与序列a aa，你可以决定 pigstd 的聪明值x xx，使得他能喝到的可乐的箱数最大。求出这个最大值。

输入格式

第一行两个由空格分隔开的整数n , k n,kn,k。

接下来n nn行，每行一个整数a i a_iai，表示第i ii箱可乐上标的数。

输出格式

一行一个正整数，表示 pigstd 最多能喝到的可乐的箱数。

输入输出样例 #1

输入 #1

3 5 2 3 4

输出 #1

输入输出样例 #2

输入 #2

4 625 879 480 671 853

输出 #2

说明/提示

提示

pigstd 的聪明值x xx可以为0 00。

样例解释

样例 1 解释：容易构造当x = 0 x = 0x=0时，可以喝到所有可乐。

样例 2 解释：容易构造x = 913 x = 913x=913，可以喝到所有可乐。

样例解释未必是唯一的方法。

数据范围

本题采用捆绑测试。

Subtask 1（29 points）：1 ≤ n , k , a i ≤ 1000 1 \le n,k,a_{i} \le 10001≤n,k,ai≤1000。
Subtask 2（1 points）：a i ≤ k a_{i} \le kai≤k。
Subtask 3（70 points）：无特殊限制。

对于所有数据，保证1 ≤ n , k , a i ≤ 10 6 1 \le n,k,a_{i} \le 10^61≤n,k,ai≤106。

⊕ \oplus⊕代表异或，如果您不知道什么是异或，请单击这里。

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintM=1e6+10;intc[M*2],a[M],n,k,ans,maxn;ints1[50],s2[50];voidf(intb){memset(s1,0,sizeof(s1));memset(s2,0,sizeof(s2));intlen1=0,len2=0,kk=k;while(b)s1[++len1]=b%2,b/=2;while(kk)s2[++len2]=kk%2,kk/=2;intlen=max(len1,len2);for(inti=1;i<=len/2;i++)swap(s1[i],s1[len-i+1]),swap(s2[i],s2[len-i+1]);intsum=0;for(inti=1;i<=len;i++)if(s2[i]==0)sum=sum*2+s1[i];else{intk1=(sum*2+s1[i])*1<<(len-i),k2=(sum*2+1+s1[i])*1<<(len-i);c[k1]++,c[k2]--;sum=sum*2+(s1[i]^1);}c[sum]++,c[sum+1]--;}intmain(){scanf("%d%d",&n,&k);maxn=k;for(inti=1;i<=n;i++){scanf("%d",&a[i]);f(a[i]);maxn=max(maxn,a[i]);}for(inti=1;i<=maxn*2;i++)c[i]+=c[i-1];for(inti=0;i<=maxn*2;i++)ans=max(ans,c[i]);cout<<ans;return0;}