THUSC+PKUSC+APIO2024 (险些)坠梯记
CarroT1212 · · 生活·游记
初二酱油选手献丑了。
还是不知道为什么每篇游记的比赛第一天我都会写 Day 0 而不是 1。
生地实验模拟
Day -9
啊原来 THUSC 和 PKUSC 不在同一天吗？
Day -4
滚回去上 whk。感觉废了。
Day -2
周五下午要去考生地实验操作的模拟。是什么力量使一个模拟考让我们的飞机改签？
模拟考项目是显微镜观察番茄果肉细胞。
话说今年居然是在你旁边摆一堆摄像头然后线上统一评分，旁边摆了个平板显示所有操作，还接电子目镜截图展示显微镜画面，甚至要求你标出来细胞在哪，都这么高级了吗。而且显微镜下面用的是电灯，老师说全深圳统一，那就没有对光问题了。
晚上去生物室考了模拟考的模拟考。本来还觉得多此一举的来着，结果实际情况是盖玻片滴个水还能手抖滴到外面，刮番茄果肉刮了两分钟刮不出来一点，学校的显微镜看起来没有跟深圳统一，显微镜没用过要对光的然后对了一分钟。还得多练。
Day -1
班上别的人考二模。看起来题目比较抽象，不知道到明年又会变成什么鬼样子。
Day 0（5-10）
去邻校考生地实验。甚至要穿白大褂。
好高级的设备。
开考倒计时结束。
仔细地擦干载玻片和盖玻片。
居然做出了这几天以来最完美的一个装片。
抬出显微镜。
等会不是说全深圳统一用电源的吗怎么要对光啊喂？
然后看了一圈好像只能对教室的照明光，对了一分钟终于看到个合理的亮度。
抬头看一眼时间。
还剩一分钟。
原地石化。
忘了限时五分钟了。
于是最后刚看到一个像样的圆形就结束了。
看来显微镜确实全深圳统一了，官方视频除外。
虽然归根结底还是我菜，但是真的不得不瑞平一下这个神秘的五分钟时限。去年都是十分钟的，咋今年就卡这么死了。官方的演示视频行云流水一顿操作下来都干到了四分钟，五分钟这意思是一点自己预想之外的情况都容不得吗。还是说这就是模拟考存在的意义？
祝正式考试别抽到显微镜。
THUSC
同游者：czk，lyj，lzh。
Day -1（5-10）
飞机上跟某位外校同学坐到了一排，一问发现居然是 Dengduck。惊到了。
住余姚宾馆。到酒店的时候已经 23:00+ 了。
酒店看起来处于一种古老和高级的叠加态，甚至有浴缸。而且床头柜里还放了一些不可描述的东西。
Day 0（5-11）
酒店的早饭是优秀的。
电脑收上去了。/ll
上午报到+试机。THU 又发了经典的 bug 调试指南小转盘，但换了个皮，并把“问 chatgpt”改成了“问 AI 大模型”。
非常难绷的一幕是我们跟着一堆人进社区学院考场，前面一堆人上了二楼就全部往外面走，我还想着哪里写了机房在二楼并且一起跟了过去，然后看到前面的一堆人走到最后全部掉头走了回来。
机房在四楼。机器和环境还是不错的。
试机赛 T2 有点意思。走的时候一直在想它以至于忘记拿袋子然后跑了两百米回来。四个人一起绞尽脑汁到吃完午饭之后上讨论区看了一眼，居然是每次删
T3 提答来不及搞。
午饭吃了一些抽象东西。
13:10：进考场了。但是不能动电脑，难绷。
13:30：rp++。
13;45：看了一圈。
大致记下题意，以后看的时候想得起来。
T1：求
\sum\limits_{a_1=0}^{n_1-1}\sum\limits_{a_2=0}^{n_2-1}\cdots\sum\limits_{a_d=0}^{n_d-1}\max((a_1\operatorname{xor}a_2\operatorname{xor}\cdots\operatorname{xor}a_d)-l,0) 。n_i,l\le 10^{18} ，d\le 10 .T2：给定串
S' ，求串S 使S' 为S 的前缀，并且所有小写字母组成的长度为k 的字符串都是S 的子序列。数据范围O(n\sim n\log n) 。T3：一棵树，带边权，有些边已被定向，请你将剩下的边定向后使树上权值最大的有向路径的权值最小，问最小值。
n\le 10^5 。T4：提交答案，输入一个只支持赋值、
\bmod\ 998244353 加法和内存访问的程序，输出一个加法操作和使用的内存大小都尽量小的程序，根据某些标准评分。10 组数据。
T1 像是一个数位+状压 DP，但是直接做可能有不小的常数问题。
T2 让我想起了 CF1924A，判定
T3 感觉处于一种可做与不可做的叠加态。（读错性质了以为）链是可以简单贪心的。
T4 纯乱搞。晚点找找规律。
想了一会 T3 感觉没什么戏就开写了。
15:15：感觉状态不太行，T1 这种东西写了半小时调了快一小时，还被卡常（实际上是复杂度不对）只有 85，先去写 T2 了。
15:35：把 T2 的特殊性质拿完了。
然后发现这个特殊性质的做法就是正解？
麻了。
15:45：写完 T3 暴力。
发现链的性质不是保证所有被定向的边同向，只是单纯是条链而已。然后不会了。
16:00：开 T4。
16:35：花了点时间研究了一下 T4 怎么用。想着直接把输入程序输出来着，以为每个点能拿
暂时不太想推。回去尝试卡一下 T1 的常。发现 T1 复杂度可以用类线段树判断合法卡掉一个
17:20：1.5s 卡过去了。
去写 T4。
前三个点是输出
17:50：用神奇的快速乘在前三个点获得了
第四个点是输出
什么玩意啊这是。
尝试用快速乘去拆它，但是发现由于它有非常大量的
第
想搞个线段树，但是感觉来不及实现。最后三个点根本看不出是什么。
发现这几个点有一些引导性语句没有实际用处，但是改完之后分数并没有变多。开摆。
尝试回去把第四个点搞出点什么东西来。发现我根本看不懂输入数据的构造过程，到最后也没啥思路。
18:30：于是最后
感觉周围一圈全是 300+。
出去一问，lzh 不会编译寄了，czk 过了 T3 但 T1 被卡常，lyj T4 乱搞出了
明天希望能被随机区分上去。
晚上 ABC 因为死活连不上热点没打，否则估计能上黄。
Day 1（5-12）
8:30：手搓 Wordle？
8:37：整理了一下文件。
- 给定词库。
- T1：模拟简单模式的 wordle checker。
- T2：模拟困难模式的 wordle checker。
- T3：求在简单模式下的玩家操作后的每一步有多少可能的答案。
- T4：在简单/困难模式下对于玩家的每一步求下一个选哪个词信息量最大。
- T5：交互，写一个 wordle 求解器，满分是
3.5 组内猜出答案。
8:45：根据观测 T1\~3 是纯模拟，T4\~5 要先把材料里那个信息熵学会才能做。怎么感觉比之前的工程题友好到不知道哪里去了。
不过这次还是只能先开写了。
9:15：过 T1。
9:23：改了改过 T2。
10:15：过 T3。
感觉调试时间有点长了。
然后开始学信息熵。
10:45：会用了。
信息量就是对于当前猜测的单词在所有可能得答案下的返回结果分组，然后把每组的单词的信息熵乘个
证明跟证了一样，反正有上面的过程就够了。
写 T4。
11:40：过 T4 50。
然后怎么还有困难模式啊。/tuu。
12:00：过 T4。
剩下半小时，T5 优化到 100 估计来不及，把 T4 改一下变成每次选信息量最大的直接交吧。
12:15：改完了。
怎么本地编译不了。
交上去喜提 60s TLE。
12:20：测原来 T5 下发文件后来修了。
12:25：为什么我可以一边 freopen 一边在终端输入。
12:30：调不对，寄。
于是两天加起来
好像周围一堆 400+ 和 500。
出考场发现 czk lzh T2 没调对于是没写 T4 寄了，lyj AK 了！
了解到在 freopen 时在终端输入是 Linux 在死循环时的特性。那就是改挂了，悲。
午饭是神秘的。
下午讲座。
唯一的记忆点是 D1T1 被从指数复杂度爆标成多项式和 D1T4。一到三爆搜拆分，第四个点可以直接回收用不到的变量，但是一个更厉害的结论是
一开始说四点半发奖，然后到五点半才出来，中途放了一遍又一遍的 thu 的纪念视频和余姚中学的高考百日祝福视频。话说这个高考百日视频也是逆天。
概要：九科老师轮流开大。
还有更逆天的，但是忘了。
- 祝同学们高考考场上能有贾黛共读西厢的一目十行。
- 双曲线，抛物线，助你冲上清北线。
- 过去将来进行时，（后面忘了。）
- 动量冲量，前途无量。
- 同学们，高考是将反应物转化为生成物的重要化学反应。
- 调动你的线粒体，燃烧你的 ATP。
- （政治普普通通。）
- （历史普普通通。）
- 不管是正气旋还是反气旋，祝你们高考归来都能凯旋。
居然三个人都 1= 了。lzh，默哀。
PKUSC
同游者：czk。
Day -1（5-12）
晚上跑去杭州。
路上了解到 APIO 的 Au Ag Cu 是各
这个酒店敢把“智能”写在名字里，看了一圈确实挺智能的。酒店里放了个小度可以语音操作各种设备，那个神秘的马桶也是走到旁边就自动开盖。不过这个电视怎么看不了啊，这么大一个 4K 电视居然没有网？
Day 0（5-13）
早饭是好的。然后前往文渊中学。
非常神秘的学校，感觉更像个公园和博物馆的结合体。过于先进了。
听 pku 宣传。
试机。经典体育馆摆电脑，但是为什么是笔记本电脑？刚开始用感觉眼快瞎了。后来好一点。
不过好像也挺合理，像育才那样搞那么许多台式机估计也挺麻烦的。
午饭学校发的是盒饭，吃不到本校伙食（悲），不过味道还可以。
中午脑子清空。
13:40：进场。
电脑不还原的吗。不过好像也没法还原。
14:00：rp++。
T1：两行的字符矩阵，可以随便挑起点和终点，每次只能向右/下走，问路径上的字符组成的所有可能的字符串中最长的回文串长度是多少。
n \le 10^5 。T2：网格图上有一个凸多边形，问有多少个正方形在它内部。
n\le 8 ，0\le x_i,y_i \le 2000 。T3：一棵树，每个点的点权在
[1,m] 中随机选取，求这棵树的最大权独立集的期望乘m^n 得到的结果。1 \le n \le 2000 ，1 \le m \le 10^8 。
神秘字符串+神秘计算几何+神秘期望 DP。
坏了，没一个擅长的。
14:30：T1 可以二分+哈希
但是为什么 T2 样例 1 的答案是
14:40：啊正方形可以斜着？
坏了，不会。如果考虑包含一个斜正方形的最大正方形的话好像有戏，但是那样就得处理几个角度能取，没得二分，只能
15:05：T3 也没啥戏，开写吧。
15:40：状态还是不好，T1 写完过不了样例。先写 T2
15:50：怎么三个样例都过了还会挂啊？
16:00：看不出来，把 T3 暴力打完回去调 T1。
16:30：搞定了。再想了一会 T3，依然无思路。
16:50：那就回去搞 T2 了。
18:00：根据观察似乎是判断点是否在多边形内的部分出了问题。把拆三角形面积法换成了叉乘法和回转数法以及各种神奇的方法都失败了。中途反复尝试思考其他的特殊性质也没想到。想着最板的暴力也打不对还写什么别的分，就继续调了。
于是 T2
czk T3 拿到了近一半的分数。啊原来那个最大正方形的方法在 T2 Sub1 里面是可以用的吗？我场上干啥去了。
晚上 czk 在疯狂研究 T3，我随便看了点东西。
Day 1（5-14）
上午喜提九条可怜讲座，自动 AC 机的标题和主讲人名称出来的时候全场原地开始鼓掌。
讲的是真有意思，至少在现场气氛上感觉可以把我之前听过的学术讲座全体薄纱。
13:50：rp++。
14:00：怎么前两题题面这么死长。T3 什么玩意……？
T1（经过少量转化后）：
n+1 个点的图，1 \sim n 中的每个点有两条边连向编号比它大的点，现在在1 号点放x 个物品，每个点会将自己的物品轮流发向两个连接的点，问x 最小是多少才能使每个点收到的物品数都是偶数。1 \le n \le 5\times 10^4 。T2：给定序列
a,b ，每次询问一个区间[l,r] ，从l 到r 遍历一遍，有一个变量x 初始为0 ，如果x\in [a_i,b_i] 就将x 加一，对于每个询问求最终的x 。1 \le n \le 10^6 。T3：
q 次随机询问求随机有向图上两点的最短路。1 \le n \le 2\times 10^5 ，1\le m\le3\times10^6 ，1 \le q \le 10^4 。部分分：m \le n ，m \le 2.5n ，m \le ?n 。
14:10：看完了题。感觉不是很妙。T3 晚点再来乱搞，T2 感觉更可做但是想了一会并没有很好的维护方法。先搞 T1。
14:20：感觉几题都还是很有 pku 题目一贯的看起来非常可做但是就是不会做的风格。
T1 尝试了一会直接用答案表示每个点的物品数量。但是由于有巨量的向下取整给干不会了，考虑到出题人也是人遂放弃。
14:25：难道说答案一定是
14:30：考虑充分利用 IOI 赛制，写了发暴力交上去，然后在输出答案前加了个 assert，没有 RE，所以是对的。
14:40：又显然答案不超过
哦有高精。那手写个 bitset 维护一下
15:15：过了。开始细想 T2 T3。
15:50：T2 尝试从特殊性质下手，但下手不了一点，好像只有询问右端点全在
16:20：写完了，中途尝试给 T3 加点优化，但没有多分。
17:00：随机乱想 T2 乱试 T3。搞不动了，然后终于意识到 T2 Sub2 可以倒着用平衡树维护每一个位置能到的答案，需要区间平移。但是平衡树已经有几个世纪没有写过了，感觉写出来的希望渺茫。
17:10：感觉真的想不动了，决定试试写个平衡树缓解一下脑子停机问题。可能中途灵光一闪啥的。
17:45：闪不了一点。写完了。过不了一点。
18:00：寄。
czk 没过 T1 寄飞了，默哀。
晚上摆摆摆。去京杭大运河转了一圈。好看的。
Day 2（5-15）
旅游天。去了岳王庙和西湖。
“怎么感觉西湖里头就西湖十景最不好看？”
突然意识到 D2T2 好像想歪了。寄。
APIO
同游者：zjh，lyj，tjb，hxh。
Day -1（5-15）
酒店电视可以接硬盘，于是下了个信条插到电视上晚上跟 zjh 把它看完了。两人大为震撼。
Day 0（5-16）
九点半到学校选的酒店报到都有这么许多人。
酒店房间还不错，只是作为一间双人房这个桌椅的设置有点阴间了。
跑去学校吃饭。但是车程达到了惊人的半个小时，怎么回事呢。
这回居然不是盒饭。感觉不错。
回去车程又达到了惊人的四十分钟，感觉是车太高了一直在绕路。
然后回收标题。
酒店只有四部电梯可以上到住房，而这几天它们需要面对的是前往各种楼层的六百名考生。而正好右边外侧的那部电梯还停工了。
电梯规格是 11 人 1045kg。然而在我们等电梯时发现，通常刚过六七个人电梯就不关门了。于是大堂积压了大量的人群。
想走楼梯但是不开。
后来 zjh 和 lyj 费尽千辛万苦挤进了右边里侧的电梯，这时电梯里装的人还算比较多，我感觉会超载于是没进。但这次电梯门相比之前是以一个非常缓慢的速度逐渐关上的。
然后我想另找出路的时候看到那部电梯的门突然打开，然后里面的人全部一脸惊恐地跑了出来。
据同学所说，电梯在上升了半秒之后突然停住并且以一个非常大的动静震了一下，然后立刻下降半秒之后再停住震了一下，把大家吓得不轻。
工作人员过来停了这部电梯。于是原本就不多的电梯数量雪上加霜。突然猜到外边那个电梯是怎么寄的了。
耗了很久才上去。
然后摆。晚上懒得专程跑学校吃一趟就一起去吃了疯四。
回来时发现有人在弹酒店大堂里放的那架钢琴。手痒了，但社恐没去。
晚上瞅了几眼热身赛。感觉提交格式非常神秘。
睡觉的时候房间空调开了跟开了一样。
Day 1（5-17）
早饭是优秀的，只是人好多。那个苹果汁和泡椒鱼皮非常灵性。
上午是 gyr 的讲座。大体上能听懂，但是感觉概率论还是非常神秘的。话说这个舞台设计的时候就是只打算让大家看人的吗，幕布把近一半的屏幕挡住了。
午饭感觉没那么优秀了。
中午润去了 tjb 的宿舍呆着。
下午是 zky 和 gyc，这个不好评价，感觉坐后排听不清一点也看不懂一点，归根结底还是菜了。
旁边人在用我的电脑看别的题的时候吸引了一位热心外校同学。
晚上开幕式。
开场的学军民乐团是真的厉害，有种这个乐团水平可以上正式音乐厅演出的感觉。
致辞感觉一切正常。中途意外插了一个 zky 的。
“祝评测机可以运行顺畅。”
（全场爆笑并掌声雷动）
回酒店摆。
Day 2（5-18）
要来力。
9:00：试机启动。
桌子上摆了四张卡片，以供召唤监考老师。旁边有午饭。
原来不发题？那就随便个线段树和 Dinic 吧。
10:00：rp++。
T1：一棵树，每一轮会依次删除它的一些叶子。有
M 个人，每个人会分别将每一轮内被删除的叶子随机排列。现给出m 个人排列后的结果，求最多有多少轮。1 \le N \le 10^5 ，1 \le \sum NM \le 8\times 10^5 。T2；一张 DAG，每条边上有一辆列车在
A_i 时刻出发并在B_i 时刻到达，坐上去花费为C_i 。你可以在任何一个点等车，但只能通过坐车移动。你有W 顿饭，每顿饭需要在[L_i,R_i] 时刻内吃完，饭可以以任何顺序吃，车上吃没有花费，在第i 个点吃的时候花费为T_i 。求0 到N-1 的最小花费。0 \le 所有数\le 10^9 ，N,M ,W\le 10^5 。T3：通信题。Alice 收到一个数
X ，需要将其编码成一棵n\,(2 \le n \le 5000) 个点的树并传递给 Bob，中途会丢失至多\left\lfloor\frac{n-2}{2}\right\rfloor 条边，Bob 需要根据这棵损坏的树求出X 。1 \le X \le 10^{18} 。
你说得对，但是 T2 T3 这个 Subtask 区分度是认真的吗？
10:05：T1 一开始以为只用看每个点出现的最前位置和最后位置判一下就好，看 T2。
10:35：T2 想了一会不太懂，看 T3。
11:00：T3 想不到 Sub2，先开写。然后意识到 T1 如果按我现在的做法就压根跟树没有关系了，所以还得看树上关系是否合法。
请问：每次删除树上的一个点，那么询问一个点的后代中删除最晚的点要怎么做？
答：拍到 dfs 序上直接线段树求最大值。单
这时的我：主席树二分！双
哈哈。
11:40：写+调完了主席树。并且 TLE 83pts。
然后发现这个玩意直接线段树就做完了。
哈哈。
继续随机乱想 T2 T3。
12:50：
我左边的神仙：（举手）请问 AK 了可以提前离场吗？
周围一片人：？？？
工作人员：你等等罢。
13:00：目前会 T2 的
13:15：Sub1 写完过不去。
13:30：瞪不出来去搞 Sub2 和 T3 Sub1。
13:45：都过了，回来整 Sub1。
13:55：发现由于要对边建图导致出现巨量
14:00：过了。冲 Sub2。
14:30：过了。再想了一下感觉按目前这个做法没有前途。时日不多，冲 T3 Sub2。
15:00：冲不了一点。
应该不会打铁。
lyj 把 T3 过了，乱搞之神/bx/bx/bx。
tjb，zjh，默哀。
T3 都是什么神仙做法。怎么感觉成人均题了？很不妙。
晚饭非常离谱。看起来是周六学校没人然后给我们整了点好的。什么炸鸡披萨可乐小龙虾关东煮全上了。
“为什么这个糖醋排骨有臭袜子味？”
晚上极早地回到了酒店。
ABC 选择 unr 然后倒开。
E F 秒了，D 纯唐，G 绞尽脑汁然后整不明白。
Day 3（5-19）
上午讲座是什么神仙语言。感觉可能很有用但是我开场就掉线了。然后神游了一个上午。看起来很多人逃掉了课。
午饭又重回平常状态了，甚至可能还差一点。
润去 tjb 宿舍。没事干于是将昨天发的牌拼成了如下样子。
并临摹了邻床的一坨被子。感觉布料的作画难度还是太高了。
下午 hlt 讲网络流。听得最明白的一集。
sjy 讲构造+非传统。精神状态最炸裂的一集。
走的时候想尝试克服一下社恐障碍于是去问了下前面的人的洛谷号。
闭幕式不好评价。
（APIO 主席总结）
主席：本次中国区比赛金牌
74 名，其中满分56 人。（掌声雷动）
主席：T1 的平均分为 97.3 分。
（掌声雷动）
主席：T2 设置了较多的子任务。
（掌声雷动）
主席：T3 有
103 人通过。（掌声雷动）
（CCF 主席致辞）
主席：我们这次出的非常好。
（掌声雷动）
主席：我们希望 NOI 的题目质量能向这次 APIO 看齐。
（全场一片卧槽并且掌声雷动）
Au 240，Ag 200，Cu 115。不好评价。
据旁边同学所说，115 的有一位去年金牌和一位 CF LGM，又不好评价了。
三个颜色的不同分数都不超过四种，更不好评价了。
走的时候 hxh 没来于是我跟 zjh 和 lyj 先走了。
然后我旁边的 zjh 从袋子里掏出了手机然后发现不是他的，但是他兜里又有他自己的手机。
二脸懵逼.jpg。
这时我后面原本应该由 hxh 坐到的位置上的人突然发现不对，并把那部手机拿来看了一下，发现是他的。
四脸懵逼.jpg。
又问了一下发现他们两个报告厅上正好坐在一起。
还挺巧的，要是 zjh 上了前一班车或者 hxh 上了这一班车又或者是 zjh 没把手机拿出来或者这位同学没正好坐到 hxh 的位置上，这部手机基本就寄了。
晚上为了不把美好的时光浪费在等电梯上遂去大堂的钢琴上弹了几首，感觉手感非常抽象。
Day 4（5-20）
润了。深航还是很好的。
第一次连着出去打这么久的比赛。
虽然基本不算崩，但其实感觉整体状态并没有到一个自己足够满意的水准，降智操作还是不少的。
菜就多练，下次再来！
一些后记
卧槽我硬盘插在 pkusc 酒店的电视上没拔出来。
原来 apio 坐我左边的那位是滴叉？？
卡线金钩了。
讲座加到洛谷号的那位大神在同年 NOI 顺利获得了金牌，祝贺。