游记 - PKUWC 2024 & WC 2024

大概是初中阶段最自由、最刺激的一个寒假。

Day 0: 20240125

出发前，应 lzqy 拉我一把，加了一个约饭群。划重点，要考的。

飞机，同行的人有教练，还有 lzqy_、wzj33300、gyyyyx。在机场和 mod998244353 汇合。

到达重庆，机场快线的一路上首先是一段山路，让人想起跨市高速，在广州城内想是断然不会的。走了一段，忽而来了一座高山，然后路途便分成若干条立交桥，触手一般四散开去。然后就是重庆的城了。真乃立体城市！马路时有上下坡，且九曲十八弯。未曾见过有哪个城市立交桥如此多而繁复的。当车行到河上时，桥之高与滩之低形成多么壮观的落差！下了大巴要走去酒店，沿着导航却走到不存在的途径，最终不得不绕一个大圈。后来想来，导航毕竟是二维的，重庆乃是三维的。途中看见一所重度医科大学附属医院……啊，那不是度，是庆的繁体慶。

吃碗“微辣”的豌杂面，就要跟着大家去巴蜀中学校（除了我以外都报了 THUWC），期待与群友面基。对着群里一张 Phigros 暂停的照片，居然看到有两个本校学生玩双人 Phigros，乃是 Igallta AT。另一位旁观者一直劝阻。我向旁观者询问是不是其人，旁观者似乎不知情，并且称其中一位玩家为 lulu。后来才知道，这是小 l。

在板凳逐渐聚拢起一群人，我想是不是群友，经过推断八成是了，但是过于社恐，不敢打招呼。过了会跟着 lzqy 和他们一块从后山走到开封菜。面到了：

回到酒店，浴室门和厕所门半透明，且外面不再有任何遮挡，值得辱骂。

一起沿滨江路散步，看景，聊八卦。并走了个旁边的、爬山一样的路途，lzqy 买了些文创品，并且都买了瓶汽水。

Day 1: 20240126

不知道是哪个营完全没有纪念品。也不知道是谁是全校唯一一个去这个营的人。

上午查询育才中学校和陶行知的关系，然后睡觉，然后合照，然后试机，然后吃饭，然后睡觉。

试机时的一个特判，要原封不动地输出，结果先输出再输入，我真唐吧。

下午发现上午试机后没关机，.vimrc 不用重写，试机代码还在，好吧。

简述题意：

A: 给一个只有 L 和 R 的字符串。Alice 和 Bob 博弈，拿到空串者输，否则选择一个字符，如果是 L 就保留其左边的前缀（不包括），否则保留其右边的后缀（不包括）。求最优策略下胜者。$1\le |S|\le 10^6$。

B: 对于长为 $n-1$ 的非负整数数组 $a$，定义长为 $n$ 的数组 $f$ 满足 $f_i=\sum_{1\le j\le i-1}\min_{k\in[j,i-1]} a_k+\sum_{i\le j\le n-1}\min_{k\in[i,j]} a_k$。给定 $f$，构造一个 $a$ 或报告无解。$2\le n\le 80$，$0\le f_i\le 10^8$。

C: 给一个下标在 $[1,2^h-1]$ 的、数是两两不同的正整数的完全二叉堆 $a$，给出删除一个堆中一个节点删除（表现为值置为 $0$）并下沉的形式化描述。并且维护两个点集 $s_1, s_2$。$q$ 次操作，每次操作是往某个点集里加入某个数或从中删除某个数（保持 $s_1\cap s_2 = \varnothing$），或查询有多少个点集 $s$，满足 $s_1\subseteq s\subseteq s_1\cup s_2$，并且在使得 $\forall p\in s,a_p\not = 0$ 且 $\sum a$ 最小的结果中（题目强调这样的结果堆是唯一的）$a_x=z$（单次询问中给定 $x,z$）。$2\le h\le 18$，$1\le q\le 5\times 10^5$，$1\le a_i\le 10^6$。

看了一下，没有明显可做题。先写 A 暴力，然后手造几组样例，然后猜结论是如果 $S$ 是一个把 R 作为左括号、L 作为右括号的合法括号序列，就是 Bob 赢，否则 Alice 赢。然后就过了。

B 感觉太难做了，多拿一点部分分都难。一开始以为可以 $n!$ 枚举大小顺序然后高消，结果不会处理无限组解的 case。所以打了 11 pts 纯暴力就跑路了。

想磕 C。觉得策略大概是，从上往下 pop，如果本次 pop 会破坏性质，就不再 pop，然后递归到儿子。我好像感受到某种结构，但是没有抓住它。最后打了 20 pts 暴力枚举每种 $s$ 预处理。

以上过程基本就是颓一会然后写一会，所以非常久，足花了 3h，反正最后 1h 也啥都做不了，只是再证了一下 T1 说法的正确性，然后接着颓。

由于一开始网炸了，考试延迟结束 5 min。快结束时突然发现 C 还有 20 pts 是每次询问可以单次模拟，且 $s_2$ 总为空集，大意了，差点白丢分了。然后就是继续颓，直到考试结束。颓的方法是趴在桌子上，往草稿纸上写我能想起来的一切信息片，名字就力图写好看，或者是某些汉字、或英文字母、曲名等。

晚上吃家常菜，大家怎么都不吃水煮牛肉啊，大家怎么都不吃糖拌番茄啊，怎么不吃糖拌番茄然后觉得辣啊。

在酒店 22 楼出去，结果发现这个天台正连接重庆医科大学附属医院的楼……并且，讲真，22 楼的景色和 1 楼一样。

然后就是，给尺子姐姐送女装（lzqy 斥巨资采购）……嘿嘿……图像就不放出来了……

结果发现错过鸽游直播，真不行。去看了看榜，对于一些高名次……感觉真不行。

晚上完成德育作业，被评为唐。又熬夜了。

Day 2: 20240127

上午演讲，讲一些计算机语言的东西。其中推荐了 SICP 和《七周七语言》，然而这之后我就昏昏然睡了……

午餐有一个橙子、五个草莓，还有一瓶草莓味奶，这是 jao 的。

简述题意：

A: 给定 $n$ 个一位小数满足 $0<a_i<10$，每次可以将其中两个数相加后放回去、或者把一个数四舍五入后放回去，直到最后只剩一个数，以这个数四舍五入的结果为结果，求结果的最大值。多组数据，$\sum n\le 10^6$。

B: 给定 $n,m$ 和一个递减正整数序列 $d$，满足 $d_1\le 10,d_m=1$。求以 $d$ 为步长序列，$1\sim n$ 的排列进行希尔排序的交换次数的最大值，以及取到最大值的排列个数。$1\le n\le 30$。

C: 要维护 $n$ 个初始为空的栈，进行 $m$ 个操作。有三种操作：一是区间 push $x$ 个 $y$，二是区间 pop $x$ 次（若空则不操作），三是单栈询问第 $p,q$ 位的和（不存在视为 $0$）。$1\le n,m\le 10^5$，$1\le x,y\le 10^5$，$1\le p,q\le 10^{10}$。

没有明显可做题。先推推 A，发现只考虑小数位，并且只考虑初始是 1 到 4 的位，并且已经不小于 5 的会直接去四舍五入。一开始嗯算，反应了一下才发现可以由多个相加然后四舍五入。然后分讨，拍，假，然后严谨化算法，发现可以小范围 dp。考虑到这一步，我已经拿下 $n\le 12$ 和 $a_i=0.2k,k\in \mathbb{Z}$ 的 56 pts，剩下的不知道为什么错。继续卡，卡到 3.5h，不甘心，但是真的快没时间了。

B 感觉不可做，18 pts 暴力跑路。C 看出了 55 分部分分，是暴力+扫描线+吉司机线段树。于是嘲讽自己花那么多时间却 A 不了 A。最后只调完了最低档的暴力 18 pts，不再有时间了。应该没人比我低分了。

晚上嗦酸辣粉，相当不错！然后和 mod998244353 和 gyyyyx 联机 MC，第一次屠龙速通，mod998244353 带飞，%%%。然后在寻找末地城的途中 wzj33300 加入，用床把全部人炸出末地了，就不玩了。

Day 3: 20240128

短暂的休息。

和 lzqy、gyyyyx 一起去了北仓转，看文创品，那里非常安静。我们在那里转圈。吃完饭就开始出北仓，在附近乱转，所谓 citywalk。直到说累了，就回酒店，跟 gyyyyx 最后玩一玩，他要走了。

晚上跟随 lzqy 去晚餐，面到 xht、尺子、shinzanmono、CYJian。期间没有反应到 xht 是 PKUWC 监考，脸盲真不可取。红衣帅气大学生，怎么可以记不起呢。然后就是 xht 请茶颜悦色，味道很好。回来路上买了 6 个竹子上爬熊猫的玩偶（但是这不应该是在成都买的吗？），打算分给我的舍友。

晚上聊天，把 lzqy 聊尴尬了，嘿嘿嘿。最后想补点题，但是怎么也没想清楚。并且又熬夜了。

Day 4: 20240129

发的有外套，小背包，还有一大本讲义，真牛吧。

在宿舍打音游。然后去操场溜了一圈，发现三个引体向上都做不了了，真不行。

第一次留意到育才有国际象棋棋盘，那种立体的、大的。cfz 就在旁边，穿着黑丝、裙子，被大家簇拥着。自己就在外面一圈找一个地坐了打音游，Destruction 3,2,1 AT acc 达到 99.54%，rks 达到 15.94，很好。

育才美食。

开幕式太多乐子了，“尊敬的子德主席”“冬奥会”还有一两处非常精神的语气……加上群友的复读，全程绷不住，从歌舞笑到讲话再笑到最后。

去了教室走一转，看到猫猫。

然后再回去棋盘边上打了会音游。本来以为有音趴。下面也的确还有人打，一个打 4k 的，一个玩蛇的，旁边一个写代码的。期间有个女的看了看，骂了句脏话然后走了。难评。

Day 5: 20240130

上午 lxl 讲持久化数据结构，非常可爱！我所了解到新的东西有：肥节点（虽然很难写），节点分裂（虽然很没用），斜二叉堆（虽然还没会完而且也有点没有）。另外，两棵一样的 AVL 树合并，为什么是 $O(1)$ 的？

下午 xtq 讲 OI 在 TCS 中的运用，目的是为了告诉我们持久化数据结构也没那么难。不过看出来 xtq 非常有学术精神，%%%。

下午跟 ztx 去跑圈。我一开始也慢跑，后来沉不住气，越跑越快，很快已经很累，不能负担得起原来的体能消耗了。于是怀疑自己是不是平时也是由于心浮气躁，且体能不足，所以好多东西太难持之以恒下去。去饭堂路上偶遇一位大佬弹钢琴，非常熟练，%%%。

晚上营员交流，怎么人均会 Top Tree 啊。除了 ducati 听起来用处有点局限的新 technique、fzw 有实用性的数据结构合并时间复杂度分析，其他的全都没听懂，听一半跑路了。

Day 6: 20240131

上午 qlr 讲题，难度亲民，讲的也非常透彻！

但是线上的同学反映没有声音，麻烦解决一下我没有说话的问题。

但是电脑突然无法开机。

打了打乒乓球。

下午讲量子计算相关，完全没心情，但是还不能直接离校，翘了四处走了走消磨时间。

感觉育才的水龙头有点蠢了，手全是水，抹完香皂，怎么拧不带把的水龙头？

晚上试机，是 NOIP2021，写完了 T1、T2 就跑路了。归程看见 qlr 和 xtq 大战国际象棋，qlr 胜。

Day 7: 20240201

前一天晚上梦见在夜晚，一个离冼村一站的 18 号线地铁站，徘徊到底是进去还是在外面搭乘其他交通工具回去（我似乎很喜欢交通的场景）。最后好像没有进去，但是走了一段路就发现决策错了，但不再回头。

打到一辆车，司机是个壮士，但他提醒我绝对不要回头。那里大概是城中村一类，所以很有理由。然而出于好奇心，我还是回头了一下，看到一辆车在尾随，回头的一刹它突然撞来。我便把头埋下来，似乎是惊恐。这时车停了，司机下来同他大声对抗。他说回头看的都把手举起来，我并没有，于是后面那人忿然走了。

梦的后半段就不太明确了，只记得我似乎在翘文化课。想是有点关联。

A：给 $n$ 个正整数对 $(a_i,b_i)$。对于其的一个子集 $S$，先按原顺序列出 $S$ 中元素，再按原顺序列出 $S$ 外元素，形成的数组中最长的满足 $\sum a\le T$ 的前缀中 $\sum b$ 就是对应的价值。求所有集合对应的价值的总和。$n\le 200,T\le 3\times 10^5$。

B：给一个长度为 $n$ 的正整数数列 $h$，求出长度不小于二且存在正实数 $l$ 使得可以把若干 $h_i$ 变为 $l-h_i$，使区间内 $h$ 值递增，这样的区间数目。$h_i\le 10^{12},n\le 3\times 10^5$。

C：给一棵特定形态的线段树，维护的序列长为 $n$；还有 $m$ 个区间。要求数有多少个节点集合，满足确定了这些节点的值后这 $m$ 个区间的和也被确定。$n,m\le 2\times 10^5$.

A 卡了一会，一开始感觉要算贡献，但没有马上怎么推。其他路没走通后推一推贡献就做完了。此时8:47，样例过完。

B 可见的双指针，但是判定却想得很繁琐，要维护最后一个点两种策略分别的 $l$ 的取值范围。一开始猜连续，推了一推发现假了。不想写 STL，最后写了单次判断 $\frac{n^2}{w}$，双指针也没意义了，总共 $O(\frac{n^3}{w})$。

C 花了很久，认真推了一个树形 DP，然后把 1、2、3、4、8 组样例过了。打开第 5 组样例，绝望的发现树形 DP 没有前途，因为我永远不知道我到底要目标区间作为谁的子集。只是这种策略则特殊性质下倒是符合的。

但是我是蔡队的粉丝！！！

下午出分，$100+44+20$，$O(\frac{n^3}{w})$ 冲过 $n=4000$，神圣 0.907s 之力，赢。

对 lzqy 来说，这则是超低发挥了。

听完题，知道了 B $O(n)$ 做法，突然就很懊悔。我想过双指针，但是没想起来 Baka’s trick。我想过在峰点和谷点拎出来讨论，却没有乘胜追击把条件简化。就差一步。差一步。

晚上是文艺汇演，一开始是育才中学的歌舞，怎么都是女的啊，音响有点吵了。

留下最深印象的是五哥的串词，节目效果拉满了！笑不停。谁是卧底节目效果也好满，我到最后都没有猜到卧底，原来他早已看破：“LCP=1.”后来一首原神温迪歌曲真的很喜欢！音准、节拍都非常在线，除了高音气息不太稳（哎，我何尝不是这个问题）。以及 Kubic 演唱的《人是_》属实全场最佳了（除了开头的失误），副歌音色太好了。感觉最期待的 dottle《我的又一个机器人朋友》演讲冲击力不如 coffee_zzz《我的一群机器人朋友》演讲。然后就是难忘今宵之《蜂鸟》。别的都没有很深的印象。

钦佩组织者 skc 领导！

Day 8: 20240202

前一天晚上的梦，背景大概是某个废旧车库之类的，梦见很多同学，印象上很 happy。梦见 gyyyyx。梦见一个小学女同学，梦里好像她中考成绩就是我的目标成绩来着（我甚至还记得我的期末考成绩），尤其是那个物理成绩（她似乎弱项在理科来着）。我在乎导致的。

上午 EI 的课，非常听不懂，但是非常认同 EI 的数学审美。

下午跟着教练出去修电脑。店员说把显示屏的线重接了一下。本来想假戏真做（我们请的是看耳朵的病假），结果去了重医附一院，挂个号，出来 16:45~17:00，果断离场，只是可惜白费的 ¥15 了。回来接着听 He_Ren 讲题，一回来就是一道重磅 FFT，各种天花乱坠的性质。往后面还是很难，魄力，唉，魄力。还是觉得 He_Ren 很擅长讲，节奏把控挺不错的。

晚上不听困难的集训队交流，写完美的队列，写了很久才过，很多细节都要厘清楚，最后发现 bug 是 rk[k] 写成 k，真小丑。一道思路这么清晰的题目写了 2h，唐完了。此外，电脑修好了，耳机一边的套却不见了，这就是我想要的吗。

还看到若干 PKUWC 游记，有人 Day2 $56+55+55$ 翻盘，我的偶像！

Day 9: 20240203

前一天晚上梦见一个 whk 同学，另还有化学老师给我讲题来着。

上午 csy 讲随机化和近似算法，相当困难，IOI 两题讲的有点急，最难到低密度 01 背包、卡字符串滚动哈希，但是也有有趣的随机化题目。很符合我对理工男的想象。

中午更新 Phigros，性了 G.V.N.，Crush Beta 不太想打。

下午“计算机与教育漫谈”，意料之中的大量爆梗，但的确是有真知灼见、有眼界。我想，像我经常思考老师的问题，也许以后我也会选到和讲者相似的研究方向呢。佩服讲者的最高语速。顺便把 G.V.N. 收了，我是咸盐的忠实粉丝，嘿嘿。

晚上先打了个上下界流板子。启动 ABC，卡 F 了。一开始以为 FFT，发现单次点乘太慢，但是没往模数想，觉得模数应该很容易被卡。然后又以为根据相乘长度相加，有一些均摊，失败了。结果是随机模数，20-哈希。……

Day 10: 20240204

上午国家队答辩，zak 略显紧张，Kubic 稳得不得了，花花被 dzd 锐评英语不好，Rainbow_qwq 获得首个 dzd“我没有问题”，skc 一直强调自己的组织能力（我后来感觉这一点会不会有点扣分），cxy 是第二个 dzd“我没有问题”。

最后的国家队队员是 zak、Kubic、花花、Rainbow_qwq，祝贺！但是 skc\ll。

下午闭幕式，哦，原来银牌线 169，我 164 啊。好的。%%% lovely_ckj，%%% wtc。\bx。

晚上瞪 WC T2，的确没有瞪出来，罪有应得了。ARC，T2 一开始有个细节漏了，瞪了一会才瞪出来；T3 卡了比较久，想怎么构造双射，然后设一下 $f_{i,0/1}$，好像可以做，然后就做完了。T4 没时间了，赛后一下子补完了。

此外，不记梦是因为好像没做梦。

Day 11: 20240205

前一天晚上比较晚睡着。宿管怎么 7:00 就叫人起床？还说最后一班校车是 8:20？

lzqy 介绍扑克牌接龙游戏，很好玩，并且他赢麻了。跑路。lzqy_ 顺便口头 AK 校内 ACM 赛。

真不如预计起飞 14:30，实际起飞 16:05。

Day 12: 20240206

之所以要在活动结束后多写一天，是因为我发现听完题解瞪出来的 WC T2 其实是对的，并且调对了。赛场上讨论 00,01,10,11 的转移的思路也是对的，唯一不对的就是考场上我以为它有很多段区间，实际上除了 xyyz 以外的情况它就是连续的双端开区间，那么这种情况甚至不用处理。漏的是讨论峰/谷点处，当时想到却没有明确化，也没有想起 Baka’s trick，我真是差一步拿 220 的（再差一步就 225）。不过调的时候 Baka’s trick 写挂了，还是不太行。% zlt，看他的题解完全懂了。

加训，再战。