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

MX-X21

并没有参加 MX 比赛,这是一篇补题笔记。

T3

神人数据,一个显然假的贪心是从前往后能放就放,最后尝试将前后两端合并起来。

然后你会发现将近 50 个测试点还全是多测的情况下,我们仅仅 WA 了最后一个测试点。于是我们考虑将序列翻转做一遍,或者随机化选几个开头多做几遍我们就过了!

正解显然应该每次找最小值向两边拓展,但这样做显然比较困难,可能需要线段树带 \(\log\),但由于跑不满(没卡)所以能够在 \(n = 3e7\) 的时候通过!

怎么优化到 \(O(n)\) 呢,我们考虑只需要向左拓展到最远,那么拓展到的点一定是某一段的开头。而向左拓展的过程可以通过单调栈维护最大值最小值来达成。我们终于用正解通过了这个题!

T4

这个题数据很诡异。我只是漏了一个特判就被活活打断了双腿获得了 \(0\) 分。

首先如果全 \(1\) 或者全 \(0\) 是好判断的。

然后这种博弈题不妨找找必胜态或者必败态,玩一玩首先发现一个时刻连续 \(0\) 块和 \(1\) 块个数相同。接着发现当出现 \(10101010\) 时先手就输了。因为后手可以跟着先手拿的拿,这样最后一定出现 \(101\) 或者 \(010\) 的情景,这时候 \(1\) 或者 \(0\) 玩家连拿两个就赢了。

进一步分析我们发现,如果一个人拿完后同种颜色的块只剩一个则对手就赢了,所以每个人都要尽量不先拿完。所以每个人每次都只会取走一个,并且尽量不把一个块取完。

所以每个块对一个人的贡献是块长减一,由于两种块的数量相同,所以我们只需要判断 \(0\)\(1\) 的数量即可得到胜者。

当然我们需要特判一下,如果总共就只有两个块,那么先手直接拿完了,不需要判断了。

T5

其实这个计数真的很汤吧。但这场单调栈怎么出现频率这么高。

第一档分好做,对于第二档分我们手玩一下会发现对于一个序列中的点 \(a_i\),对于满足条件的 \((i, j)\)\(j\) 是满足单调性可以二分的。于是有 \(O(n^2\log n)\) 的做法。

到这里直接做就行不通了,考虑如何判定一个段的合法性(这里令第一位为 \(1\))。发现段中每次删除的 \(0, 1\) 数量都相同,于是我们需要任意前缀中 \(1\) 的数量大于等于 \(0\) 的数量。于是将 \(0\) 看作 \(-1\),求出前缀和。则 \((i, j)\) 合法当且仅当 \(\forall k \in [i, j] s_k - s_{i - 1} \geq 0\)。二分加上数据结构维护 \([i, j]\) 中的最小值即可判定。复杂度 \(O(n\log^2n)\)

但这么做其实比较蠢,我们从 \(n \to 1\) 扫然后用单调栈或者dan'diao维护一下即可。

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

相关文章:

  • Kubernetes Cilium网络组件和CoreDNS配置
  • 题解:P10107 [GDKOI2023 提高组] 树
  • Gitee Wiki:AI赋能的下一代研发知识管理平台如何重塑软件行业协作范式
  • COLMAP 安装在ubuntu20服务器上问题解决全记录
  • 完整教程:Prompt Tuning提示词微调工程
  • Autodesk Moldflow 2026下载地址与安装教程
  • 程序员利用Python分析股票赚钱,开发了股票行情看板
  • 9.26
  • K8S Deployment 学习
  • 全面掌握 Py2neo 与 Neo4j:从容器化部署到高级应用实战 - 详解
  • 原型
  • 集训队作业1——qoj#11722
  • 如何设置将浏览器网页临时禁用网页mathjax渲染直接查看latex编译前的文本
  • 《IDEA 2025破解 长效使用指南:2099 年有效期配置实战之JetBrains全家桶有效》​
  • Helloworld
  • 基于菲涅尔积分的角锥喇叭方向图计算
  • Flask的ORM工具SQLAlchemy
  • 使用 Rust 和 Tesseract OCR 实现英文数字验证码识别
  • 构建复合AI系统以实现可扩展工作流
  • Python HTTPS 爬虫实战,requests aiohttp Selenium 抓取技巧、HTTPS 问题与抓包调试(python https爬虫、反爬、抓包、证书处理)
  • GreatSQL 优化技巧:最值子查询与窗口函数相互转换
  • Windows Time 时间同步时出错
  • CCS开发环境和TMS320系列DSP实现IP-IQ谐波与无功电流检测
  • 多机动模型PHD滤波算法
  • Navicat17无限试用重置14天
  • 基于Electron的Web打印解决方案:web-print-pdf技术分享
  • CF455D Serega and Fun
  • 实验任务
  • 61.【.NET8 实战--孢子记账--从单体到微服务--转向微服务】--新增功能--提取金额 - 实践
  • 使用 Ansible 部署 Elasticsearch 集群