THUWC 2025 游记

· · 生活·游记

虽然说是游记，但其实还会记录很多东西，比如训练的内容。

本文下标以 0 开始，即 Day 0 指的是 2025.1.13。

另：我发现是不是因为我的游记前面内容太多所以没有人点赞啊/dk 大家点个赞满足一下我的虚荣心吧/ww

Day -11

晚上一放学拿到手机就得知可以查结果了。虽然之前已经觉得自己进的概率挺大的，但是打开界面的时候还是很忐忑。发现自己可以去了之后就非常开心了。

是人生第一次参加校营啊。不知道我的 OI 生涯还剩多久，不过这一次至少续上了十天的命。

但是无论如何能够翘掉期末考试还是很开心的！毕竟我之前几次考试都没有能发挥得特别好。

这次能去 THUWC 也是得亏 NOIp 保住了下限。CSP 真的打得太烂了所以去不了 WC，现在至少还能去一次 THUWC，也差不多吧。

所以我点了个疯狂星期四/zhq

Day -10

正式开始停课训啦。不用复习文化课还是很爽的。

今天先训一下之前的 THUWC 真题，感受一下题目的风格。

1. THUWC 2024 T1（的一部分）

首先，我们发现至多会选择 n 个人。n 这么小，肯定可以状压一下。我们可以扫一遍所有的 m 个人，同时设 f_{i,S} 为当前在看第 i 个人，且 n 个任务的完成情况为 S。这样很方便计算代价，因为我们可以钦定在放第一个任务的时候就给它扣掉代价。这样，就有一个朴素的 O(2^nmn) 的做法。这个做法过不去，但是好像还有个很强的 O(2^nm+3^n) 的做法，暂时还不会。

这段先鸽了。我们接着训 AtCoder 的题目吧。

2. ABC163E（*2037）

这个题的第一步关键在于想到这个贪心策略。我们考虑先把序列从大到小排序，依次填入新的序列中。可以先不把贪心策略完全确定，发现我们要填到的地方一定是当前新序列两端中的一个。然后考虑设 f_{l,r} 为左侧填到了 l，右侧填到了 r，就可以 O(1) 转移了。或者也可以反着做，也就是从小到大排序后，不断在原来的区间两端扩展，也是对的。总复杂度是 O(n^2) 的。

再训一个 *2000 就加点难度吧。

3. ABC350G(*2058)

这题很简单，做法都属于比较暴力而直接的类型。

根号分治

我们一开始认为可以 bitset 暴力冲对吧。但是你发现这个空间怎么是 256 MB，那就得爆了。但是注意到总度数是 O(N) 的，因此可以考虑设 B=\sqrt N，对于出度 \geq B 的点可以开 bitset，而剩下的可以暴力枚举。这样就完全能过了。

暴力根号

很经典的结论和做法。我们对于询问直接暴力做：先判断是否在同一连通块，这是为了方便记忆化；然后我们找到 u,v 中出度小的那个点，暴力枚举它的出边，看是否存在这样的点。显然可以记忆化，因为如果在同一连通块，那么答案就已经不会被后面的加边影响了。这样的做法复杂度是 O(n\sqrt n)，容易证明。

不过，这个做法比较依赖本题的很多性质，而且太典了，所以没啥意思。

启发式合并

这个做法的难点就在于你要想到这个算法。但是你又发现这个题目的模型真的非常 merge，所以其实没啥难度。那么我们考虑到如果存在一个点 x 满足条件，那它要么是 u,v 共同的父亲，要么是其中一个的儿子，另外一个的父亲。那我们其实只需要记录每个点的父亲就能做完了！如何记录呢？我们发现每次合并两棵树都需要改变其中一棵树的方向，也就是说里面每个结点的父亲都要变化。我们就可以选择修改大小更小的那棵树即可。于是就做完了。

根号重构

没啥意思。不想写了。

3. AGC014D(*2266)

发现自己几乎不会博弈论，这下这下了。还是多补一补这种能补的算法和内容吧。

这个题真的在我这种没见过什么 games 相关的题的人看来相当神仙啊。首先我们显然是不可能直接想到完美匹配的，但是可以逐步地通过观察样例来做，可以发现如果存在一个点，拥有至少两个叶子结点，那么如果先手染上它，后手必败；那我们接着考虑，判掉这一种情况之后，就会出现一些链。发现删掉这些链是不影响结果的，当然必须两个两个删。然后如果删光了那就没了；否则，如果删到了某个结点，那么它的儿子一定都是叶子结点，便可以继续按照这个思路进行判断。

但是貌似这个结论不够方便。我们考虑一个结点的每个儿子，能对它起作用当且仅当它的大小为奇数。这是因为如果是偶数的话，显然一棵树要么是有办法被删光的（完美匹配）；否则，这棵子树已经可以使得后手必败了。就非常简单了，只需要判断每个结点是否有 \geq 2 个子树满足大小为奇数，不要忘了加上自己上方的那棵子树（当然如果你一开始就把 n\bmod 2=1 判掉就不用了）。

思路有点 chaos，但是整体来说这种题目这么做其实很舒服啊（

4. AGC004D(*2346)

其实你想明白这个题目的要求之后就非常简单了啊。

我们发现，1 必须指向自己，否则要么它指向的点不能在 k 步后到 1，要么它自己不能。然后在这个基础上，由于题目给的性质，原图就成为了一棵树。然后我们考虑要做的就是修改一些位置，使得每个结点的 k-1 级祖先中至少有一个是 1，也就是每条长为 k 的树链中必须有一个 1。考虑贪心，显然是要从叶子开始做，如果当前结点的子树中深度最大的到自己已经有 k 层了就把它修改为 1，同时修改新的深度。

5. AGC013C(*2462)

这道题目我们可以先考虑链上的情况。于是发现每个点最终的相对顺序不会变化；可以假设当两个点相遇时，互相穿过了对方，只是交换了编号。那对于这个弱化版我们就做完了，这也是这道题目的一个非常精妙的地方。

但是如果是环上的话，我们无法确定 1 号点在哪里。如果有一个点逆时针经过了 0 到了负数（其实并非负数），那么对于最终结果而言它会被算大，也就是说 1 会被向后算一个，那么真实结果是 1 应当被往前算一个，而顺时针则相反。于是我们要干的就是统计有多少个点最终是穿过了 0 的，以及是如何穿过的。

统计这一点看起来非常困难，但是其实我们已经做完了这道题目最困难的部分。我们观察到并不需要考虑是哪个点穿过的，而且每个点以同一个方向只会穿过 0，穿过的次数也很容易计算。于是我们就能计算出最后的偏移值了。复杂度是 O(n\log n)，因为排序。

然后这个时候发现自己去不了 P 营，虽然原本也没想去来着。。不过下个赛季不能打得那么差了。

Day -9

今天上午看了眼 THUWC 2024 的工程题，感觉人机对抗很牛啊。不知道该咋训练这种东西的。还是先练 Day 1 的内容吧。

6. AGC002D(*2514)

又是很多做法的典题。

整体二分

我更喜欢整体二分这种做法。我们首先考虑对于单次询问的二分，如何 check？发现可以对于当前可以走的边用并查集全部连起来，然后看 x,y 是否满足在同一连通块且连通块内点数 \geq z。那我们就可以整体二分了。设 \text{solve(l,r,L,R)} 为对于 [l,r] 内的询问，其答案在 [L,R] 内。但是会存在撤销并查集合并的部分，因此并查集要用启发式合并，支持撤销。然后就能做了。

Kruskal 重构树

咕咕咕

Day -8

昨天咋这么摆？颓了 5h，CF 和 AT 都下大分。

真的清晰认识到自己手感还是很差，必须抓紧复建。

我们 vp 一场远古 ABC 吧。

ABC237

ABCD 一共吃了两发/yun/fad

E

这个题我一开始就无脑莽了个 dijkstra。。后来才发现没法这么做，SPFA 赛后被叉掉了。只能转化题意中的边权了。首先我一开始的思路是，既然题目中要求的是最长路（最大值），我们可以全部取反得到最小值，求的就是最短路。但是这个时候发现有负权边，考虑可以给每条边加上一些东西使得权值非负。但是这个时候我们加的东西必须存在一定性质（就是可求），否则没法在最后减掉它们。

我们注意到边权为负时，都是 h_v-h_u。可以考虑给每条边都加上一个 h_u-h_v，这样就避免了负权边，而且我们可以惊喜地注意到路径上的这些东西是可以相消的，最终只剩下了 h_1-h_i。于是就做完了。

这道题目确实很好玩啊。但是其实关键还是思路的引导性问题。

F

这看起来像是个 dp 套 dp，但是我不太会的。

考虑怎么求一个序列的 LIS？似乎有很多做法。

我们于是设 f_{i,v_1,v_2,v_3} 为前 i 个位置，当前三个值的情况为 v。转移非常简单，枚举一下当前这一位填什么，就能算出新的 v 了。复杂度 O(NM^4)。

写的时候有一点技巧就是可以把还没有答案的位置设为 M+1，这样就能自动更新了。

G

这个 P2824 之前做过的。。但是第一眼又没看出来。

你考虑区间排序操作还是太复杂了。考虑把 \geq x 的数当成 1，<x 的当成 0，用线段树来维护。然后再做一遍，把 >x 的当成 1，\leq x 的当成 0。这样只有一个位置会不同，就是 x 的位置。

Day -7

还有一周了。从今天开始不可以再颓废了。

早上先玩一场 ABC 236 吧。

ABC236F

好玩的线性基，是板板题。

当然还有一个不需要线性基的思路是，我们考虑至多选 O(\log n) 个数，可以在按照代价排序后从小到大取的同时，每次取都算出能得出的值；如果这个位置能更新值那就必须取，否则就只能被它所能更新的值更新，是不优的。单次更新是 O(n)，总复杂度不变。

ABC236G

这个所谓恰好 L 条边咋判断啊？不会做。

哎哟，这个判断不是很明显吗？？你肯定是考虑倍增做这个东西。

设 f_{i,j,k} 为 i\rightarrow j 走 2^k 步需要的最少操作次数，转移是容易的，类似于 floyd，可以在 O(n^3\log L) 的复杂度内完成。

现在考虑怎么把 L 拆位后拼起来。先设 g_{i,j} 为转移过程中，i\rightarrow j 的最小操作次数。对于每一位如果 L 为 1，那么可以进行转移，设一个临时 dp 数组 h_{i,j} 为这一次转移中的最小操作次数，那么 h_{i,j}=\min\{\max(g_{i,k},f_{k,j,x})\}，转移完了之后把 h 赋给 g 即可。复杂度不变。

一直没学会这个东西/ll 但其实挺简单的。

我们想到一个最暴力的 dp 转移方程：设 f_{i,j} 为从 1 开始走 i 步到 j 的最小操作次数，a_{i,j} 为 i\rightarrow j 的最小操作次数，那么 f_{i,j}=\min\{\max(f_{i-1,k},a_{k,j})\}，复杂度是 O(L\operatorname{poly}(n)) 的。那么我们发现这个形式非常矩阵乘法，即 f_i = a \cdot f_{i-1}，我们设这里的点乘为 C_{i,j}=\min_{k=1}^n \{\max(A_{i,k},B_{k,j})\}。

复杂度也是 O(n^3\log L)。

ABC236Ex

这个题也过于抽象了吧。其实每一步都没啥难度的，就是你得想到这一步。呃呃感觉是属于那种多练就会的题目。是不是我 NOIp 前多练这种题就可以 332 了啊？

但是这个题做不动了。先做会我存的陈年旧题吧，来源是【数据删除】，只挑有原题或者题意简单的写一写。

P6534

*2300

这个题首先你得把 dp 思路弄清楚。如果设 f_{x,l,r} 为结点 x 是否可以形成 [l,r] 的区间，显然状态非常冗余。我们考虑把状态缩成 L_{x,i},R_{x,i} 分别代表从 v_x 向左/右扩展可能得到的值，但是如何证明这两者是独立的呢？我们发现，x 的每一个儿子的连续权值都不可能跨过 v_x，那就是说每个儿子的子树都至多只会对 L,R 其中一个造成贡献，因此并不会相互影响。

现在，我们证明了 dp 状态的可行性，考虑如何转移。实质上要考虑的就是如何把儿子结点的合法区间拼在已有的合法区间的边上。我们先考虑更新 L_x。假设现在有 x 的儿子 y 满足 v_y<v_x，且有 R_{y,p}=1，也就是说 y 能拼出一个区间满足右端点为 p，那么这时如果我们经过前面的更新，已经可以拼出一个 L_{x,p+1}=1，就可以拼接上去了！还需要考虑的是如何处理更新顺序，发现需要从距离 v_x 最近的开始更新。对于 R 的更新也是同理。我们发现可以用 bitset 优化之，于是复杂度为 O(\displaystyle {nV\over w})。

P3070

*1900

看到 n\leq 15 肯定是状压。我们 O(R^2C^2) 地预处理一下每个位置两两之间的距离，可以使用 01-bfs。然后处理出连通块之间的距离，最后 O(n^22^n) 地 dp 一下即可。

所以这么简单的题为啥我前年不会做？

Day -6

【未知题号 1】

求逆序对数 \leq k 的长为 n 的排列有多少。n,k\leq 2000。

*2200

首先一眼是 dp。设 f_{i,j} 为前 i 个位置，逆序对数为 j 个的方案数。

我们考虑怎么转移。当决定第 i 个位置时，我们发现由于逆序对只会被大小关系影响，那就是说具体数值只会有 i 种本质不同的情况。

我们可以脑补一下这个离散化的过程，把前 i 个数看成一个排列。实际上，如果你在第 i+1 个位置填了一个 k\leq i，那如果我们把前面的在 [k,i] 的数都 +1 就可以使得它重新满足这一条件。

相当于，我们每一步插入一个数都只确定大小关系而非具体数值，这样到最后就自然获得了具体数值，而不会影响最终结果的方案数。

于是，我们可以直接把前 i 个位置当成 [1,i] 的排列。那么就可以考虑第 i 个位置放 j 的方案数，显然是会造成 i-j 个逆序对。

然后我们再枚举一下之前有多少逆序对，这样就是 O(n^2k) 的；前缀和优化一下就是 O(nk) 的了。

这个 trick 挺不错的啊。对于解决排列方案数状物确实需要很多特殊性质才好做。

HDU 6078

*2400

首先我们的暴力优化可以通过树状数组做到 O(n^2\log n)。但是其实原本的状态，即设 f_{i,j,0/1} 为钦定 a_i=b_j 为结尾的答案。

我们发现这玩意和 LCIS 其实是本质相同的。转换思路，设 f_{i,j,0/1} 为钦定最后一位是 b_j=a_k，其中 k\in[1,i] 的答案。然后就能更加方便地转移了，因为这样就使得我们在考虑转移前驱的时候只需要考虑 i-1 而不是 [1,i-1]。然后我们只需要在 a_i=b_j 的时候特殊转移一下，由于可以固定 a_i 所以对于当前这个 i 来说每个 b_j 的贡献情况是不变的。于是复杂度就是 O(n^2) 了。

HDU 4980

*2800

好玩的树形 dp。首先你考虑把这个题的模型抽象出来，就是用若干路径覆盖整棵树，看起来还挺经典的嘛。

然后我们考虑 dp 过程中，对于结点 x，考虑它的每棵子树被覆盖后，是否会对当前的位置有影响。于是有三种可能：

我们考虑设 f_{x,i} 为 x 子树有 i 个第三种情况的子树。但是我们发现一件事情，就是这种情况一定有 i\leq 2。为什么呢？因为一条边至多被 2 个人使用。如果被更多的人使用，那么不如进入这条边之前先走到另一个方向去再回来，是更优的。这一步可以感性理解。

那么我们考虑要做的就是让每棵子树的贡献信息进行匹配，要求剩下的 3 操作至多有 2 个。发现每棵子树会提供 1 或 2 条路径，而我们其实并不关心具体用的哪个，而是还可以留下几个。那么在每棵子树间再做一遍 dp 就好了。我们能这么做的原因是 k 的这部分贡献可以直接计算而不必记录。

唉但是这个题写的时候太唐了。我在中间状态 dp 的时候不仅额外开了个数组但其实本来可以滚动的，还开了双倍的状态用以表示是否有待匹配的。但其实你发现这个匹配的过程完全可以不用状态体现而在转移过程中直接给它做完。

也就是说，我们 dp 转移只需要枚举三维：之前待匹配的部分 i\in[0,2]，该子树提供的路径条数 j\in[1,2]，以及这次要匹配的个数 k\in[0,\min(i,j)]。不难发现我们一旦有 \geq 2 条路径就一定可以且必须匹配，否则剩下的就留作类型 3 上传处理了。那这一步就非常自然地做完了。

至于子树没有上传路径而只有一条出边待匹配的情况也非常好处理。我们可以在初始化 dp 数组的时候就允许 f_{x,0}=f_{x,1}=0，这样来说对于叶子结点就既可以算一条边也可以算没有上行边；进一步地，对于子树内已经可以完全覆盖的情况，例如一条链，就完全可以实现把一条边当成一条路径了。太强大了。我之前考虑的是直接把 f_{x,1} 向 f_{x,0} 取 min，看起来没问题但其实非常不自然。

怎么会有这么自然的转移思路啊。我之前写的那个玩意是啥啊真是，过于复杂且不优美了。

Day -5

越来越摆了。

vp ABC 235。B 居然吃了发罚时？？

ABC235D

这个简单题给我干蒙了。最后莽了个 dijkstra 还 RE 了一发。

ABC235E

一开始读错题目了啊。不过还是很简单的题目。

ABC235F

这个数位 dp 其实很简单，不知道怎么打到 *2129 的，可能是外国人都没有系统性训练过吧。

ABC235G

萌萌组合数学。O(n^3) 的 dp 是简单的，但是好像从这个方向走不太好优化的。

那我们还是考虑容斥，首先如果可以放空盒子，那么总方案数就是 \sum_{i=0}^A \binom{n}{i} \times \sum_{i=0}^B \binom{n}{i} \times \sum_{i=0}^C \binom{n}{i}。那如果我们钦定 i 个盒子是空的，其它随意，那么方案数就是

\sum_{i=0}^n(-1)^n\binom{n}{i} \sum_{j=0}^A \binom{n-i}{j} \times \sum_{j=0}^B \binom{n-i}{j} \times \sum_{j=0}^C \binom{n-i}{j}

但是这个直接算是 O(n^2) 的，咋办呢。我们发现把右边这个式子剥开之后，可以接着分离为 A,B,C 三部分的贡献，其本质相同。然后考虑到随着 i 的增加，\sum_{j=0}^A \binom{n-i}{j} 的变化其实是不难刻画的。

如果我们设 f(i)=\sum_{j=0}^A \binom{i}{j}，根据组合递推式 \binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}，我们有 f(i)=\sum_{j=0}^A \binom{i-1}{j-1}+\binom{i-1}{j}=2f(i-1)-\binom{i-1}{A}。这个为啥是对的呢？这个就等价于 \sum_{j=1}^A \binom{i-1}{j}-\binom{i-1}{j-1}，此时这个式子展开后发现可以临项相消了，最后只剩下 j=A 时的 \binom{i-1}{A}。

这部分推导也启示我们通过对组合式的变形和递推式的应用来构造新的递推方程。

那么根据这个玩意我们就可以先 O(n) 算一遍 i=0 时的第一项，然后后面的 O(1) 算出变化的量即可。总复杂度就是 O(n)，当然需要线性预处理逆元。

P7635

插播一个简单题，我觉得做题思路需要记录一下，但是实际难度可能只有 *1800。

我们考虑直接枚举或者二分都是没道理的，考虑刻画一下最终的结果，发现满足单调性的其实是前 K 个与后 K 个的中点。那我们就可以藉此找到所有的合法区间了，稍微维护记录一下即可。

ABC235Ex

突然发现自己怎么上一场的 Ex 还没补啊。咕咕咕。

这场怎么两个树形 dp 啊？没素质。

*2967，好难

首先跑一遍最小生成树是 trival 的，很明显不会影响最终结果。然后我就不会了。

Day -4

摆烂一整天。在此不表。

但是欢迎大家游玩 SCP:SL 谢谢喵！

Day -3

摆烂大半天。中午 vp 了一波，晚上来补题。

ABC234F

*1596，简单题

其实这个题场切了，但是还是很想写一下。额首先我们发现子序列没啥用，所以关键的东西只在于每个字符有多少个。然后就能 dp 了，预处理一下阶乘，根据经典结论做就好了，复杂度 O(n^2m)，其中 m 是字符集大小，本题中为 26。

ABC234G

*2306

这种题做不出来是不是可以去死了？我居然又去想那个板子的线段树优化 dp 题了。真是够了。

首先我们考虑拆贡献，把答案当成最大值 - 最小值。然后这个题的贡献形式是求和，所以不用线段树维护的。我们考虑算最大值的贡献，设 f_i 为前 i 个位置的贡献之和，那么 f_i =\sum_{j=1}^{i-1} f_j\times \max_{k=j+1}^i a_k，也就是要求以 i 为右端点的每个区间的最大值乘以 f_j。

我们考虑到每个位置的 f_j 是不变的，因此只要动态地更新它到 i 的最大值即可。显然我们要做的就是先找到从 i 往左第一个比 a_i 大的 a_k，那么 [k+1,i-1] 的最大值都要被改为 a_i，前面的不变。那么如何快速求新的贡献呢？显然贡献的增量就是 a_i\times \sum_{j=k+1}^{i-1} f_j 减去 [k+1,i-1] 原本的贡献。前者是很容易维护的，O(1) 地前缀和一下即可。但是问题在于如何计算这个区间原本的贡献呢？我们可以在单调栈维护前缀最大值的时候同时地记录这个区间的贡献，在被弹出的时候就把贡献去掉，最后新的 i 入栈的时候把整个区间的贡献加上即可。

这样就做完了，时间复杂度 O(n)。

这个题给我的一种启发就是，对于这种细节多的题目一定要屏去杂念和没有必要的部分，尽量减少需要考虑的细节，规约类似的部分，避免出错。例如这个题我们要分别地维护 max 和 min 贡献的前缀和，但是发现只需要记录单调栈需要的那一部分就可以了。

ABC234Ex

*2505

人类智慧题！我写了好久的乱搞但其实都没啥技术含量，只能过一半的 cases。但是随机旋转就能过了。

考虑一下正解。

平面分块

把整个平面划分成 K\times K 的正方形，(x,y) 属于 (\lfloor {x\over K}\rfloor,\lfloor {y\over K}\rfloor)，这样只存在相邻块的位置可能出现答案。然后暴力枚举即可。

推导一下

我们考虑这个式子 (x_p-x_q)^2 + (y_p-y_q)^2\leq K^2。不妨先考虑计算 (x_p-x_q)^2\leq K^2 也即 x_p-x_q\leq K(x_p\geq x_q) 的二元组数量，显然把序列按照 x 排序后满足条件的是一段连续的区间，可以双指针处理出来。然后再在这个区间内找满足 |y_p-y_q|\leq K 的，这个就是值域上的问题了，可以用 multiset 维护合法的 y 集合，通过二分找到 y 同样合法的区间，然后逐一判断即可。

分治

经典做法。我们只统计跨过区间中线的点对，显然不重不漏（虽然不重在本题没啥意义）。我们把 x 距离中线 \leq K 的点全部找出来，然后按照 y 双指针，同样地找到合法区间。和刚刚做法本质相同。

（补）ABC236Ex

235Ex 暂时不补了，因为暂时不想学新的东西啊。然后就认真学习了一下容斥原理。

那我们考虑原答案就相当于，有 \binom{n}{2}=n(n-1)/2 个条件，要求全不成立的方案数，那么显然可以容斥原理处理，若设 f(S) 为 S 内的条件成立，其余随意的方案数，那么总的方案数等于 \sum\limits_{S}(-1)^{|S|}f(S)。

考虑如何求 f(S)，相当于用并查集把无向图上的这些边连了起来，这样就有了一些连通块。那我们考虑如果此时有 k 个连通块，每个连通块。。。

补不动了。实力不够。

Day -2

又摆了一天。啥也没干。

Day -1

最后 vp 一场 ABC233 吧。然后就稍微补补题吧。

ABC233F

*2038

判无解是简单的，把连通块找出来看看其中现有的值是否匹配。然后我们考虑怎么操作比较合适。

如果我们对于每个位置 i，都把 i 暴力交换过来的话，似乎操作次数没有保证。但是可以尝试一下，因为貌似最劣情况（序列单调递减）的操作次数并不会超。

但是写假了！我忽视了一件事情，就是每次暴力交换是有后效性的。然后我们根据题解的思路在这个基础上进行优化，再通过随机化优化操作次数。

但是最后没调出来。难过了。

但是我们可以口胡一下另外的做法。

首先我们发现一件事情，就是对于每个连通块而言我们要做的其实就是排序。考虑做完并查集之后把这棵树建出来（其实就是把后面的边给去掉，容易发现不影响结果），然后我们考虑对于森林的每棵树，跑一遍 DFS，目的是对其进行排序：先对于每个结点的各个子树进行一遍排序，最后把当前结点的数交换到合法位置去。然后我们就会惊奇地发现，最后一步的交换操作本身并不会影响单调性。于是就对了。

这个做法本质上是充分利用了树的结构的特点，以及我们最终序列的单调性。

ABC233G

*2438

相当经典的题目啊。我们显然要先考虑 dp，设 f_{i,j} 为前 i 行 j 列的最小代价，可以考虑枚举 f_{u,j} 与 f_{i,v} 进行转移。然后就是要算一些子矩阵的贡献了。这样发现不是很舒服，所以我们不如直接设 f_{x1,y1,x2,y2} 为这一个子矩阵的贡献，考虑如何转移。

首先我们知道一个 n\times m 的矩阵，最大代价肯定是 \max(n,m)。而如果它可以从某条线分开的话，就可能有更加优秀的答案。但是如果不存在一条空的线，那么显然一定不存在更优答案了。O(N^3) 预处理之，就能做到 O(N) 的转移，总复杂度就是 O(N^5)。

ABC233Ex

*2530

不补了。没时间了。

Day 0

上午高铁睡大觉。

下午到 rdfz 报到了。年度新梗：我是 q-z！排了一个半小时的队才报到完，腿都快要站断了。在这期间面到了 i 宝，可爱捏。

然后就是试机。我比较弱智然后跑出校门去找高中楼。。然后最后试机就写了 200，T2 还 WA 了一发？攒 rp 了属于是。

然后去麦当劳面。结果最后来了一车的人，但是我社恐发作只能低着头对着手机看/ll 不过也换了一些徽章，还白送给了几个老哥。大家都好可爱！

然后打了把 uno，在外面合完影就被父母拉走了，没赶上徽章合影/dk

晚上吃了北京烤鸭。到宾馆也不想干啥了，再看去年的题感觉意义也不大？就看会电视睡觉吧。

希望可以考好一点。

在这里写一下 Day 1 的考试策略吧。这些内容都是依据历年的题目平均难度写的，所以不能犯下本本主义的错误。

首先一般认为只有 T1 是值得冲正解的题目。后面三道题可能有可做题，但是不要莽撞。由于 THUWC 题目的部分分一般只有最多四五档，而且很多题都是捆绑了子任务，所以需要考虑的乱搞不多。而且由于是 NOI Pretest 赛制，五十次提交基本上相当于 +\infty 了。所以子任务要好好写，以拿分为第一要务，不一定冲正解；即便第一题没有 AC 也不是大问题。

Day 1

这是 Day 2 写的。

反正很输吧。本来 T1 T2 都有机会做出来的。结果 T1 这么典的题目还是没想到点子上去。

感觉整体上就是一个做题思路不够流畅的问题，可能不只是不熟练，还有就是做题的时候不太会把握做法的方向和正确性，这一点本来可以更好的。

Day 1.5

嘉年华。在地下绕圈子。回宾馆。

Day 2

上午真是赤石了。这个题面真的太逆天了。

Codeblocks 的编译器坏了，所以只能直接提交测。前五个题做了 2 h，本来以为还不错，结果由于对于线性代数和矩阵乘法太不熟练，所以 T6 瞪眼 1.5 h 才看出个大概，一直就是卡在一个矩阵形状的问题上，没想明白怎么乘上去的。然后写完也没调出来。

然后就成功地被翻出了 Au。成为了高贵的 Ag 选手。

这里要恭喜 gza，颁奖的时候和他坐在一起，肉眼可见的非常开心。真的好可爱/tiao

不过是不是也不错了（）毕竟一半多的人都没有奖拿来着。

然后就是 THUSC 2025 努力吧。不过在此之前的省选，我还没想好目标是什么，也没想好该怎么准备。无论如何，时间不多了。