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

CF Round 1024 / CF2101

VP 的,但怎么 ABC 都是贪心 /kel

赛时 1.5h 过了 ABC,剩 1h 摆烂 / 写题解。

A. Mex in the Grid

不是,我随便搞搞然后就不知道为啥就过了?

就维护一个当且的子矩形,能在里面填就填,否则扩展短的那边。

然后这样会 WA on test 2,你每次扩展能扩充的位置最多的那边,然后就过了,我也不知道为啥。

B. Quartet Swapping

容易看出来可以奇偶分开做,但不完全,它们还是会有一些影响的。

一个显然的贪心思路是每次选最小的然后挪到前面,然后最后会剩 \(3\) 个数动不了,不管它,这样一定是最优的。

可以直接模拟,用链表 + set,但是这样不够好。

考虑更智慧的做法,直观的想法是奇数位和偶数位分开排序,但这样不完全对,因为最后会剩 \(3\) 个数动不了。事实上,容易看出只有 \(a_{n-2}\)\(a_n\) 这两个数需要处理。

邻项交换这类问题可以从逆序对数量入手考虑,你发现每次交换会让奇数位和偶数位的逆序对数量发生恰好 \(1\) 的变化,所以你可以通过逆序对数量的奇偶性来确定 \(a_{n - 2}\)\(a_n\)

感觉两种做法实现都不难,不过第二种做法实现更简洁一些。

C. 23 Kingdom

维护前后缀贡献,随便贪心就行。

D. Mani and Segments

发现最多有一个数既在 LIS 也在 LDS,于是枚举这个数,然后用脚维护。

我赛时发现了这个性质,但不是这么想的,冷静下来后才发现了这个思路。

然后用脚维护的细节还没想明白,等会再说。

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

相关文章:

  • 本地 Git 清理已经在远程删除的分支引用
  • 一切皆有逻辑,元推理框架是逻辑真相生成器
  • 2025 年工业减速机厂家最新推荐排行榜:聚焦谐波 / 行星 / 直角换向器等多类型设备,精选实力企业助力采购决策
  • 如何用有限元法,分析物体表面的张力?
  • 2025 年最新切割机厂家口碑推荐排行榜:全包围 / 半包围激光切割机及金属等离子切割机优选企业指南
  • Exp2
  • Hadoop RPC深度解析:分布式通信的核心机制 - 教程
  • 2025 运动鞋品牌推荐:从专业竞速到大众适配的全场景选择
  • 替代FTP文件传输工具有哪些?
  • 国产DevOps工具链崛起:Gitee如何重塑企业研发效能
  • PD快充诱骗电压芯片XSP25支持5V9V10V11V12V15V20V电压
  • electron——屏蔽顶部标题栏最大化按钮 - 前端
  • 2025 年折弯机厂家最新推荐排行榜:涵盖数控 / 电液伺服 / 液压 / 小型等机型,助力企业精准选购优质设备
  • 2025 年国内变压器优质厂家最新推荐排行榜:聚焦低压/单相/三相/特种/定制/非标/配电/节能/光伏/隔离变压器设备,助力用户精准选靠谱品牌
  • 数据安全交换系统是什么?有哪些核心价值?
  • 2025 年流量计厂家最新推荐排行榜:聚焦国内优质厂商,覆盖电磁涡街等多类型产品,助力企业精准选型避开风险液体质量/金属管浮子/液体涡轮/气体涡轮/旋进漩涡/空气流量计厂家推荐
  • 2025 年发电机组厂家最新推荐品牌排行榜:聚焦优质产品与服务,助力用户精准选购合适设备沃尔沃/移动拖车/静音柴油/集装箱发电机组厂家推荐
  • 2025石墨聚苯板源头厂家推荐榜,岩棉板/石墨保温板/EPS泡沫板公司推荐
  • Gitee引领中国DevOps市场的黄金时代:本土化创新与生态构建
  • 多智能体微服务实战(1/4):康威定律在 AI 时代的应用
  • 中国开源协作的数字化转型:从社区共享到智能工程平台的演进之路
  • 使用python将图像上传minio服务器
  • CDH 集群服务角色规划
  • 国产项目管理工具突围战:Gitee如何成为本土开发者的效率引擎
  • 基于Saleh模型的功率放大器参数辨识与曲线拟合
  • 2025 年防火涂料厂家最新推荐排行榜:膨胀型 / 非膨胀型 / 室内外 / 超薄型 / 厚型钢结构防火涂料优质企业精选
  • 【2025精选】如何选择跨网文件传输系统?5大核心指标要关注
  • res-downloader v1.0.6 资源下载工具:多平台视频 / 音频一键获取(支持 WinMac 系统)
  • c# HttpClient在自己服务器上访问第三方接口时出现HandshakeFailure的解决方案
  • 2025 年最新雕花板厂家推荐排行榜:聚焦金属 / 外墙 / 保温 / 隔热雕花板,助力采购方精准选优质品牌