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;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/282861.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

网络安全笔记-day6,NTFS安全权限

文章目录 NTFS安全权限常用文件系统文件安全权限打开文件安全属性修改文件安全权限1.取消父项继承权限2.添加用户访问权限3.修改用户权限4.验证文件权限5.总结权限 强制继承父项权限文件复制移动权限影响跨分区同分区 总结1.权限累加2.管理员最高权限2.管理员最高权限 NTFS安全…

使用npm创建一个全局的cli命令,就像vue-cli一样

我们用过vue-cli等工具包&#xff0c;全局安装之后&#xff0c;我们可以直接使用vue create等命令&#xff0c;实际上能够这样使用的原因&#xff0c;就是使用了package.json里面的bin字段注册命令。接下来就以一个脚本文件为例子为大家演示一下bin是如何发挥作用的。 创建项目…

vue.js+element-ui的基础表单

遇到原生的html小型单页应用时&#xff0c;是脱离了vue框架&#xff0c;而我们又想使用vue的语法和element的组件加快我们的开发速度&#xff0c;这个时候就需要引用他们的js了。技术栈即htmlvue.jselement-ui。而使用它们的方法也很简单&#xff0c;引入对应的js和css文件即可…

MySQL定时任务Event详解

文章目录 基本概念一、Event事件使用权限二、开启\关闭Event事件三、Event事件定义格式四、事件调度使用案例4.1 准备工作4.2 创建单次定时执行事件4.2.1 创建指定时间单次执行事件任务4.2.2 创建延迟时间单次执行事件任务4.2.3 创建单次执行事件任务[多SQ执行] 4.3 创建循环定…

数据仓库的数据处理架构Lambda和Kappa

1.数据仓库 数据仓库(Data Warehouse),简写DW。顾名思义,数据仓库是一个很大的数据存储集合,为企业分析性报告和决策支持而创建,是对多元业务数据的筛选与整合,具备一定的BI能力,主要用于企业的数据分析、数据挖掘、数据报表等方向,指导业务流程改进、监视时间、成本、…

从0到1实现RPC | 03 重载方法和参数类型转换

一、存在的问题 1.重载方法在当前的实现中还不支持&#xff0c;调用了会报错。 2.类型转换也还存在问题。 假设定义的接口如下&#xff0c;参数是float类型。 在Provider端接受到的是一个Double类型&#xff0c;这是因为web应用接收的请求后处理的类型。 在反射调用的时候就会…

前言:为什么C语言最适合编程入门?

前言&#xff1a;为什么C语言最适合编程入门&#xff1f; C语言被认为最适合编程入门的原因主要有以下几点&#xff1a; 基础且强大&#xff1a;C语言是一种基础且强大的编程语言。它提供了对底层硬件的直接访问&#xff0c;让初学者能够更好地理解计算机的工作原理&#xff0…

从零开始学Spring Boot系列-集成Kafka

Kafka简介 Apache Kafka是一个开源的分布式流处理平台&#xff0c;由LinkedIn公司开发和维护&#xff0c;后来捐赠给了Apache软件基金会。Kafka主要用于构建实时数据管道和流应用。它类似于一个分布式、高吞吐量的发布-订阅消息系统&#xff0c;可以处理消费者网站的所有动作流…

基于python+vue的O2O生鲜食品订购flask-django-nodejs-php

近年来互联网络的迅猛发展和电子终端设备的普及&#xff0c;赋予了各行业充足的发展空间。微信小程序的O2O生鲜食品订购相比于传统信息技术&#xff0c;时效性是它最大的特色&#xff0c;已经在电子娱乐、经济等中发挥着举足轻重的作用。短时间内迅速扩大了线上管理系统的规模。…

了解云原生

1、云原生学习路线 学习云原生(Cloud Native)技术涉及了解和掌握一系列的概念、技术和工具。云原生是一种构建和运行应用程序的方法&#xff0c;旨在充分利用云计算的灵活性、可伸缩性和弹性。以下是一个可以参考的学习路线&#xff1a; 了解云原生基础 学习云计算的基本概念&…

此站点正在尝试打开 ,chrome/edge 允许http网站打开url schema

正常https链接会有首次允许选项 但http没有&#xff0c;每次都会弹出&#xff0c;非常烦人。 Chrome / Edge 配置 地址栏输入 chrome://flags/搜索Insecure origins treated as secure, 配置允许网站&#xff0c;需要协议和端口再次跳转会显示始终允许选项

puppeteer使用示例云顶之弈官网

自己从0到1开发的&#xff0c;微信小程序【云顶宝藏】求求点个5星好评吧&#xff01; 需求&#xff1a;拿到所有英雄的信息 思路&#xff1a;点击每个英雄&#xff0c;进入英雄详情页&#xff0c;拿信息&#xff0c;并返回&#xff0c;继续下一个英雄** 最终效果 本地环境 win…

docker进阶篇,docker集群介绍

docker swarm 官网&#xff1a;https://docs.docker.com/engine/swarm/how-swarm-mode-works/nodes/ 什么是 docker swarm docker swarm 是 docker 官方提供的容器编排和集群管理工具。它允许用户将多个 docker 主机组成一个虚拟的 docker 集群&#xff0c;以便更高效地管理…

云计算系统等保测评对象和指标选取

1、云计算服务模式与控制范围关系 参考GBT22239-2019《基本要求》附录D 云计算应用场景说明。简要理解下图&#xff0c;主要是云计算系统安全保护责任分担原则和云服务模式适用性原则&#xff0c;指导后续的测评对象和指标选取。 2、测评对象选择 测评对象 IaaS模式 PaaS模式…

文本处理(有关go web方面)

文本处理 3.21 本文基本摘录至https://learnku.com/docs/build-web-application-with-golang/073-regular-processing/3197&#xff0c;仅供学习&#xff0c;如果有需要学习web的同学可以看这个&#xff0c;不懂的再来看我的&#xff0c;我的仅作补充 文本处理是什么&#xf…

基于CSS3制作专属可自由旋转的立方体

一、代码区域 1.1 css3代码区域 <style>* {padding: 0;margin: 0;list-style: none;}/* 1) 定义动画 */keyframes loop {0% {transform: rotateX(348deg) rotateY(67deg) rotateZ(95deg);}50% {transform: rotateX(0deg) rotateY(0deg) rotateZ(0deg);}100% {transform:…

论文阅读-MIPD:一种用于分布式深度神经网络训练的自适应梯度稀疏化框架

摘要—基于参数服务器架构的异步训练广泛应用于大规模数据集和深度神经网络模型的扩展训练。在大规模分布式深度学习系统中&#xff0c;通信一直被认为是主要瓶颈。最近的研究尝试通过梯度稀疏化和量化方法来减少通信流量。我们发现前期研究存在三个限制。首先&#xff0c;他们…

基于python+vue网络相册设计与实现flask-django-nodejs-php

网络相册设计与实现的目的是让使用者可以更方便的将人、设备和场景更立体的连接在一起。能让用户以更科幻的方式使用产品&#xff0c;体验高科技时代带给人们的方便&#xff0c;同时也能让用户体会到与以往常规产品不同的体验风格。 与安卓&#xff0c;iOS相比较起来&#xff0…

蓝桥杯2021年第十三届省赛真题-卡片

一、题目 卡片 小蓝有很多数字卡片&#xff0c;每张卡片上都是数字 0 到 9。 小蓝准备用这些卡片来拼一些数&#xff0c;他想从 1 开始拼出正整数&#xff0c;每拼一个&#xff0c; 就保存起来&#xff0c;卡片就不能用来拼其它数了。 小蓝想知道自己能从 1 拼到多少。 例如&am…

Cookie和Session登录注册案例

文章目录 一、需求说明![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/f29467ed6b7f4de7a568004ad50de591.png)二、用户登录1、Dao层代码2、Service层代码3、Web层代码 三、记住用户四、用户注册五、展示验证码 一、需求说明 二、用户登录 1、Dao层代码 UserMapp…