THUPC2025 初赛游记

· · 个人记录

前情提要

省流：成为高贵的负贡献选手。

开场肯定是先签到，irris 化身手速战神直接过了。之后开模三余一。A 不会，D 感觉很简单但不想写，G 是神必结论题想不明白，J 一眼树形 dp 板子，写写写。

过程中吃了一发罚时，同时 grg 抢到了 C 一血，这下高下立判了。好在最后还是过了。

发现 G 过的人比较多，开想。想了几个结论之后感觉不太对，但还是写了一下。稍微改了改代码，一发就过了。

决定写 D。先写了个 n\log n\log V 的做法，过不去（实际是有个死循环）。改成 n\log nV，两发罚时过了。队友过了 L。

grg 开了 A，我就去想别的题。排行榜说 F 和 K 不可做，B，E 和 H 可做，于是开 E。我不会，irris 也不会。和 irris 一起想 H。很快 irris 会了神秘分块做法，他就开写了。

经过了一些不太顺利的调试之后队友分别在 2.3h 和 2.7h 过了 A 和 H，同时我也开了 B。

很快写完了。第一发没过。（拍了 1e4 组数据）第二发没过。发现自己最大全 1 矩阵的做法有问题，在 grg 指导下学会了正确的做法。第三发没过。第四发没过。拍了 3e6 组数据无果。交了一发暴力直接 T 了。

这时 grg 让我检查一下自己有没有读错题意，真读错了我草。好在问题不大还有救，改改改，拍了 1e5 组数据无果，但第五发没过。

此时我让 grg 去回炉重造 B（别的题没人会），做到一半发现自己输出格式看错了。改回来就过了。

当时排在 10 题队伍中间（rk50 左右），最后半个小时慢慢掉到了 rk60，也变成了 10 题最前面那几个。

irris 冲 E 无果。倒闭了。

贡献：1（J）+1（G）+1（D）-1（B 只能算负贡献）= 2/10。

部分题目题解。按照过题顺序排列。部分题有一定口胡成分。

M

三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。

另解：发挥注意力。

C

(from Graygoo)

设 a 从小到大排序后结果为 b。

$n\ge 3$ 时，可以构造一种方案使得答案 $\le b_3$ 和第一步能走到的 $a_i$ 中第二大的值中较大者。 先用 $b_1,b_2,b_3$ 中一个替换掉一步能走到的地方的最大值，然后考虑对方的行动方式，优先堵它前面的那个位置，否则断它的后路，如果两个位置都被 $\le b_3$ 的数占据就堵上中间那一个，易证这样可以把波特堵死。 ### J 树形 dp。 $f_{u,0/1/2}$ 代表：$u$ 子树，不考虑 $u$ 本身合法性且随便放/放 $u$/不放 $u$ 但是放 $u$ 儿子的答案，转移显然。 ### I 注意到有效状态数相当有限，直接大力 dp 即可。 ### G 数一下两头都是 $W$ 和都是 $M$ 的段数 $A,B$，显然这玩意要求一个人比另一个人多花一步。 理论上如果 $A\le B$ 则 W 赢，否则 M 赢，但有个小问题就是如果 M 发现自己赢不了可以掀桌子把 W 和 M 都消完，就会平局。 考虑一下这样的可能，就是 $A=B$ 且存在一个两头是 $M$ 中间有 $W$ 的段。M 一直留着这个段不消，如果 W 来消相当于它浪费了一步这样 M 就赢了，否则到最后把一整段直接消掉。W 同理，这时要求 $A+1=B$。 ### L (from Graygoo) 最小割建图，把所有 $i$ 管辖的边并到一起。 但是这样的话就没法管一个点进去之后再往哪里走了，那会不会出现一个点进去之后从一个原图上到不了的位置溜出来呢？注意到所有（同一个公司管辖的）边都有一个公共点，所以不会出问题。 ### D 考虑先把所有 $a_i$ 降到 $[0.5,1)$ 以内，这个可以用 priority_queue 做到 $O(n\log n\log V)$。之后显然有一个长 $n$ 的循环节，结束循环之后用原来的 priority_queue 继续跑即可。 如果卡常的话可以用类似的方法找循环节然后做到 $O(n\log nV)$。 ### H (from irris) 用弹飞绵羊的 trick 分块。 路径上 $a_i$ 的和可以用 tag 解决，但弹的位置不太好直接搞。 注意到总的有效修改次数是 $O(n\log \log n)$ 级别的，所以只要有修改就暴力重构整个块即可。计算是否会有修改是简单的。 ### B 考虑一个矩形的移动，显然需要保证相同的东西是五个整行/整列的块，这个东西的预处理是简单的。 然后剩下的就是求一个 $01$ 矩阵最大的全 $1$ 矩形，这个枚举最上面一行和限制整个矩形的一列就可以做到 $O(nm)$，总复杂度 $O(nm^2)$。