死掉了

20231105 MXNOIP#17

赛时笔记：

Imbalance

14:27 边分治之后变成二维偏序 $O(n \log^2 n)$ 不知道过不过得了。

原子

14:20 直接贪大概是对的。

旅行计划

15:17 大概是换根 dp。

简单题

15:15 神秘数论最后再做。

开题顺序：BACD。

得分：$70 + 100 + 0(100) + 0 = 170(270)$。

总结：T3 差一分钟没交上去，而且写 T1 写太久了，如果先写 T3 可能会更好一点。顺带一提，T1 是我没做的之前模拟赛的原题。

20231106 TYNOIP#47

赛时笔记：

登山

9:04 直接贪。

蝴蝶变换

9:24 可以 $3$ 次操作分开奇偶位。

9:26 摆了。

爬梯高手

9:43 $f_{i, S}$ 表示第 $i$ 层 $S$ 集合内的点往后最多可以走到多远，转移是一个二分图完美匹配判定问题，考虑 Hall 定理。

10:03 考虑 $S \to T$ 的转移，$f_{i + 1, S}$ 能转移到 $f_{i, T}$ 当且仅当 $|S| = |T|$ 且：

$\forall T' \subseteq T, \left|S \cap \left(\bigcup_{v \in T'} r(v)\right)\right| \ge |T'|$

那就相当于有一堆形如 $|U \cap S| \ge x$ 的限制 $(U, x)$。

Border 的第六种求法

没开。

开题顺序：ACB(D?)。

得分：$100 + 20 + 80 + 0 = 200$。

总结：T3 没想到转最小割，太蠢了。T2 是神秘题，幸好没开。T4 是字典，真的会出。校内 rk1 联测 rk6 好高兴。

20231108 TYNOIP#48

赛时笔记：

dp

10:50 太神秘了先放着。

线段树

7:47 操作四可以变为整体加上 $k$，然后 $[y, n]$ 加上 $-k$。然后操作变为整体加，询问区间加，扩张询问区间，清空区间。

7:54 询问区间 $[0, y - 1]$ 相当于询问 $\min([0, x], [x + 1, y - 1])$，询问区间 $[x + 1, n]$ 相当于询问 $\min([x + 1, y - 1], [y, n])$。所以我们只需要维护 $[0, x], [y, n], [x + 1, y - 1]$。

7:57 前两者是容易维护的，打个加法 tag 即可。后者不好维护，相当于是删点求 $\min$，但是我们留意到这个区间在每次重构之前是不会受到两边操作影响的，所以离线下来改成加点求 $\min$ 即可。

8:00 最后清空的时候直接暴力加到原序列上即可，均摊时间复杂度是正确的。

博弈论

没开。

图论

没开。

开题顺序：B(ACD?)

得分：$0 + 0(100) + 0 + 0 = 0(100)$。

总结：T2 卡了半天空间还是没卡进去，T1 结论题，不知道开了的话猜不猜的出来。T3 T4 都比较困难，主要还是 T2 做太久了。每次重构取中点一个 $n + \frac n2 + \frac n4 + \dots$ 的东西我以为是带 $\log$ 的，真的太聪明了。