THUSC&PKUSC&APIO2024 打铁记

· · 生活·游记

前情提要

本来教练不给报 APIO 的，后来因为和 PKUSC 挨上了就给报了，然后稀里糊涂的又报了个 THUSC。

小一 PKUWC 优异了，没来 T。

不管了反正是来旅游的。

2024.5.3-2024.5.9 停课训练

在某场模拟赛获得 4.5k 代码只得 10 分的光辉战绩。

由于独特的姓名给我记了五次值日。

2024.5.11-2024.5.12 THUSC

Day1

早上下雨，鞋湿了。

上午试机。T2 是老题但没做过，想了半天胡了个做法觉得太复杂就没写。T3 格式很像旷野大计算，看了半天觉得不是人能写的。出来看了下 uoj 上一些老哥的 T2 代码，我的做法不出所料地假了。

试完机发现和午饭还有一个小时的距离，于是在门口随机游走。

Day1 五个小时四道题，伟大的 cyx 说按照以往的经验拿到 200 应该就够了，于是并没有对分数抱很大的期待。

开 T1，貌似是求

\sum_{x_1=0}^{n_1}\sum_{x_2=0}^{n_2}\dots\sum_{x_d=0}^{n_d}\max(0,(x1 \oplus x2 \oplus \dots\oplus x_d)-l)

这样一个东西。

看到 d=10 想到状压，d 个数每个都有一个上限想到数位 dp，可以记 >=l 的数量与和。于是得到 dp_{i,j,0/1,0/1} 表示第 i 位，顶到头的集合为 j，有没有贴到 l 的数量与总和。转移的时候枚举这一位取什么值，整个复杂度是 O(T\cdot4^d\log n) 的。

虽然转移可以枚举子集优化，但是复杂度还是很高，由于还要取模之类的常数也比较大。发现很难写，好在 1.5h 写+调完了，交上去直接过了（pretest）。

开 T2，开到一半觉得 pretest 强度不够，自己造了一组 T1 的极限数据。跑了 11s。瞬间慌了，开始疯狂卡常、重构，最后写了半天只降到了 9s。于是开摆。

T2 是给定前缀 s，构造一个字符串使得所有长度为 k 的小写字母组成的字符串都是它的子序列。

发现没有前缀的限制就是是 k 个 a-z 拼起来，于是胡了个将 s 扩成这样的字符串的做法，没有细想就写了，然后交上去就过了，这下这下了。感觉会假的很离谱但也懒得拍了，反正拍挂了也想不出来正解。

开 T3，给你一棵带边权的树，有些边已经被定向，你需要给没被定向的边定向，使得可到达的两点之间的最大距离最小。

一眼二分答案，想到一个状态 n^3 的 dp，记这颗子树到根的上行和下行最长路径能否做到。又发现我只能子树根向父亲的边定一个方向，所以只关心其中一个信息，另外一个方向只要保证合法就行了。

于是 dp_{u,0/1} 表示以 u 为根的子树在最长路不超过 k（这个是二分的值），上行/下行的最长路径的最小值。转移的时候把子节点按照上行/下行的 dp 值排个序就行了。

感觉大脑有点过热，上趟厕所先（

调完测到样例 5 就自信提交，直接过了。觉得不保险就回来看样例 6。然后 RE 了。对着代码瞪了好久，最后断定因为是一条链所以递归的时候本地栈爆了。不知道怎么开栈，于是就开摆了。

开 T4，woc 这题格式怎么跟试机一模一样，显然写不出正解，最后拼拼凑凑拿了 31 分。

出来交流了一下发现人均过三个题。

晚饭 BJ 初二 OIer 聚餐，由于不太熟所以没聊起来。有人 T1 有 O(d^2\log n) 做法，折磨牛。

完了 Day2 要爆蛋了。

Day2

还是下雨，但是准备了鞋套，结果走一半破了，猛猛进水。在门口等了 20min szh，成功吓到。

今天是工程题。开题，诶 T1 不就是模拟吗，写写写，过了。诶 T2 不就是加几行代码吗，写写写，过了。T3 还是大模拟，写写写，过了。

感觉优势在我啊。

T4 给了个信息熵，发现就是前几题拼起来暴力枚举计数然后套公式。写写写，诶样例怎么挂了。瞪了半天发现读错题了，又改了好久终于写对了。但是样例两组跑了快 1s，有点慌，不过交上去过了就没管。

看眼时间，woc 怎么就剩半小时了。赶紧读 T5，发现是个交互题，格式要改好多。然后一大车编译错误，woc 怎么就剩 2min 了。改改改，怎么又蹦出来一堆不知名错误，此时只剩 1min，直接交了，没 CE。

比赛结束。

旁边老哥 479，挺牛的。但是我代码怎么还没跑完啊。又过了 2min 跑出来，TLE 0pts。

好似！

下午就是吃饭合影听讲座发奖，本来打算不听讲座直接跑路的，后来还是决定等发完奖在走。

讲座讲的是大模型发展之类的，没听懂一点.jpg。然后是讲题，D1T1 连续两个老哥上来分别用 O(d^2\log n) 和 O(d\log n) 的复杂度吊打标程，出题人摸着脑袋的样子真的很可爱。D1T3 上演《我的麦很炸吗》名场面。D1T4 的“注意到”没绷住。反正就是各种抽象。

发奖，但是证书迟迟没有准备好。于是循环播放清华宣传片，由于声音太大了所以一直捂着耳朵，这波和校服配合很好。

不是真没人觉得声音太大吗。循环第三遍的时候忍不住了，直接跑到台下让老师把声音调小，我们 BDFZ OIer 真是太有实力啦！

1=了，证书发下来直接跑路赶高铁，路上司机猛猛超车，结果高铁晚点 14min。ps：高铁是 CRH400BF-AZ 5252，要素过多。

终于不用大家再见了，但是 cxy 怎么分跟我一样却要死的感觉啊，这就是队爷吗/bx。

就这样。

（昨天写了一大段没保存，这下这下了）

2024.5.13-2024.5.14 PKUSC

Day1

早上在电梯口吓小一失败。

试机放了 PKUWC 的 D1T2，我怎么刚补过.jpg，于是啥都不干，开始默写。于是成功在试机结束前通过编译。最后所有人都走了，剩下三个人围着看我调代码。莫名喜感.jpg。

最后还是没调出来样例，突然想起这个试机好像是不删代码的，貌似可以试机的时候把所有板子都照着手机打了然后考试的时候直接用。坏了感觉要成伏笔。

去食堂的路上看见可爱的猫猫，追着它摸了半天。

午休，woc 我昨天写那么长游记咋没保存，于是整个中午都在补昨天游记。

于是迷迷糊糊去了比赛。

开 T1，给你一个 2\times n 的网格，每个格子上一个字母。你可以从任意格子出发，向下/右走，在任意格子停止，求最长的回文路径。当时想了半天怎么把马拉车扩展一下，发现了选定格子作为中心先尽量在它的那一行往外扩肯定最优。诶这不就是哈希吗。woc我咋把哈希判回文串给忘了。

对面老哥开考后没过几分钟就开始狂敲代码，恐怖。好在没被压力，1h 过了 T1。

开 T2，我超计算几何，这下啥都不会了。貌似是数一个凸多边形里有多少个格点正方形。自己胡了一个判断某个点是否在凸多边形里的方法。感觉很对。想着总不能拿 15 分暴力就走，于是开始推性质。等一下，数正方形不就是枚举一个角随便递推吗，那这不就是做完了吗。

上趟厕所冷静一下。

回来决定先手玩一下样例，然后惊喜的发现还有不平行于坐标轴的正方形，好似！这下真不会了，看看特殊性质吧。可以发现，一个正方形可以找出它唯一的平行于坐标轴的外弦图，每个外弦图里能找到它的边长个正方形。而且如果一个正方形在长方形中，那么它的外弦图也在长方形中！性质 1 的凸多边形正好是平行坐标轴的长方形，好耶 10 分有了。后来又想了半天性质 2 直角三角形的答案，不会。于是把 15 分的暴力和 10 分的性质写了。

此时还剩一个小时，想着把 T3 暴力写了，再碰碰运气。T3 是求一颗树的最大权独立集期望，每个点在 [1,m] 中取值，n\le 2000，m\le 10^8。显然是个 dp。。最大权独立集可以用 f_{i,1/0} 表示以 i 为根的子树该点选/不选能做到的最大值这个 dp 来实现。

dp 有个套路是看你关心什么。这道题发现我只关心 \max(0,f_{i,1}-f_{i,0})，并且很显然这个数不超过 m！于是可以用 dp_{i,j,0/1} 表示以 i 为根的子树，该值为 j 的时候的方案数/f_{i,0} 的和，这样 max(f_{i,0},f_{i,1}) 的和（也就是答案）就能快速求出。O(n^3) 的 dp 可以拿到 n,m\le 500 的48分！

于是用半个小时写掉了，决定优化 T2 暴力枚举的复杂度。发现由于是凸多边形，任意一条直线上在图形内部的点一定是连续的，通过一些计算可以省掉枚举一维的复杂度。没准可以再多拿 35 分！然而最后细节有点多到比赛结束也没调出来。

173，应该够了。

没调出来的 35 分不要成为伏笔。

Day2

上午吉老师讲自动 AC 机，崇拜。

吃完饭合影，顶着太阳照了两遍，眼睛好疼。

开题，T1 是给你一个除了 n+1 号点所有点出度为 2 的有向无环图（只有 1 没有入边），每个点两条出边分别连向 out_{i,0} 和 out_{i,1}，又一个布尔值 b_i，每次有一个东西从 1 号点出发，在第 i 号点往 out_{i,b_i} 走，并将 b_i 取反，到 n+1 号点结束，问最少多少次之后所有 b_i 都回到初始状态。

感觉最后答案是 2 的多少次方，后面就不会了。不知道怎么迷迷糊糊写了个每个点维护一个以 2 的次幂为分母的分数，每次除 2 加到两个出点上。要高精，好烦。好样例过了，自信提交！不出意料挂成 0 分，接下来就是疯狂调细节，获得了 35 分的好成绩。

2h30min 觉得这个做法没前途，准备开 T2T3 写几个暴力。赛后交流了一下发现是对的。

T2 是给你 n 个函数，f_i(x)=x+[x\in[l_i,r_i]]，，q 次询问给定 L,R 让你计算 f_R(f_{R-1}(\dots f_{L}(0))，看到特殊性质有好多分，但是貌似都不会，O(nq) 10 分跑路。

T3 是随机生成一个有向图，q 次询问每次给起点终点计算最短路，n 是 2\times 10^5，m 是 3\times 10^6。貌似也有很多性质，但是都不会。想着把询问按起点离线，在对每个起点算最短路，清空用 dfs，成功骗到暴力 5pts 和 m\le n 的 10pts。

剩下的时间想 T1，由于把正解给否了，什么都没有想出来。

比赛结束，35+10+15=60，怎么大家都会 T1，小一总分 346/bx。

173，应该够了。

算了一下 35 分真成伏笔了，初二线好像是 250，233+35=268，绷不住了。

这次总不能怪策略，签到题切不掉纯纯实力问题。

感觉这几次炸掉的比赛赛后越来越平静了啊，或许是认识到自己思维水平的差距。

希望 APIO 别打铁吧...

大家再见。

2024.5.15 西湖

绕着半个西湖走了一圈，貌似和 cxy 擦肩而过了（？

走一会就要停下来合个影/fn

唯一的收获就是看到几只可爱的松鼠，相册多了几张照片吧。还有这好像是我这 20 天最大的运动量吧。

风把我耳机吹没了啊啊啊。

2024.5.16-2024.5.19 APIO

Day1

退房，然后到新的酒店住，怎么离学军更远了/jk

yyx 被鱼鳍抓走一起住了，祝好。

有一趟班车送我们到学军吃饭然后吃完饭再送回来，有点抽象。于是选择在酒店吃午饭。下午 ran 在群里说不去学军吃报名费就亏了，这下这下了。

稍微补了 10% 的作业，然后啥都没干。

晚上竟然有黑四，十分艰难地打完了。tl 怎么没打，应该是觉得太简单了吧/bx

小一 2 点才睡着，我也一直半梦半醒，有点怀疑酒店床的质量。

Day2

早上被强制起床。

gyr、zky、gyc 讲课，但是我为什么一点都听不懂啊啊啊。

迷迷糊糊过去了一天。

Day3

试机和考试是连着的，开始疯狂打板子。

桌子上怎么有个 toilet，哦原来是上厕所要举这个牌啊，感觉这种艺术还是太超前了。由于比赛是 10:00-15:00，主办方贴心地给我们准备了食物。

开题，T1 懒得说题意了，反正就是各种乱搞，成功在 1h 中过掉了。

感觉优势在我啊。

T2 给你一张图和若干特定时刻从某个点出发再由特定时刻到达某个点的航线，有几个时段需要吃饭，但是在航线中吃饭不用花钱，在某个点停留是吃饭需要花这个点的权值。第一眼是用一些方法建图然后在这条路上一去不复返...

先把 10 分的暴力+性质1 打了，发现吃饭时间不重叠的 30 分可以保证复杂度地建图，开写！

于是就到了 14:30 呢。

打算看一眼 T3，交互库给 A 一个 10^{18} 级别的数字 n，A 需要构造一棵点数 5000 的树给交互库，交互库会删除最多一半的边给 B，B 需要根据删完的那些边猜出这个数字。

感觉很人类智慧啊，想了半天我怎么连 n\le 5000 都不会，于是又去调 T2，于是不出所料地，拿到了 110 的总分呢。

yyx 把 T3 秒了/bx

听说铜牌线 115，好似！

讲题一堆老哥不同的 T3 做法，测怎么都会 T3 啊啊啊。

Day3

花花和 sjy 讲题，虽然一点都听不懂但还是拜谢。

晚上闭幕式。还是各种名场面。到了喜闻乐见的颁奖环节，但是是我是高贵的铁牌选手！

拜谢银牌爷 yyx。拜谢银牌爷 yyx。拜谢银牌爷 yyx。拜谢银牌爷 yyx。拜谢银牌爷 yyx。拜谢银牌爷 yyx。拜谢银牌爷 yyx。拜谢银牌爷 yyx。

伴随着头部的阵痛，我又浑浑噩噩过了一天呢。从 THUSC 到现在，无论是思维能力、精神状态还是心态，都稳定单调递减。我还需要面对堆了快 20 天的 whk 作业和回到学校中人际交往的压力。可以说，去掉 THUSC 不算太差的表现，很难想象我将要如何面对接下来的生活。

“感觉这几次炸掉的比赛赛后越来越平静了啊，或许是认识到自己思维水平的差距。”

仔细想一下，也许这件事也有我所认为的“可以依靠的东西”的影响。直到现在我才意识到，我引以为傲的“可以依靠的东西”只不过是从我连出的两条边而已。

如此不堪一击呢。

正因如此，才应该去努力守护吧，为了不跌入绝望的深渊。

无法立下“下次我一定要站在领奖台上”这一誓言，唯一能做的是从我可怜的思维水平和码力中求得一点提升。

帮你的只有你自己呀。

大家再见。