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

CF2160 Codeforces Round 1058 (Div. 2) 游记

省流

以为开出 \(5t\) \(winwin\) 了,结果是数据过水惨遭轻松 \(hack\),打出表现分 \(1898\)

10.13

内含剧透,请vp后再来。

不是题解!!!!!!!

赛前

最近一周一直掉分,心态已经调理的足够平和了,赛前补了两篇游记就很正常的开始了这一把。对于两个半小时的比赛其实有点担心能不能抗住,毕竟一般我的有效时长也就 \(100min\) 左右。

赛时

先开 A 题,给定一个多重集,要求把这个多重集分成几个 \(mex\) 相等的多重集,问 \(mex\) 最小是多少。一开始凭借着直觉认为答案只有零和一,就只判断了最小值是不是 \(0\) 就匆忙的交了一发挂掉。仔细思考一下,发现 \(mex\) 要求相等所以其实分不分都一样,直接看本身的 \(mex\) 就可以了。
接着看 B 题,题目要求构造一个长度为 \(n\) 的序列,要求第 \(i\) 位的一个函数值为给定的数。函数是从 \(1-i\)\(2-i\) 直到 \(i-i\) 的这些集合中每个集合中不同数的个数之和。显然是要存一些前面的东西,然而大脑比较混乱,没有很好的想法也不是很想动笔写画,就先跳过看 C。
C 题要求你给出一个数 \(x\),使 \(x\)\(x\) 的二进制数倒过来,这两个数的异或结果为 \(n\),如果存在这样的 \(x\) 就输出 \(Yes\)。手玩一下发现要求 \(n\) 是对称的,于是写出测样例发现 \(6\) 不对,于是可以发现往前面填充 \(0\),然后发现 \(8\) 不对,发现正中间那个数不能是 \(1\)。于是交了一发就过了。
扭头回来看 B,推式子得到当前位置减增长量为同一个数,如果为零就多一个数,按这个模拟就行了。这个时候 \(31min\),分数不太好,毕竟中间跳了,第一题还吃了罚。
此时 \(Moemi\) 一直在旁边上压力,他写出 D 了说可以下班之类的,非常慌张了。于是接着 D 题,D 题有 \(2n\) 个数,\(1\)\(n\) 各有两个,每次可以询问任意个位置,程序返回给你这些数中出现两个的最大值,要求在 \(3n\) 次询问内给出整个序列。容易想到的是如果我们可以把整个序列分成两个没有重复的部分,那么每次拿一整段,对着另一段的每一个询问一次就能确定另一段的每一个位置都是什么数,于是考虑怎么得出一个没有重复的整段。然后想到我们可以直接一直往后查,每次多查一个数,如果重复了那么新的位置就是这个给出的数,否则加到不重复段中接着询问,这样 \(2n\) 次就可以得到一个不重复串和剩下每个位置。然后再 \(n\) 次询问把不重复串的每个和剩下的全部位置放一起得到的数就是不重复串每个位置的值。
虽然感觉很大可能基本下班了,不过秉持着坚持到最后(虽然最后也没坚持到最后)的思想,坚持看一下 E。E 题给了一个 \(01\) 矩阵,把 \(1\) 为四个角的矩阵内的点填这个矩阵的面积,每个点都取最小值,问最终矩阵每个点的值。\(n * m \leq 250000\)。看到这个数据范围容易想到把 \(n\)\(m\) 拆开,这样较小边最大就是 \(500\),可以考虑扫描线。假设行数较大列数较小,每行每行遍历,记录每列的两个点间上一次同时出现在第几行,然后把这行有的两列的点与之配对并更新,这样的时间复杂度是 \(O(n^2 * m)\),但是要考虑怎么更新矩阵内的值。我想能不能暴力更新,然后试了一下感觉可能是最坏情况的全 \(1\) 矩阵,发现复杂度还是这个值,于是大胆猜了一个结论是可以暴力,交上去过了。
F 和 G1 都简单看了一下,但可能是被虚假的胜利冲昏头脑了,F 没太明白,G1 想了一个 \(DP\),用了单调栈和线段树优化,发现复杂度还是太高,只好放弃了。

赛后

虽然还没打完,但是我一看后面题好像都写不了,就提前写这篇游记了。还想等打完了和别人讨(装)论(x)所以不能提前走人啊!
结果比赛结束被 \(hack\) 了,装 x 失败。
想了一下,如果只有第一行和最后一行全是一,那么就要在 \(n^2\) 个遍历中再去来一个 \(m^2\) 的遍历就挂了。然后看了题解,题解提到了 \(DP\),于是考虑怎么优化。发现对于一行中记录每一个 \(l\)\(r\) 区间内的最小值,就可以通过固定 \(r\) 增大 \(l\) 和固定 \(l\) 缩小 \(r\) 然后取最小值就可以在 \(O(n^2)\) 的复杂度内解决一行,记录 \(l\)\(r\) 的方法还是用刚刚的,把扫描线到当前行的 \(l\)\(r\) 的值都修改成这个矩阵的大小,这样每行的每个 \(l\)\(r\) 就最多被修改一次,时间复杂度就变成了 \(O(n^2 * m)\)

2025年10月13日

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

相关文章:

  • 2025年国内铝单板工厂推荐/国内铝单板厂家/ 市场铝单板推/公司榜荐
  • 一个老码农的掏心窝推荐:微擎,我后悔没早点遇到的开发利器
  • 国内铝单板工厂推荐/国内铝单板厂家/ 市场铝单板推荐:四川汇才铝业有限公司
  • 超景深显微镜厂家TOP10推荐:拓界光电引领精密观测新时代
  • 2025 闪蒸/流化床/喷雾/实验型喷雾/离心喷雾/压力喷雾/流化床喷雾/桨叶/盘式/真空耙式干燥机厂家推荐榜单:技术适配与场景落地能力成核心考量
  • 2025 年点胶机源头厂家最新推荐排行榜:自动 / 果冻胶 / 无痕内衣 / 烫钻 / 珠宝热熔胶等多类型设备优质企业精选
  • harbor 局域网https 自签名证书搭建
  • HyperWorks许可证使用报告生成
  • 2025年国内铝单板工厂推荐/国内铝单板厂家/ 市场铝单板推/公司权威排行榜荐
  • 小程序 拖动节点
  • ORA-00604: 递归 SQL 级别 1 出现错误 ORA-01000: 超出打开游标的最大数
  • Python的解释器
  • 10月13号
  • shiro快速启动
  • netty思维导图总结
  • gitreset、revert
  • 2025 年直流电弧炉厂商最新推荐排行榜:全面剖析优质企业技术实力与产品优势,助力各行业企业精准选购适配设备贵金属/节能直流/环保直流电弧炉厂家推荐
  • 2025 海外仓服务公司最新推荐榜单:含维修换标特色服务,三大优选品牌口碑解析美国/英国/德国/法国海外仓公司推荐
  • MaxKB 的 RAG 引擎和向量存储实现细节
  • 工业相机传感器CCD的原理及基础知识
  • ubuntu22.04安装激活Navicat15详细教程
  • 20232406 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • 经验再多,可能不如有个OCP证书好使
  • 2025 国内三效废水/多效废水/母液/废液蒸发器及三效/多效/单效MVR蒸发器厂家精选指南
  • 309、清平调三首其二
  • win11系统,右键新建记事本没有了
  • 高级语言-Lec2
  • 太强了!迅捷视频转换器一键搞定所有视频格式,还能剪辑加水印!
  • 2025 年变电站厂家推荐榜:撬装/移动车载/预制舱式/移动/预装式变电站厂家,聚焦技术与服务,助力电力建设高效推进
  • 2025 年建筑装饰材料优选:劈开砖 / 陶土砖五大靠谱厂家推荐,兼顾自然质感、长效耐用与多元场景需求