2025-09

2025-09-01

• A - AT_abc421_d - RLE Moving
  分讨
  1. 注意简化分类
  2. 将一些判断放在前面统一判断。
• B - AT_abc421_e - Yacht（！）
  记忆化状压期望
  1. 数据范围很小，实际上甚至跑不满。
     solution
• C - AT_abc421_f - Erase between X and Y
  链表+模拟
  1. 删除的个数始终不大于增加的个数。
  2. 若不确定两个数先后顺序，可以从两个数同时扫，时间复杂度无差别。
• D - AT_abc421_g - Increase to make it Increasing（！）
  网络流
  1. 对序列的增减性有要求考虑差分。
  2. 数据范围小且限制多考虑网络流。
• E - AT_abc420_f - kirinuki（！）
  笛卡尔树+组合数学
  1.
• F - AT_abc420_g - sqrt(n²+n+X)（！）
  简单数论/推式子
  1. 遇到多项式可以将变量全部丢到等号一边
  2. 因式分解不一定要完全严格分解，只要保证右边仍然是常数就可以配方。

2025-09-02

• A - P1314 - 聪明的质监员
  二分
  1. 绝对值可以拆成大于等于和小于
• B - P3128 - Max Flow P
  树上差分
  1. 对一条链进行加减修改考虑树上差分
  2. $\color{blue}{注意到没有更多操作，无需树链剖分}$
• C - P2569 - 股票交易（！）
  单调队列优化dp
  先考虑dp再思考如何单调队列优化
• D - P2254 - 瑰丽华尔兹（！）
  单调队列优化dp
  先考虑dp再思考如何单调队列优化
• E - P1600 - 天天爱跑步（！）
  LCA+桶+树上差分
  1. A 对 B 的贡献可以用 A 统计也可以用 B 统计。
  2. 树上一条路径对点的贡献可以尝试拆分为起点和终点的贡献。
  3. 子树的贡献可以考虑丢桶里回溯时统计。

2025-09-03

• A - CF2046B - Move Back at a Cost
  贪心
• B - P12598 - 参数要吉祥（！）
  莫队+值域根号分治
  1. $X$ 个不同的数和为 $N$，则 $X\le \sqrt{n}$。
  2. 数组大小 $10^5$ 区间查询（无修改）考虑莫队。
  3. 值域大小 $10^5$ 考虑值域根号分治。
• C - P12029 - Election Queries G（！）
  根号分治
  1. $X$ 个不同的数和为 $N$，则 $X\le \sqrt{n}$。
• D - P12030 - OohMoo Milk G（！）
  二分
  1. $(x^2)'=2x$，则一个数越大它的平方的增长速度就越大。
  2. 对于序列中最大的 $m$ 个数中选择任意个进行增加操作，那么最大的还是那 $m$ 个数。

2025-09-04

• A - AT_arc100_c - Or Plus Max
  1. $i | j\le K \to i | j = K\text{(前缀max)} \to i | j \in K\text{(同样满足条件)}$
• B - CF1208F - Bits And Pieces
  1. $x\& y\Leftrightarrow \overline{x}|y$。
  2. 求二进制的贡献可以按位考虑。
• C - CF165E - Compatible Numbers
  1. $x\& y\Leftrightarrow \overline{x}|y$。
• D - CF383E - Vowels
  1. 求满足某个条件 $\Leftrightarrow$ 求总数减掉不满足这个条件。
• E - CF449D - Jzzhu and Numbers
  1. 如果几个数中都含有S集合，那么这几个数的任意子序列，与起来的结果肯定包含S集合（即S的超集）。

2025-09-05