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

CF1977 Codeforces Round 948 (Div. 2) 游记(VP)

省流

仅做出两题,结果凭借手速拿到表现分 \(1740\)

10.17

内含剧透,请vp后再来。

不是题解!!!!!!!

赛前

早上花了很多时间试图把 \(stars569\) 搞的数据库装好,结果搞了半天缺一堆东西,愤而开始摸一把比赛。
https://github.com/stars569/ACM_Summary
星辰的项目,可以统计做了什么题,以及根据加入时间和难度来个艾宾浩斯记忆法复习,背单词式 \(ACM\),你值得拥有。

赛时

A 题模拟,不谈。
B 题要求用二进制表示一个数 \(x\),但新引入了一个值 \(-1\),以及要求不能有两个连续的非零数,问如何表示。可以想到形如 \(1110\) 的连续 \(1\) 可以表示为 \(-1001\),按这个思路模拟就行。
C 题给了 \(n \leq 2000\) 个数,要求取一个子集,使子集内所有数的 \(lcm\) 不存在于一开始的 \(n\) 个数中。问子集最大为多大。我主要从两个方面想,构造和 \(DP\)。通过构造,想要塞入尽可能多的数,那么全部塞满,此时 \(lcm\) 只会是大于等于最大值的数,然后枚举最大值和大于等于最大值的所有数就是 \(n^2\) 级别的,但不知道该怎么做。猜了一个相同最大值只会删掉一个较小的,但不能通过样例。\(DP\) 也很容易想 \(n^2\) 级别的,状态存储现在是第几个前面最大选了多少个,但没有很好的想到该存什么。肯定不能存所有的可能 \(lcm\),如果全是质数肯定就炸了,所以也不了了之。感觉肯定和因数有关,但没有什么很好的思路,就这样耗过了 \(110min\),比赛结束。

赛后

看 C 题解,还是先判断是否可以全选。如果不可以,那么证明所有数的 \(lcm\) 就是最大值。所以所有数任意组合的 \(lcm\) 都是最大值的约数,所以枚举最大值的所有约数,把是这个约数的约数的值加入进来以求找到这个约数,最后再验证得到的实际值有没有出现,如果没有则是答案的候选。时间复杂度就是 \(O(\log {1e18} * n * \sqrt{max})\)

2025年10月17日

http://www.hskmm.com/?act=detail&tid=32882

相关文章:

  • 别被波形“骗” 了!差分探头与无源探头测量不一致的 5 大关键因素
  • 2025 年展览会服务商最新推荐榜权威发布:22 年经验甄选十强品牌,助力企业参展高效决策
  • 2025年信息流代运营服务商权威推荐榜单:专业投放策略与效果优化服务口碑之选
  • 2025 年焊把线厂家最新推荐榜:国标欧标铜芯软焊把线优质企业排行,优质品牌助力选购欧标/铜芯/软/耐高温焊把线厂家推荐
  • 基于MATLAB的倒立摆控制实现方案
  • 2025 年展会服务商最新推荐排行榜:聚焦一站式服务与高效执行能力的优质企业榜单瓷砖/暖通/照明/门窗/玻璃/厨卫/卫浴/灯饰展会厂家推荐
  • 数据迁移mysql--sr
  • iOS 26 App 开发阶段性能优化全流程,从监控到调优的多工具协作实践
  • MATLAB实现语音去混响与去噪
  • 风险评估的流程和各阶段的工作内容
  • 无穷小和无穷大
  • Adobe Media Encoder 2025 免费版一键安装包完整安装教程(含下载安装包)
  • 2025 年最新推荐船用气囊源头厂家权威排行榜:聚焦专业生产与可靠供应,助力精准选购优质产品橡胶/船舶/防撞/山东/港口用船用气囊厂家推荐
  • 【隐语SecretFlow用户案例】亚信科技构建统一隐私计算框架探索实践
  • Zynq选型
  • 2025 西安楼盘最新推荐排行榜:聚焦优质教育配套的品质楼盘精选高端/刚需/品牌/现房/优质楼盘推荐
  • 稀疏离散分数阶傅里叶变换的MATLAB实现
  • 2025 年导轨丝杆源头厂家最新推荐榜,技术实力与市场口碑深度解析的优质企业榜单东莞/直线/滚珠/孚雷导轨丝杆厂家推荐
  • Linux-简单命令 - 实践
  • far的数据类型
  • Zemax 2019下载地址与安装教程
  • 2025 年隔音门优质厂家最新推荐排行榜:覆盖剧院 /ktv/ 防火 / 实验室等多场景,解析实力口碑助您选对产品
  • 2024ICPC(济南站)
  • 事件在react中的处理方式?
  • volcano源码阅读——action/enqueue
  • 2025年工业大吊扇厂家权威推荐榜:大型厂房通风降温设备源头企业综合实力与客户口碑深度解析
  • 【左扬精讲】SRE 别慌!我用 故障预测与诊断,性能评估与优化,资源分配与规划 讲概率与贝叶斯算法的实战应用,都是咱运维人能懂的话(含代码)
  • 农经权报表生成小程序介绍
  • 【2025-10-16】移居香港
  • 学校社团招新的题目(莫队+树状数组统计区间逆序对个数)(蒟蒻被薄纱QAQ)