20251127

· · 个人记录

T1### T1

首先，所有字母均满足要求的卡片一定可以直接放上去。

然后，所有非要求字母被挡完的卡可以放上去。

就变成考试n*m<=1e6的那道题了。

（以上为考场注释）

转化成以前的一道题。这是容易的。然后就做完了。虽然说绕了一步，但是其实能够接受。

T2

先搓了一个 O(n^2) 的启发式合并。

加了个小优化，\frac{n(n+1)}{2}。

加了个小剪枝，\frac{n(n+1)}{4}。

加了个小优化，\frac{n(n+1)}{9}。

优化不动了，特判了重复的询问。

过了。

注：赛后，chenyichen给出了证明，证明此程序是对的。时复为 O(n\sqrt n \log n)。

这告诉我们:赛时不要害怕，随便创就完事了。况且这份代码肯定可以拿75的部分分。

T3

最开始秒了树的解法，然后苦想100pts。

最后在想到T2的同时想到T3正解（只需要加一个缩点就行了）。

写完T2只剩20min给T3。然后我忘记tarjan怎么打了！！！！！！

复习了一下午的连通性问题。

  1. 复习了tarjan全家桶（边双，点双，强连通）
  2. 复习了边双的树上差分解法，作为备用。
  3. 学习了点双的树上差分解法，写了题解，作为备用。
  4. 复习了kosaraju，作为tarjan的上位替代。

T4

奇妙，只有我想到了 O(n^3) 没想到 O(n^2\log n)。

从 O(n^4) 优化到 O(n^3) 需要发现一个点只会更新一个答案。

我发现了，然后就忘记了这一点。

然后我考虑数据结构优化，但是