THUPC 2024

· · 个人记录

前情提要

这里是首次线下三人一机的萌萌队伍「虹虹蓝蓝打铁记」（「匿名用户」）。

在不久前结束的 APIO2024 上，我们打出了一银一铜一铁的优异发挥；

在 THUPC 晋级名单上，我们以递补倒一的排名荣登榜尾；

在试机赛上，我们（我）冥思苦想半天仍然不会做签到题 A；

如此成绩，如何 THUPC？？？？？？

赛时

队伍成员是 honghong lanlan 和 铁（），以下分别简称为 虹、HL 和 emoji（玩 game.hullqin.cn 玩的）。

<-1>

<0>

比赛开始时我没有注意时间，因此电脑在 10:00 时还没有打开，我们只好拿起纸质题面研究签到题 M（伏笔*1）。

——然后不出所料很意外地卡住了！道理我都懂，但是哪里有一个确定性的答案？

尝试输出关键词 "Zayin" WA 了，"zayin" WA 了，"CTT" WA 了，"std" 也 WA 了，看榜怎么这么多个队过题了，遂破防，那么各自随机看了些其它题，但显然大家都还在潜意识里对 M 进行阅读理解，并没做出有效思考（）

<1>

十几分钟后榜上有队伍过了两题，我们 M 的罚时也来到了六发，与「思路打开」「我是鱼」等少数队伍并列垫底。感觉「思路打开」没能打开思路很有意思，你觉得呢。

此时意识到再这样好像真要倒一了，于是跟榜想正常题。emoji 老师很快会了 K，我在他上机后几乎同时会了 D 和 E——E 貌似难写又难调，但鉴于初赛时我仅仅罚时六发就通过了同名题目”转化“，我对自己能够通过 E 抱有充足的自信（flag*1）。

emoji 写完 K 挂了，我接力上去写 D，即将写完的瞬间 emoji 老师冲过来修改了 K 题的数组重名，于是 K 和 D 都过了；

出于一下子过两题的喜悦，我又上去罚了四发 M（"std.cpp"、"zayin.cpp"，"CTT2023"……），然后灵光一闪打开了网页题面的“下发文件”，于是 M 也过了（-10 无人能敌！）；

虹老师/emoji 老师表示 B 题像是网络流/最大权闭合子图，很快解决掉 f_i,h_i 的建图问题后丢给我写，我不会网络流建模，但感觉直接最小割就很好理解，于是敲完板子 B 也过了；

虹老师/emoji 老师说 C 题是“给 n^2 个区间，选一些不交区间最大化权值和”问题，我一眼发现根分后就 n\sqrt m 了啊（破案：emoji 没有发现 c_i 与人无关），写完因为 a_i,b_i 看反调了一会，于是 C 也过了；

此时我们来到了 rk14，五题第（倒）一！以压倒性优势领（落）先（后）rk13 近一个半小时的罚时！无论如何总之还剩三个半小时，手上还有两道已经会做的题，这怎么输？（flag*2）

<2>

虹老师开始分讨 L，我上机去写 E。越写越破防，显然它和初赛 E 题风格类似，像是同一个**出题人出的。

大约半小时后我调过了 E 题样例，获得第一发 WA；虹老师借机验证了 L 数列递推 n=2 的正确性和 n=3 的错误性，继续去手动分讨修改 n=3 的递推式；emoji 老师声称会了弱智的 J，但没多久又表示自己看错了题（伏笔*2）。

那么把 emoji 拉过来帮忙调 E。他听完我的做法觉得很对（先缩点，再判零，再对每种转化方式判 inf 并向后继传递，最后枚举终止点在 DAG 上随便 dp），遂同我一起陷入了修改初版代码的天坑（伏笔*3）。

——于是直到临近封榜时，我们三位还理所当然地在“L：改递推式系数+过不去样例”和“E：瞪眼挑错+改代码+WA”两条进程上无限循环，时不时打开榜欣赏下不断下滑的排名。

我实在无法忍受于这种无能无力的处境，跑去开了 H 题。

虹老师看一眼给出了一个不太对的和一个非常复杂的判定结论，我发现其实应该是 \frac{\sum |i-p_i|}{2}\leq m；并且“恰好交换 n 次”的要求其实就是限制置换环数量为偶数。那么做过云斗四月月赛的我容易想到 \frac{\sum |i-p_i|}{2}=\sum [p_i>i](p_i-i)，然后枚举值域对置换环/链形态进行复杂度 O(nm\sqrt m) 的 dp——这个做法代码既短又好调，想必应该能过题吧？（flag*3）

<4>

最后一小时，我们幻想着封榜后连过三题的奇迹降临，但显然比赛不总能如意。

虹老师于封榜后二十五分钟终于找到了 L 的正确递推式，交给我加上矩阵快速幂后成功 AC；

emoji 老师瞪眼许久仍然找不出 E 代码各个部分有什么错，然而在封榜后三十多分钟后忽然发现我代码的整体实现与逻辑全是混乱的：我在初始化前调用了 vector<int>e2，在判 0 之前使用了判 0 的结果去更新 inf，etc。然后交给我加急修改，但不知为何仍然 WA 在了数据范围很小的点上。

我则于封榜后二十多分钟写完 H，最后十分钟终于调对了大样例！可是我早没想到，计数题通过样例虽然不太可能 WA，但很可能 T 啊——状态数 n\times m\times \sqrt m\times 2 达到了惊人的 5e8，本地不开 O2 要跑十秒钟——于是一边谴责 shaber 出题人一边卡常，直到最后两分钟交了两份代码，一份阈值 100 T 了，另一份阈值 50 WA 了（实际上可以设成 71）。

最后只有 BCDKLM 6 题。

赛后

<1>

听讲评。

M 我*****你*******。

E 果然还是小 E 题，题解和我的做法只能说完全一致，实在不懂到底哪里写挂了？？？？

J emoji 老师表示和他想的一模一样，但是他不会 sg 函数？？？？？？所以在发现题面不是多测而是叠加后就弃掉了？？？？？？？

H 我们该知道的结论都猜到了，该会的 dp 也会了。但数据范围凭什么开这么大？？？我复杂度没有任何问题，只是没有精细卡常/状态数比 std 多乘了个二就死了？？？？？？？

L 出题人被虹老师强烈鄙视！搜出 46 的状态数也太菜了，我们虹老师手模两小时把状态数压到了 6！我最后交的 6*6 矩阵快速幂甚至能过多测 T=10^5，建议开大数据范围把其它做法全部卡掉！（让我膜拜下虹老师，真是分讨大师，贡献了本队唯一一道后期题！！！！！！！）

<2>

滚榜进前五十了，比起初赛很有进步（无语），但显然不是很满意 v_v

如果我们开场没有在谜语题 M 上浪费半小时；

如果我 E 的代码能在清晰精准一些，或者如果 emoji 老师能在空机时尝试重构一份，或者弃题去看 I；

如果 emoji 老师能给我们讲讲 J 的做法，讲讲为什么“看错题意，有很大问题”；

如果我还来得及用几分钟给 H 加上加法的取模优化/改掉 define int long long；

。。。。。。

过去的故事没有如果，但假如还有下次，我先相信我们一定能打出更好的发挥哈哈。

<3>

获得纪念品——气球！我的蓝蓝太可爱了，xsap 的虹虹也是