ICPC2024 Nanjing 补题

· · 个人记录

E. 签子，最多左移 7 位，模拟即可。

J. 签子，细节一车，分讨加好友的两个人有没有直接的回复关系即可，没有就是取俩最大值，有的话这样的数少，枚举即可。

K. 签子，没那么难写，按照黑块分区域处理，每个区域线贪心的用条子的左端点覆盖从左到右第一个还没盖住的红块，如果最后一条把黑块也盖了，那就从右往左贪心的每个条子尝试移动尽量短的距离。显然仍然合法，如果挪完以后最左边的条子盖住左端点黑块就寄了，否则就是一种方案。

为了处理方便把位置 0 和 w+1 涂黑。

B.

仍记得场上写了一坨不明物质，不知道怎么的就正攻（不使用偶数位取反）击破了，但是维护了 100w 个东西，细节多成史，场上能过真是奇迹。

你把偶数位反转，这样连续的 01 和 10 都能消。你发现如果确定了 2 的方案，最后一定会消到只剩一种数。不然两种数的连接处能继续消。所以你的 2 的目标就是要平衡两种数的个数，这样消得最多，剩的最少。

偶数位反转后统计 0,1,2 分别有几个，然后尽量用 2 去平衡 0,1 的个数即可。

G.

仍记得场上帮 djwj223 写了重心 tmd 写错了痛失 Au，还拼进新生赛里，把大伙创的不轻。

没啥好说的，淀粉质交互。因为二叉树，分讨重心子树个数：

C.

好啊好啊，场上最后一个小时狂干失败。原来是自顶向下做。

记 f_{u,x} 为除了 u 的子树里的点（不包括 u）都确定了相对顺序，且 u 在第 x 个位置的方案数。这个状态是没问题的，因为 u 的儿子们填进去只会填在 u 后面，不会影响 u 的次序。

考虑 f_{fa_{u},x} 转移到 f_{u,y}，考察转移系数。你发现只要把 fa_{u} 的除了 u 之外的其他子树填进去，把 u 放在第 y 个位置上就好了，所以 f_{u,y} 是把所有 x<y 的 f_{fa_{u},x} 把其他子树填进去的方案数求和。

只要 O(1) 算出 f_{fa_{u},x} 把其他子树填进去的方案数，这个题就做完了。这是好做的，你先算一个把所有子树填进去的方案，然后撤回某一个子树的方案即可。撤回的具体措施就是除掉这个子树本身的拓扑序数量，然后除掉把这个子树里的点填进 x 后面的 n-x 个位置里的方案数就好了。

如果你自底向上做，会郁郁症，复杂度 3 次方降不下去。但是自顶向下就能做，真神奇。

I.

min-max 容斥。先排序，从小到大填进去。

设 A_{1},A_{2},\dots A_{n} 为每一行被填满的时候的最大的值（即最后一个被填进去的那个数）；B_{1},B_{2},\dots,B_{n} 为 每一列被填满的时候的最大的值。那么一种方案的答案就是

\min(\{A_1,A_2,\dots,A_n\}\cup\{B_1,B_2,\dots B_n\})\\=\sum_{S\subset\{A_1,A_2,\dots,A_n\}}\sum_{T\subset\{B_1,B_2,\dots B_n\}}(-1)^{|S|+|T|+1}\max(S\cup T)

你发现这个 \max(S\cup T) 在做的事情就是选定某些特定的行和列，求出这些格子里最后被填进去的数是什么。容易发现这个值只和被考虑到的格子数量有关，而这个格子数量只和 |S|,|T| 有关。因此我们可以改写这个式子为：

\sum_{i=0}^n\sum_{j=0}^m(-1)^{i+j+1}\binom{n}{i}\binom{m}{j}f(im+jn-ij) 这个式子复杂度已经对了，现在唯一的问题是算 $f(t)$。考虑枚举最后一个填进去的数是什么： $$f(t)=\sum_{i=1}^{nm}a_i\binom{i-1}{t-1}t!(nm-t)!$$ 这个式子的意义就是第 $i$ 个数是最有一个填进去的，前 $i-1$ 个数里挑 $t-1$ 填到剩下 $t-1$ 个格子里，这 $t$ 个数和剩下的 $nm-t$ 个数分别可以随便排序，所以乘上阶乘。 这个式子可以差卷积。做完了。 ### F. dij 起手，状态设成 $(i,j)$，第 $i$ 条线上的点 $j$，考虑换乘点怎么优化转移。 对于一个点 $u$，按照 $b$ 排序，每次队首取出的状态如果是 $u$ 上的点 $(i,u)$，那么会对这些和 $u$ 相关的状态做一个 $dis_{j,u}\leftarrow\min(dis_{j,u},dis_{i,u}+a_{i}b_{j})$。你发现如果把 $(b_{j},dis_{j,u})$ 撒在坐标轴上，这个式子就是给和 $u$ 相关的状态做一个 对直线取 $\min$。 总体来说，这个题暴力做的复杂度在于这个对直线取 $\min$ 的操作暴力枚举复杂度是炸的。但是你发现一个点的最短路只能来源于：1. 这个点上另一条地铁线路给他搞了一个直线 $\min$；2. 同一条线路上上一个点直接走向他。来源于 1 的点值可以每个点掏一个李超树维护，2 直接维护即可。现在的难点变成了怎么在有 1 的情况下快速判断现在的的队首是谁。 建立一个优先队列，存 2 来源的最短路；再搞一个 set 存那些 `还未被 dij 以队首取出来过的点` 的点值。如果取队首的时候发现 set 里的最小值比队首小，那就取 set 里的那个。 显然加直线的时候 set 没法全部维护，所以对于每个点 $u$，我们只往 set 丢这个点下 $b_i$ 最小的那个（这个必然是直线 $\min$ 最小的那个），然后动态维护即可（被遍历过了就在 $u$ 相关的状态往后枚举更新）。 李超树疑似有点变态了，其实可以维护 $\min$ 凸壳。这样好像会多一只 $\log$，但是两只 $\log$ 而且其实是跑不满 感觉难写的要死。