本文主要是介绍Codeforces Round #936 (Div. 2)D（拆位贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路：首先需要知道：如果某一位的数量为奇数,那么无论怎么分都会最终变成1.
整个问题转化成能有多少个隔断选取位置
先将所有数都拆位来看,首先观察那些比x的最高位还要高的位：
如果这些位的数量为奇数, 那么必然会使其位是1，不满足题意直接-1.
如果数量是偶数,那么就会存在若干个不可取区间,然后将这所有区间都合并起来.
然后再从x的最高位逐一往下枚举：如果x的某一位是1.那么有两种选的方案
1、选完后这一位变成0，那么接下里随便怎么选都不会大于x了，也就是在满足条件的情况下尽可能的选取位置即可.
2、选完后仍然为1,这种情况下可行区间内的任意位置都可选
如果x的某一位是0，那么就必须选成0，否则接下来的所有情况都不用讨论了。在必须选成0的情况之下不可行域会被增大。
最终枚举完所有位以后的可行域即是所有隔断的可选位置,全部选上即为最大值.
// Problem: D. Birthday Gift
// Contest: Codeforces - Codeforces Round 936 (Div. 2)
// URL: https://codeforces.com/contest/1946/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve()
{cin >> n >> m;vector<int>cnt(35 , 0);int maxx = -1;for(int i = 0 ; i < 32 ; i ++){if((m >> i) & 1){cnt[i] = 1;maxx = i;}} vector<int>num[35];for(int i = 1 ; i <= n ; i ++)cin >> a[i];for(int i = 1 ; i <= n ; i ++){for(int j = 0 ; j < 32 ; j ++){if((a[i] >> j) & 1){num[j].pb(i);}}}//大于maxx的需要偶数一组set<pair<int,int>>st;//不可行域for(int i = maxx + 1 ; i < 32 ; i ++){if(num[i].size() & 1){cout << -1 << endl;return;}for(int j = 0 ; j < num[i].size() ; j += 2){st.insert({num[i][j] , num[i][j + 1] - 1});//所有的不可域}}vector<int>diff(n + 5 , 0);for(auto it : st){//不可行域的合并diff[it.x]++;diff[it.y + 1]--;}vector<int>vis(n + 5 , 0);int cntt = 0;for(int i = 0 ; i <= n ; i ++){cntt += diff[i];vis[i] = cntt; }//如果某一位是1 , 那么任意区间都可选 ，但是需要满足后续，也就是区间往后延，如果某一位需要是0，那么就必须全偶数,也就是说不可行域是在不断增加的int ans = -100;int i;for(i = maxx ; i >= 0 ; i --){if(cnt[i] == 1){//这位是1//取0操作,后续不用管if(num[i].size() == 0){int c = 0;for(int l = 1 ; l < n ; l ++){c += (vis[l] == 0);}ans = max(ans , c);}else if(num[i].size() % 2 == 0){//可以取到0int st = 1;int c = 0;for(int j = 0 ; j < num[i].size() ; j += 2){int l = st , r = num[i][j] - 1;for(int t = l ; t <= r ; t ++){if(vis[t] == 0){c++;}}st = num[i][j + 1];}for(int t = st ; t < n ; t ++){if(vis[t] == 0){c ++;}}ans = max(ans , c);}else{continue;//必须取到1,那么也就是随便选}}else{//不可行域的减少if(num[i].size() & 1){if(ans < 0){cout << -1 << endl;}else{cout << ans + 1 << endl;}return;}else{//不可行域更新for(int j = 0 ; j < num[i].size() ; j += 2){int l = num[i][j] , r = num[i][j + 1] - 1;for(int t = l ; t <= r ; t ++)vis[t]++;}}}}int k = 0;for(int i = 1 ; i < n ; i ++){k += (vis[i] == 0);}ans = max(ans , k);cout << ans + 1 << endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}
这篇关于Codeforces Round #936 (Div. 2)D（拆位贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
