HDU 多校 2022 比赛记录

队友 C 和 R，Team 441。 ### HDU 多校 1 #### 比赛记录 比赛前约定好我看模 $3$ 余 $0$ 的题，R 看模 $3$ 余 $1$ 的题，C 看模 $3$ 余 $2$ 的题。 开场看 03，想了一会后秒了，9 分钟过了。 C 在 12 分钟的时候过了 02，一血。 跟榜后发现 11 才是签到题，结果因为模数打错 WA 了一发，顿时感觉自己在演。 C 猜个结论过了 12。 开场巨大优势，一度登顶好长时间。 看 09 计算几何没啥思路，丢给 C，C 秒了，37 分钟过了。 我看 01 直接秒了。因为细节巨大多写了一年，还挂了，写个对拍调了一会，过拍交上去还是挂，很疑惑。 C 秒了 04，太恐怖了。 我一边拍 01 一边看 08，发现是 Dijkstra 裸题，特殊边用 `set` 维护。写完测样例，发现注释掉了 `ifdef ALEX_WEI` 和 `endif`，点开 01 一看发现也注释掉了，顿时感觉自己在演。 01 关掉文件后过了，08 调了两分钟交上去也过了。 两个小时 C 手上有 07，我看 06 发现是莫反树 DP 裸题，不懂啊，为啥过的人这么少。 C 在 127 分钟过了 07，我在 159 分钟过了 06，一度登顶。 现在还剩 05 和 10，05 是大模拟，10 看上去像毒瘤多项式或者线性代数。我和 R 同时写大模拟，以防万一，C 想 10。 我和 R 几乎同时写完了 05，交上去一个 WA 一个 RE，蚌埠。我使用瞪眼法一直没调出来锅，发现榜上已经有队伍 AK 了，C 帮 R 调锅，发现他拓扑排序写成 `while(que.empty())`，改掉就过了。 当时排第四，成七 AK 了一个队伍。到比赛结束 10 都没啥想法，又 AK 了两个队伍，都是 11 题排我们前面的，所以排名没掉。 ### HDU 多校 2 #### 比赛记录 开场一个小时 R 过了 07，C 过了 02，11 和 03，我过了 09 和 12 和 01。01 虚树清空有问题 WA 了两发，栓 Q，我真的会谢。 C 说 10 是全局最小割板题，写完交上去 WA 了，写个拍调了 20 分钟过了，还是一血。 我写 08，$\mathcal{O}(n|\Sigma|\log n |\Sigma|)$ 结果 T 了，复杂度瓶颈在预处理，很自闭。C 过了 10 后帮我卡常，倍增表只预处理到 $\log $ 该字符最长连续段长度，交上去 WA 了，没 T。调了十分钟发现循环边界挂了，改了过了，顿时感觉自己在演。 没多久 C 过了 05，太厉害了，现在只剩 04 和 06。 R 一直在写 04，交上去莫名奇妙 WA。我和 C 研究 06，我没啥头绪，他很快想出来 $\mathcal{O}(TNMK\log)$ 的二分做法，写完发现 T 了。猜了个凸性，加了点剪枝跑的飞快，交上去过了。 我和 C 一起看 04，发现 R 用 `scanf` 读 `long double`，哈哈。改掉就过了。 好像 AK 了，还是第一个，非常感动。 因为罚时原因在比赛结束时掉到了第四。 #### 1001. String 难度：Easy-Medium，赛时 125 AC。 根据 border 论，不小于串长一半的 border 长形成等差数列，因此它们重合部分的长度也是等差数列。容易用 KMP 将问题转化为求 $di + r \equiv 0\pmod k$ 且 $0\leq i \leq R$ 的 $i$ 的数量。 若 $\gcd(d, k) \nmid r$ 则无解，否则同除 $\gcd(d, k)$ 得 $d'i + r' \equiv 0\pmod {k'}$。$d' ^ {-1}$ 存在，解同余式 $i\equiv \dfrac{-r'}{d'}\pmod {k'}$ 即可。 时间复杂度 $\mathcal{O}(n\log n)$，需要卡常，[代码](https://vjudge.net/solution/37590433/AU2a0vxESCACkjlGP0dD)。 EXKMP 求出 $z$，则 $z_i$ 的贡献形如给所有位置 $i + (i - 1 + ck) - 1$ 满足 $c\geq 1$ 且 $i - 1 + ck \leq z_i$ 的 $F$ 加上 $1$，差分即可。 时间复杂度 $\mathcal{O}(n)$，不需要卡常，[代码](https://vjudge.net/solution/37590679/Q5fU3gQrlFNYtiq2LLo8)。 #### 1002. Dragon Slayer 难度：Easy，赛时 473 AC。 ### HDU 多校 3 #### 比赛记录 今天是 Claris 场，听说难度很大。 开场点开 03，09，12 发现全是签到题，20 分钟全过了。 C 写 11 $2\log$ 被卡常，$1\log$ 还是 T 了，快读换成 `scanf` 就过了，很离谱。 02 也是签到但我假了，没注意到伤害可以叠加，丢给 C 之后很快过了。 R 开场开始写 01，写完交上去 WA，我看他代码发现有个地方没开 `long long`，改了过了。 看 08 发现是三维计算几何模板题，找 R 要了计算几何板子，$n ^ 4$ 写完发现 T 了。R 帮忙卡了卡常过了。 C 看 06，区间最小圆覆盖，但是数据随机。他以为维护凸包要树套树，所以选了 $64$ 个方向上最远的点跑最小圆覆盖，结果 WA，换成 $128$ 个方向结果 MLE，`double` 换成 `float` 过了。 C 看 05，我和 R 研究 04。 C 觉得 $2 ^ m$ 随便剪剪枝就能过，WA 了一发，调了一会过了。 我和 R 只研究出来 $3 ^ n m$ 感觉过不去，C 说常数可以除掉 $3$，让 R 先写一发暴力。本地单组极限数据只要 7s，但是交上去 T。 HDU 单组数据 12s，R 注意到只需 OJ 二分套出一组数据的答案（两个 $998244353$ 以内的数）就能过。套了一个小时终于过了，罚时 46 发，感觉出题人要看傻掉了。 R 套数据时我看 10，C 看 07。他觉得 07 是简单题，写完调到比赛最后几分钟，过拍但是 T，很可惜。 我对 10 没啥思路。 因为罚时巨大多所以同题数垫底，第六。 #### 1001. Equipment Upgrade 难度：Easy-Medium，赛时 115 AC。 #### 1002. Boss Rush 难度：Easy-Medium，赛时 246 AC。 直接 DP 不可行，因为无法处理伤害重叠。 考虑二分时间 $T$，设 $f_S$ 表示使用集合 $S$ 的技能在 $T$ 时刻前造成的最多伤害，转移枚举 $i\notin S$，则 $f_{S\cup \{i\}} \gets \max(f_{S\cup \{i\}}, s_{i, \min(len_i - 1, T - V_S)})$，其中 $s_i$ 是 $d_i$ 的前缀和，负数下标视为 $0$，$V_S$ 表示 $\sum\limits_{i\in S} t_i$。 时间复杂度 $\mathcal{O}(2 ^ n n\log V)$。 #### 1003. Cyber Word 难度：Easy，赛时 1189 AC。 签到题，根据题意模拟即可。 #### 1004. Divide the Sweets 难度：Hard，赛时 7 AC。 #### 1005. Spanning Tree Game 难度：Medium，赛时 40 AC。 #### 1006. Dusk Moon 难度：Medium，赛时 32 AC。 随机数据下单调栈期望大小 $\mathcal{O}(\log n)$，使用线段树维护单调栈，将四个方向上单调栈内所有点拿出来做最小圆覆盖即可。 时间复杂度 $\mathcal{O}(n\log ^ 2 n)$。 #### 1007. Shallow Moon 难度：Hard，赛时 1 AC。 要利用好所有正方形 $w, h$ 均相同的条件。 考虑按每 $w$ 行一块将 $m\times m$ 的网格分成若干 $w\times m$ 的子网格。因每个矩形行高均为 $w$，所以一个长方形对子网格第 $b \sim b + h - 1$ 列的限制形如顶部若干行被覆盖或底部若干行被覆盖。 不妨设当前处理的子网格对应原网格第 $c \sim d$ 行，则找出所有 $(a, b)$ 满足 $c\leq a\leq d$，则 $(a, b)$ 带来 $b\sim b + h - 1$ 列底部 $d - a + 1$ 行被覆盖的限制；找出所有 $(a, b)$ 满足 $c\leq a + w - 1 \leq d$，则 $(a, b)$ 带来 $b \sim b + h - 1$ 列顶部 $a + w - c$ 行被覆盖的限制。 因此，每一列要么完全被覆盖，要么未被覆盖的行数形成一段区间。使用上下两个单调队列求出每个极长的未被覆盖的行区间相同的列区间未被覆盖的行区间，得到若干未被覆盖的矩形。 总共 $\mathcal{O}(n)$ 个矩形，两个子网格上下相邻的矩形之间连边，双指针实现；每个子网格左右相邻的矩形之间连边。求出所有连通块矩形面积和的平方和即为答案。 注意需要将极长的未被任何矩形覆盖的行区间统一处理，视为一块大矩形，否则复杂度退化为 $\mathcal{O}(\frac m w + n)$。 时间复杂度 $\mathcal{O}(n\log n)$，复杂度瓶颈在排序。[代码](https://vjudge.net/solution/37420919/QIzVXVnRnACsk9hi88L2)。 #### 1008. Laser Alarm 难度：Easy-Medium，赛时 131 AC。 本题难点在于准备一个封装好的三维计算几何板子。 假如最优平面不经过至少三个端点，总可以调整使得它经过至少三个端点。因此，枚举任意三个两两不属于同一线段的端点，检查它们构成的平面经过的线段个数。三点共线时一定不优，跳过。注意无法选出不共线三点时答案为 $n$。 时间复杂度 $\mathcal{O}(n ^ 4)$。[代码](https://vjudge.net/solution/37421074/brVSKHXAngmqvpIi7mLW)。 #### 1009. Package Delivery 难度：Easy，赛时 667 AC。 时间越靠后，可以拿的包裹越多，因此考虑在最早的 DDL $\min r_i$ 时去邮局拿走尽可能多的包裹。除了拿走已经到 DDL 的包裹以外还可以拿走 $k - 1$ 个包裹。贪心拿走 DDL 前 $k - 1$ 早的包裹即可，问题递归。 用 `set` 模拟，时间复杂度 $\mathcal{O}(n\log n)$。[代码](https://vjudge.net/solution/37421084/nth7cJDogRYVXRkbt9BI)。 #### *1010. Range Reachability Query 难度：Medium-Hard，赛时 3 AC。 DAG 任意两点可达性只能做到 $\frac {nm}{w}$，因此本题时间复杂度不会低于这个值。 拓扑排序不能进行 $\mathcal{O}(q)$ 次，必须对每条边 $(x_i, y_i)$ 预处理它和哪些询问有关，设为 $S_i$。考虑一次拓扑排序求得所有答案。 可达性信息的类型应与 $S_i$ 匹配，使得转移形如对应位上的位运算。因 $S_{i, j}$ 表示第 $i$ 条边是否属于第 $j$ 组询问，故 $j$ 这一维的类型为询问，因此设 $f_{i, j}$ 表示第 $j$ 组询问能否由起点 $u_j$ 到达 $i$。 拓扑排序，每条边 $(x_i, y_i)$ 的转移形如 $f_{y_i} \gets f_{y_i} \lor (f_{x_i} \land S_i)$，回答第 $j$ 组询问检查是否有 $f_{v_j, j} = 1$。 $S_i$ 的空间复杂度为 $\mathcal{O}(\frac{mq} w)$，无法承受。考虑每 $B$ 组询问打包在一起处理，则 $j$ 这一维大小为 $B$。$B$ 太小则常数过大，取 $B = 2.5\times 10 ^ 4$ 加一些常数优化可以通过。 时间复杂度 $\mathcal{O}(\frac {(n + m)q} w)$，[代码](https://vjudge.net/solution/37421101/qLldujv93YcQ29QwE7LQ)。 #### 1011. Taxi 难度：Easy-Medium，赛时 213 AC。 答案为 $\max\limits_{i = 1} ^ n \min(|x_i - x'| + |y_i - y'|, w_i)$，尝试独立给定点和询问点。根据 $|a - b| = \max(a - b, b - a)$ 将绝对值符号去掉，再根据 $\min$ 对 $\max$ 的分配律，得 $\max\limits_{c = \pm 1, d = \pm 1}\min(cx_i + dy_i - cx' - dy', w_i))$。 至此，将 $(x_i, y_i)$ 按照 $w_i$ 从小到大排序，维护 $f_{c, d}$ 表示 $cx_i + dy_i$ 的后缀最大值。回答询问只需二分出 $w_i$ 与 $\max(f_{c, d} - cx' - dy')$ 的分界点。时间复杂度 $\mathcal{O}(n\log n)$，比较卡常。 从切比雪夫转曼哈顿角度入手可得本质相同的做法。[代码](https://vjudge.net/solution/37421133/f3XABJIu2tAkQiapJ2tL)。 #### 1012. Two Permutations 难度：Easy，赛时 516 AC。 相当于求 $S$ 扣出一个子序列等于 $P$，剩下部分等于 $Q$ 的方案数。设 $f_{i, j}$ 表示 $S_i$ 匹配 $P_j$ 的方案数，因为是排列，所以 $j$ 只可能等于 $P ^ {-1}(S_i)$ 或者 $i - Q ^ {-1}(S_i)$。 因此，设 $f_{i, 0 / 1}$ 表示 $S_i$ 匹配 $P(P ^ {-1}(S_i))$ 或 $Q(Q ^ {-1}(S_i))$ 的方案数，根据实际意义转移： - 若 $P ^ {-1}(S_{i - 1}) + 1 = P ^ {-1}(S_i)$，则 $f_{i - 1, 0}\to f_{i, 0}$。 - 若 $Q ^ {-1}(S_{i - 1}) + 1 = Q ^ {-1}(S_i)$，则 $f_{i - 1, 1}\to f_{i, 1}$。 - 若 $Q ^ {-1}(S_{i - 1}) = i - P ^ {-1}(S_i)$，则 $f_{i - 1, 0}\to f_{i, 1}$。 - 若 $P ^ {-1}(S_{i - 1}) = i - Q ^ {-1}(S_i)$，则 $f_{i - 1, 1}\to f_{1, 0}$。 因为每次转移使得 $P, Q$ 匹配位数之和增加 $1$，所以 $f_{2n, 0 / 1}$ 必然经过了 $P$ 从位置 $1$ 到 $n$ 的匹配和 $Q$ 从位置 $1$ 到位置 $n$ 的匹配。初始值 $f_{1, 0 / 1} = 1$，答案即 $f_{2n, 0} + f_{2n, 1}$。 时间复杂度 $\mathcal{O}(n)$。[代码](https://vjudge.net/solution/37421146/comUZrJyu4vrKIJWShl2)。 ### HDU 多校 4 #### 比赛记录 看了下多校总榜，目前 Rank 3。 开场没啥思路，两分钟看到 04 有人过了，大胆猜结论一发过了。 C 写 02 结果 WA。 看 06，签到题，很快过了。几乎同时 C 过了 11。 几分钟后 C 过了 07，然后又调出 02，很恐怖。 我看 09 没啥思路，但是注意到关键性质，于是丢给 C。C 发现这玩意之前模拟赛有类似题目。 R 从开场一直在看 01，30 分钟过了。 看 05，简单题，秒了，$nm ^ 3$ 写完 T 了，改成 $nm ^ 2 + ml$ 才过。 C 写完 09 挂了几发也过了，剩下 03，08 和 10。 R 说 10 是简单题，他会做，顿时信心大增。 看 03，简单题，秒了，差分约束直接冲，一发过了。 C 看了一会说 08 会做了，动态凸包板子题，我都没想到怎么转化成凸包，好厉害。 R 和我交流了一下 10 做法，感觉很对。 一百分钟的时候已经嘴巴阿克了，感觉很牛逼，差点半场开香槟。 我无所事事啊，写 08 暴力。闵可夫斯基和贺的 JSOI2018 战争，那题是整体凸包，但 C 告诉我只要维护右上凸包，我感觉很对，但是改过来的时候好多地方忘记改了。后来 08 交的挂的几发都是对拍时 C 输出正确答案，我写的暴力错了。顿时感觉自己在演。 三个小时和暴力拍上了，结果还是 WA，怀疑数据有问题。Clarificaitons 有人问样例，出题人说要恰好打死 Boss，题面根本没有写啊，出题人给爷爬可以吗？ 于是我和 C 开始改代码，与此同时 R 一发过了 10，简直太牛逼了！ 于是我们信心大增，我很快把暴力搞定了，但是又拍挂了一次（我的暴力输出错误答案，C 输出正确答案），贡献一发罚时，我是演员吧！ 四个小时过拍交了一发过了。 好像阿克了，非常感动。当时榜上只有两个 10 题队，我们已经 11 题了，感觉很牛逼。 到比赛结束出现好多 10 题队，但是没有其它队伍阿克。 今天赢麻了。 总榜变成 Rank 1 了，非常感动。 #### 1001. Link with Bracket Sequence II 难度：Easy，赛时 388 AC。 设 $f_{l, r}$ 表示 $[l, r]$ 方案数，$g_{l, r}$ 表示 $a_l, a_r$ 匹配的 $[l, r]$ 方案数，则 $g_{l, r} = cf_{l + 1, r - 1}$，$f_{l, r} = g_{l, r} + \sum\limits_{p = l} ^ {r - 1} f_{l, p} f_{p + 1, r}$，其中 $c$ 即 $a_l$ 和 $a_r$ 匹配的方案数。 时间复杂度 $\mathcal{O}(n ^ 3)$，注意跳过无用状态以减小常数。[代码](https://vjudge.net/solution/37529094/mXc7lOcScJ9zOlBcDXv1)。 ### HDU 多校 5 今天寄了。 开 06，发现签到题，写了，十二分钟过了。一血。 C 过了 02，一血。 开 12，发现签到题，写了过了。 C 过了 03。 开 07，发现启发式合并 FFT 板子题。没有多项式板子，遂丢给 R。 R 说这个 10 很怪，搞不清题意，他猜结论 WA 了。我拿过来猜了几发结论，重读题面发现题面更新了，写了过了。什么垃圾题。 R 一会之后过了 07。 开 08，发现后缀平衡树板子题。不会后缀平衡树，遂丢给 C。 C 过了 01，被卡常卡了几发。 开 04，发现签到题，找 R 要了个计算几何板子，写了过了。 开 05，发现 DLX 板子题。不会 DLX，遂丢给 C。 C 过了 08。 开 09，发现折半搜板子题，不想写，丢给 C。赛后发现这个决策相当错误，应该我来写 09，这样 C 就能写完了 05 了。太寄了。 09 写完 WA 了，因为数据出锅。出题人四个小时二十分钟的时候改了数据，原来 WA 掉的代码一模一样交上去可以过，但是出题人没有通知改数据。 这个时候已经写不完 05 了，大家一起想 11，到比赛最后也没想出来。本来 05 是能过的。 第五名，寄了。 ### HDU 多校 6 今天寄了。 开 06，发现签到题，写了，差点一血。 跟榜开 12，发现签到题，假了一发，冷静思考后改做法过了。 C 开 02 结果一直 WA，一个小时才过。 开 09，发现是 R 擅长的题目。遂弃掉。 开 10，以为不停删一度点可行，结果一直 WA，很寄。 弃掉开 11，发现 burnside 引理板子题，写了过了。 C 又做了一个小时 01，过了。把 10 丢给他，他说我做法是假的，换了个做法就过了。 R 两个小时过了 07。一会儿后过了 09。 开 08，发现会做，写了过了。 还有 03 04 05，当时只有金中河西一个队过了 04，其它题都没人过，感觉很毒瘤。 开 05，发现可以 $n\log\log n$ 套数据通过，我负责套数据，C 负责写暴力。套完过了。 03 04 都不太会做，一直到比赛结束都在坐牢。 今天排名 11，被杭二甩掉两题，寄了。 ### HDU 多校 7 呜呜，今天也寄了。 开 03，发现签到题，写了，一血。 C 开 08 结果不会，我打了个表没发现规律，也丢了。 此时 R 过了 04，C 说 09 是 Pjudge 原题，贺了份代码也过了。 我看 06，发现是数位 DP 板子题，写了过了。 R 说他已经会 01，07 和 10 了，所以 C 看 11，我继续研究 08，一会之后找到规律过了。 很快 R 过了 10，C 过了 11。 我看 05，会了一个 $256nm\sqrt {nm}$ 的做法，认为是简单题，后来发现我是小丑，根本过不去。 R 告诉 C 01 之前模拟赛有类似题目，C 贺下来改了改就过了。 此时 R 在写 07，C 帮我看 05，结果到比赛结束我们还是不会时间复杂度可以接受的做法，太寄了。 比赛结束前五分钟 C 告诉我除掉 $a_5! a_7! a_{13}!$ 就可以把卷积化成组合数，但是已经没时间推了。我太演了啊！ 第七名，寄了。 ### HDU 多校 8 开 03 06 09 12 发现全都不会做，队友已经过了一车题我还在想 12。最后这四道题是一血时间最晚的四道，出题人也太搞了吧！ 因为 06 是大模拟，而我比较喜欢写大模拟，所以我决定梭哈，让队友写剩下来所有十二道题，我一个人冲大模拟。 两个半小时的时候就写完了，但是一直过不去样例。由于特殊的数据生成方式，样例和所有数据几乎等难，所以调起来相当痛苦。 队友很给力，三个半小时就解决了其它所有题，然后帮我一起调。 C 直接一步一步手摸样例，发现是我有一个减号写成了加号，改掉之后就过样例了，非常兴奋，结果交上去 WA 了，到比赛结束都没调出来。 第五名，前四名全是杭二，很离谱。 打完比赛和同学出去吃疯狂星期四，一想到这场贡献为零蛋就啥也吃不下去。回来后对着数据手摸，发现 std 写挂了，我的程序在这一步没有问题！啊哈哈哈哈哈哈哈哈哈！ 反馈了一下，不过估计早就有人反馈了，晚上七点钟更新数据并重测，结果我直接过了！！！OHHHHHHHHHHHHHHHHHHHHHH！！！而且是全场唯一 AC！！！3/535 是因为我们最后交了三发正确代码，所以为什么我们不是 15 题？ 直接翻到第一名，把杭二干翻了。同学都很高兴，我也很高兴，因为帮助队伍登顶了。 ### HDU 多校 9 开场过了 03，08 两个签到题，R 过了 01，07，10 三个签到题。 C 因为 02 线性规划的实际意义搞反掉了，所以整场比赛都没调出来。 C 做 04，很快就过了。 我做 09，一开始想了 $\log ^ 4$ 的做法，写着写着发现是 $\log ^ 2$。细节有点多，写完交上去 WA 了，写了个拍不停地调，过拍之后交上去过了。 C 写 06 T 了，被我指出算法是假的，重构一下就过了。 R 做 11，到比赛结束前十分钟写完，但是 T 了，卡卡常又 WA 了。他赛后调了一个小时就过了。 最后排名第十。 ### HDU 多校 10 今天签到题写麻了！ 开场看 03，签到题，过了。 然后又看 09，打表题，过了，而且还是一血。 R 一直在看 10，但是 01，04，07 都有人过了，所以交给我来做。 看 07，签到题，过了。 此时 C 过了 02，一血，很厉害。 看 04，发现原题。此时 R 和 C 已经研究出了 10 的解法，所以我把 04 交给打过数竞的 R，10 让 C 来写。他指出这是去年 CMO 原题，让我想起来我就是看去年 CMO 题解了解到马尔可夫链。 看 01，签到题，过了。 此时一发罚时都没有，还登顶了，感觉很好。 C 贡献了第一发罚时，原因是初始化错了，很快改了过了。 R 贡献了第二发罚时，不知道啥原因。后来也过了。 C 很快又把 05 过了，但是 CE 了一发，原因是交成了样例。 看 08，简单题，结果合并直径写挂了，贡献了三发罚时。 C 看 06，我看 11，R 看 12，两个半小时的时候已经嘴巴阿克了。 我觉得 11 挺简单的，但是不知道为什么过的人很少，但是因为没注意到要输出三角形个数贡献了一发罚时。 最后只剩下 12，R 三个小时多一点的时候写完了，但是交上去 T 了，因为他写了线段树合并。卡了好长时间常数才过。 今天登顶了，可是题目太简单，阿克了一车人，权重也不是很高。 总榜 rank 3。