2022 年 11 月模拟赛总结
- 2022.11.1
T1 是一个利用性质暴力枚举。
factorial.in/out\to factoial.in/out，90 \to 0 /fn- （假如文件名没写错）没拍小数据，
n = 2 的 Corner case 也挂了，100 \to 90 /fn - 切记检查文件名！！！直接把 pdf 上的文件名复制过来以避免出错（当然要注意有没有空格）！！！
- 切记小数据对拍！！！对于
n 很小的情况一定要全部检查一遍看有没有 Corner case！！！
T2 是一个构造。
T3 是一个 P7113 [NOIP2020] 排水系统 的改编题目。
- 有亿点人类智慧，见题解。
T4 是一个离线 + 线段树上二分。
最终得分
- 2022.11.2
T1 是一个哈希。
- 把数据范围看清楚！！！
T2 是一个人类智慧题。
- 我认为其严格难于 T4，见题解。
T3 是一个 SAM + 树链剖分。
T4 是一个期望 dp。
最终得分
- 2022.11.3
T1 是一个最短路计数。
T2 是一个高精度。
- 好题，不过通过样例很容易看出结论，见题解。
T3 是一个 Nim 博弈 + 人类智慧 dp 优化。
- 原题为 P5970 [POI2016] Nim z utrudnieniem，见题解。
T4 是一个期望 + 二项式定理 / Min-Max 反演。
- 并不十分困难，但赛时没推出来，见题解.
最终得分
- 2022.11.5
T1 是一个贪心。
T2 是一个有向图上 dp。
T3 是一个背包 + 前缀和的简单计数。
这回又是998244853 （
T4 是一个 set 维护 dfs 序 + 整体二分优化有决策单调性的 dp。
最终得分
- 2022.11.7
T1 是一个简单计数。
这回变成了993244353 ，伟大的创新！！！
T2 是一个 Manacher + 线段树 /（二分答案 + ST 表）。
T3 是一个 dp + 二分最优解分界点 / 凸包。
- 存边数组的
cnt 没清空，30 \to 0 /fn - 切记多测清空！不管是变量还是数组！
- 套路题，但赛时没时间做了，见题解。
T4 是一个二分答案 + 01-Trie。
- 思维难度不是很高，但二分 mex 的套路还是有必要记录一下，见题解。
最终得分
三道可以二分的题，鉴定为 Um_nik round（
- 2022.11.8
T1 是一个贪心 / 数位 dp。
T2 是一个时间复杂度正确的小模拟 + 爆搜 + 概率。
T3 是一个 PAM（+ Hash）。
- 切记测试极限数据时不要直接在代码里生成！这样容易搞忘删！
- 回文串套路集合，见题解。
T4 是一个人类智慧的哈密顿回路相关的构造。
最终得分
- 2022.11.9
T1 是一个均值不等式。
T2 是一个最短路 + 倍增 + 二分。
T3 是一个交换状态与答案后决策单调性优化 dp。
- 原题为 [AGC033D] Complexity，见题解。
T4 是一个人类智慧分两段双指针优化 dp。
- 非常好的 dp，见题解。
最终得分
- 2022.11.10
T1 是一个简单计数 dp。
T2 是一个人类智慧构造。
- 我难以理解这个做法是怎么想到的，见题解。
T3 是一个容斥 + 压字符等价状态 + 计数 dp。
- 有趣的 dp，见题解。
T4 是一个平衡树维护置换环。
- 数据结构好题，见题解。
最终得分
T4 赛时暴力跳环可过（
- 2022.11.12
T1 是一个构造题。
- 比较有趣，见题解。
T2 是一个组合数 + 容斥。
- 不难但赛时没想到，见题解。
T3 是一个计数 dp。
-
把问题拆分为若干互不相关的部分。
-
dp 好题，见题解。
T4 是一个子序列自动机 + 类似于 DAG 剖分的东西。
- 有点难写，见题解。
最终得分
- 2022.11.14
T1 是一个质数相关的高精度。
- 数组开小，
100 \to 60 /fn
T2 是一个人类智慧 + bfs。
- 非常好的人类智慧题，见题解。
T3 是一个与 P3630 [APIO2010] 信号覆盖有关的计算几何。
- 数组开大，
40 \to 0 /fn - 见题解。
T4 是一个猫树分治 / 手搓逆矩阵 + 人类智慧。
- 两处数组开小，
60 \to 0 /fn 虽然但是，这是我第一次在赛时想到分治，可喜可贺（确信）
最终得分
感觉这场挺惨的。
一方面，是因为各种数组开小 / 大挂了
另一方面，是因为不善于观察分析 T2 这种偏人类智慧题目的性质。
但更多地，我感觉最近打模拟赛越来越懒得思考、懒得检查了。
有时候 AC 了一道签到题就溜去打颓或者补前面的题了——反正就是不想思考眼前的题。也正是因为这个原因，很多时候当我打模拟赛，若对一道题一开始几乎没有思路，就很难做出来，然后检查时也不仔细计算数组大小与空间大小。这在正式比赛里是极为危险的。
保持思考，保持认真，保持对自己的代码不信任的态度（即不要总是以为“这个哪里需要检查”等），这就是我当下最应该改变的一点。
- 2022.11.15
T1 是一个质数相关的诈骗 + 小分讨。
T2 是一个 cdq 分治优化 dp。
T3 是一个锦标赛排序相关的 dp。
T4 是一个 MST 相关的状压 dp。
- 空间算错，
100 \to 0 /fn - 倒着算，每次在最前面添加。这个思路很有趣，见题解。
最终得分 错失 AK 良机（
- 2022.11.16
T1 是一个博弈论。
- 原题为 [ARC143C] Piles of Pebbles。
T2 是一个 dp。
- 原题为 CF1699D Almost Triple Deletions，见题解。
T3 是一个 FWT。
- 原题为 CF662C Binary Table。
T4 是一个十分有趣的与树相关的计数 dp。
- 原题为 CF1034C Region Separation。有一个卡卡常才能过的做法，见题解。
最终得分
- 2022.11.18
T1 是一个爆搜 + 特判输出
- 原题为 LOJ3886 「eJOI2022」Game With Numbers。
T2 是一个基环树 + 环上模拟最大流。
- 有趣的，但是赛时没想到只需要在环上跑两圈就可以得出正确结果，见题解。
T3 是一个 CF1736C2 Good Subarrays (Hard Version) 的单点不撤销修改 + 区间查询版。
T4 是一个神奇的网格图上 dp。
最终得分
- 2022.11.19
T1 是一个 BIT 优化上升子序列 / 下降子序列计数。
T2 是一个大讨论 + 组合计数。
T3 是一个线性基 + 类似最小乘积生成树的凸包上分治。
T4 是一个人类智慧欧拉回路 + 差分约束 + 判负环。
最终得分
- 2022.11.21
T1 是一个类似后缀表达式的东西 + ST 表 / 递推。
T2 是一个二分 + 差分约束。
- 相当套路的题，但我差分约束搞忘完了。见题解。
T3 是一个二分 + 单调队列优化 dp。
T4 是一个并查集 + 启发式合并 + 二分 + BIT 维护区间哈希。
- 同样是一道相当套路的题，但赛时降智了没做出来。见题解。
最终得分
三道需要二分的题，鉴定为 Um_nik round（
- 2022.11.22
T1 是一个 Meet-in-the-Middle + 排序双指针。
T2 是一个前缀和优化期望递推。
- 在某一步没有思路时，打表找规律很重要。
- 期望好题，见题解。
T3 是一个点分治 + 并查集 + 树状数组。
- 数据结构好题，见题解。
T4 是一个人类智慧期望 dp + 容斥。
- 十分人类智慧的题，通过引入容斥系数解决 dp 时遇到的上限为
+\infty 的问题，见题解。
最终得分
- 2022.11.23
T1 是一个树状数组优化 dp。
T2 是一个 KMP 求所有 border + 哈希。
T3 是一个连通性相关的期望 dp + 容斥。
T4 是一个组合计数 + 莫队求组合数行前缀和。
题解中告诉我们这道题出自某篇洛谷日报。
最终得分