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

【251128】CF2164 Div.1+2 vp 总结

题目梗概

题好多呜,所以不设梗概了。(

赛时记录

A,感觉水呢;B,完全不会;C,感觉贪心;D,疑似差值;E,一头雾水;F,怎么还分两个版本,都不会呜;G,咋是交互;H,不可能会。

A!写了两版代码结果呢交的时候交错了导致……搞得跟我 A 也没过似的。

嗯对,总之就是算 \(\max\)\(\min\) 出来比对一下 \(x\) 在不在范围内就行了。

B!分析了半天发现,噢哟,有意思,如果不满足条件的话 \(n\) 最大三十几???暴力,上!

C!写完了写完了,好难好难。

D,玩了一会弄出来了。

时间不错了,开 E。思考思考思考,无效。

时间到了,交题去吧。

分数分布

A B D 都过了,C 怎么似了?查了半天,我是【】,居然把 \(life\)\(dam\) 写反了,我是【】我是【】。

呜呜呜怎么这么粗心啊,CF 样例怎么这么水啊,呜呜呜。

赛后题解

A

不难发现我们只需要保证序列中的最大值 \(mx\) 和最小值 \(mn\) 构成的区间 \([mn,mx]\) 中存在 \(x\) 就行了;等价于判断是否满足 \(mn \le x \le mx\)。时间复杂度 \(O(n)\)

B

首先你会想到 \(O(n^2)\) 暴力,枚举即可,但是明显过不去。怎么办呢?

推导一下,如果要输出 -1 也就是无解情况会发生什么?

首先肯定最多也只有一个偶数,否则就会——如果有两个偶数那么直接拿出来做 \(\bmod\) 操作肯定是偶数啊,所以要无解你肯定最多也只能有一个偶数。

接着考虑奇数,就假设是 \(a_i\)\(a_j\) 好了。因为 \(a_j = \lfloor \frac{a_j}{a_i} \rfloor \times a_i + a_j \bmod a_i\),又因为设定,\(a_j \bmod a_i\)\(a_i\) 都是奇数所以 \(\lfloor \frac{a_j}{a_i} \rfloor\) 必然为偶数,也就是有 \(a_j > 2 \times a_i\)

由于题目保证严格递增,奇数那一条规范直接锁死范围——毕竟 \(a_i\) 最大就 \(10^9\),后者要至少是前者的两倍以上的话,\(n\) 就最大也才 \(31\) 了!那直接上暴力嘛,如果有解肯定能 \(O(n)\) 求出,而无解的话 \(n\) 最大 \(31\)\(O(n^2)\) 跑多少次都不会挂!

http://www.gsyq.cn/news/64277.html

相关文章:

  • 2025年四川成都奖杯奖牌定制、奖章证书定制、奖杯定制、水晶奖杯定制、奖牌定制品牌厂家企业推荐top5指南
  • 基于PyTorch的YOLOv5目标检测 - 教程
  • 2025年工业冷风机车间降温技术全解析,铁皮棚车间降温/焊装车间通风降温/压铸车间通风降温/机械厂车间降温工业冷风机厂商推荐排行
  • 2025非遗新中式品牌排行TOP榜,这些品牌正走红,非遗新中式推荐排行色麦新中式层层把关品质优
  • 2025年靠谱的四川变形缝_变形缝厂家实力及口碑推荐榜
  • SQL Server设置用户查看指定数据库的指定表单
  • 深入解析:Mac如何安装mysql和完全卸载mysql
  • 深入解析:maven打jar包,将依赖的jar提取出来
  • 实用指南:云架构设计与实践:从基础到未来趋势
  • 2025年广东AI搜索优化GEO公司推荐:惠算领衔,多平台适配
  • 关于图灵停机问题不可判定性证明
  • Vue3.0 简单商城—购物车组件
  • 04.Git初始化代码仓库并上传项目代码
  • 2025 温度循环试验箱厂家推荐指南!技术实力与行业方案深度解析
  • 源码解析:CRMEB移动端订单模块的架构设计与数据同步机制
  • Vue3.0 简单商城—商品列表组件
  • Vue3.0 简单商城—Header组件与登录模块编写
  • Spring MVC项目配置tomcat
  • 2025年下半年江苏干式变压器、油浸式变压器、变电站、配电箱、电表箱厂家综合推荐指南:五大优质供应商深度解析
  • IDEA+MyBatis实现增删改查(1)
  • 阿里云安全防护神器ESA
  • 2025 年衬塑管道厂家最新推荐榜,技术实力与市场口碑深度解析
  • Makefile 快速入门
  • 2025年室内体育馆运动地胶生产厂家权威推荐榜单:定制运动地板/室外地胶‌/网红场馆‌源头厂家精选
  • 2025 年常州家政服务机构最新推荐榜,技术实力与市场口碑深度解析:全品类服务品牌测评正规月嫂 / 老人护理 / 育儿照料 / 白班保姆 / 钟点工 / 家政保洁服务公司推荐
  • IDEA 2024版如何创建Spring Boot项目
  • 什么DeekSpeek居然自己会学习?
  • 2025年下半年北京pmp培训,产品经理培训,人工智能培训,npdp培训,pmp项目管理培训机构综合推荐与选择指南
  • 2025年陶瓷环订做厂家权威推荐榜单:陶瓷零件/陶瓷手臂‌/陶瓷手臂‌源头厂家精选
  • 上海债务重组公司怎么选?这份“避坑”指南助你找到靠谱服务