THUPC 2025 单开记

Day -?

问了一下一起训练的人，没一个想打/来打的。

于是喜提一缺二。

队名：1v3er

Day 1

0:00 开始！

一眼丁真 M 是签到，0:01 过了。

之后就完全是跟榜了。

然后随机扫了几眼题，看到 C 有人过，就去看 C。

想了几分钟得出结论是 \(\max(\text{全局第 3 小},\text{和 }a_x\text{ 相邻的数中的第 2 小})\)。

然后因为第二小写成第二大而挂一发。0:17 改完过了。

然后发现好几个题都有人过了。随机想了一会题。

这个 L 为啥几分钟就有人过了？为啥我一点不会？

发现 J 是「与黑点相邻的点至少与一个白点相邻」。这不直接瞎树形 dp 吗。

写完发现 WA 了。然后发现我 dp 的东西根本不是我设的状态。0:43 改完过了。

然后看了一眼 I。这不直接 \(\Theta(11n)\) dp 吗。

然后因为「打了 \(2\) 局比赛，比分是 \(10:10\)」这种 corner case 而 WA 了一发。0:55 改完过了。

为啥我还是不会 L 啊？？？看着像 \(\Theta(\frac{n^2}w)\)，但是我连个 P 都不会？

看 D。发现 \(\Theta(n\log W)\) 次分配之后一定会变成 \(n\) 个人轮流拿。

那不是直接上个 pq 就行了吗？

01:25 过样例，发现 WA 了。发现中间运算可能爆 long long。改成了 __int128。然后 TLE 了。

我就知道俩烙鸽过不去。。。

发现有单调性，可以把 pq 换成三个 queue，分别维护拿到 \(0\)、\(1\)、\(\ge 2\) 个的人。改改改，然后又写挂了两发。1:48 过了。

现在还剩 A, G, H, L 几个题过的人比较多。

H 是大 DS，我一个人怎么可能写的动，暂时扔掉。A 题看着是神秘 DP，G 题是神秘博弈论，L 不知道。

决定想 L，然后转成了另类最小割，然后转成了二分图最大独立集。

不是哥们，你 \(\Theta(n)\) 个点 \(\Theta(n^2)\) 条边（尽管可以缩起来）的图，跑牛魔匈牙利啊？

然后愣了整整几分钟：WC，这不是直接 Dinic 没了吗？

偷了个 Dinic 板子，然后 1A 了。此时是 2:34。

看了下 G 过的人最多，遂看 G。这真好做吗？

感觉需要直接想策略。然后推了半天，推出了一个看起来不太真的策略。

写了一下，过样例了，奶了一口会 WA，交上去，过了！此时是 3:39。

最后 80min，决定冲 A。

想了半天才转化成区间 dp，然后发现是 \(\Theta(n^5)\) 的。虽然带了 \(\frac 1{12}\) 的常数但显然是不可能过 \(150\) 的。

组合意义感觉优化不动，有点急了，列出了转移方程，发现可以提出一个东西出来，然后就 \(\Theta(n^4)\) 了！

开写，4:53 过了样例，提交，AC 了！

剩 7min 肯定啥也干不了了，遂摆烂。

---

最终战绩为 8 / 17:14:16 / rk156。

感觉作为单挑这个题数已经不少了。如果来一两个水平差不多的队友可能就能进决赛了。

H 题看着吓人，实际上可以简单地发现 next 的总变化不超过 \(\Theta(n\log n)\)，可能也没那么难？

总结：明年得凑齐必有我师焉再打。