PKUWC2025游记

· · 生活·游记

从来没有用过这个功能，今天来试一下\\

100+77+0+89+49+24=339，应该是要获得p营的第3个优秀了

前言：NOIP2024斩获236高分，比NOIP2023低8分，比CSP-S2024低136分，THUWC根本过不了审，还好去年PKUSC有个良好

Day 1

省流：被 T1 硬控2.5h，T2 怒写8K被卡常，T3输出无解得0分

上午是报到，报完到就润回酒店了，开幕式就翘掉了\doge\\

试机是 12:20-13:00，试机的时候发现试机题居然变了，变成了PKUWC2024 Day2T1 和元旦激光炮（交互题）， 是不是今天要考交互了？

\\\\

试机题就只写了交互题10分，然后把对拍的模板写了一下，然后 13:00 就开考了。

$\\$T2 10分钟秒了一个 $O(n\sqrt m\log n)$ 的莫队算法，然后好像突然明白T1怎么做了，可以花 $3$ 次把1个有电和2个没电的一起丢掉，然后回去改T1，一下过了 $a,b\le4$，然后改成 DP，每次枚举丢掉的有电电池和没电电池数量做到 $O(V^4+T)$，交上去有65分，然后不太会优化，卡了十几分钟常就过了（？）$O(1000^4)$ 200ms就跑完了 $\\$然后开始写T2的 $O(n\sqrt m\log n)$，写完就过样例了，特别厉害，交上去获得 $l=1$ 的17分，发现是删除从添加复制过来的时候忘把+1改成-1了，刚好过了不需要删除的17分。改了之后交上去T成41分，本地造了个随机数据 $n=5\times10^4,m=2\times10^5$ 要跑12s，然后狂暴卡常20分钟变成4点几秒，还是41分，这时候还剩40分钟左右，又看了眼T3，觉得最多只会20分，不如继续卡T2! $\\

于是孤注一掷做 T2，发现set常数实在太大了，想换成线段树，线段树写一半觉得找前驱和后继直接暴力在这种情况下出题人不卡应该很快，所以直接改成暴力，复杂度 O(n^2\sqrt m)，交上去77分，n\le10^5,m\le4\times 10^5 2.6秒，直接震惊到了，感觉没有必要继续写线段树了，又卡了会常，本地极限数据要4.1s，时限4s，根本过不了，犹豫要不要加火车头，最后保险没有加，害怕被赛后Ban掉，给T3输了个无解获得0分后就结束了，最后是100+77+0

$\\$T2被卡就要开始打翻盘局 今天没有交互，但是有交互试机题是不是代表明天有交互？ **Day 2** 早上的讲座去听了，比较震撼，MC好评。 下午去考场的时候电梯从 $9$ 楼到 $1$ 楼一层楼停一下，还被电梯按钮电了一下，不仅如此，酒店大门还坏了（还像是不知道谁按了紧急按钮导致它不动了），心情很差！ 到了考场发现昨天的代码跟之前一样没有被删，不用再把头打一遍了，于是没事干就开始吃东西，于是开考前把东西吃完了。 考试开始先看题，T1是交互，看起来很唐；T2看起来是个神秘贪心题；T3是一个看起来比较多项式或者矩阵的题，但是部分分看起来比较可做，感觉T1和T2切一个就能翻盘。 先开T1，很快糊了个 $O(n^2)$ 次操作一，$2$ 次操作二的做法，交上去获得了 $O(n^2)$ 的分，因为题目中就要求的只能进行 $2$ 次操作二，所以我相信我的思路没有问题！然后自信开始乱优化和随机化，开考47分钟通过了 $n\le4\times10^4$ 的分，感觉很快就能过了！我的算法是 $O(n^2+3n)$ 的，后面的 $3n$ 是跑满了的，就继续卡常，试图将 $3n$ 部分的查询次数减少。在开考 1.5h 的时候仍然只有 $n\le4\times10^4$ 的四十几分，发现自己的代码会被树高为 $5$ 的类似与菊花的东西卡成弱智，优化完全起不了作用，遂先放弃T1。 T2 先胡了个贪心，可以过样例，提交之后上个厕所冷静了一下；回来发现 WA 0pts；感觉应该是算法有问题，就先写了个 $c=1$ 的部分分用来对拍，对拍后发现直接贪心不是很对，就改成了区间 DP，枚举断点转移+部分贪心的一个神秘做法，调完通过了 $n\le500$，又重新拼上 $c=1$ 后得了49分，我感觉我的算法是 $O(n^2\log n)$ 的，于是把 $\log$ 消掉后再交，发现还是49分，测了一下发现 $n\le5000$ 的时候30s都跑不完，仔细看了下代码，发现是 $O(n^3)$ 的，这下这下了，想了10分钟怎么优化，发现不会，就先跳过了。 T3先写了个 DP，交上去有24分，然后有8分好像是卡常分，先问了一下可不可以开Ofast，他说可以，但是仍然没有卡过这8分，这时候是3h，还剩下1h，决定先回去看T1。 想到了一个用正确率换操作次数的优化，加上去 WA 0分，发现这个算法在 $n$ 小的时候正确率很低，特判 $n$ 比较小后突然得了83分（？）然后瞎调了一下参数得了89分，把 $n\le8\times10^4$ 给过了。本地测了一下，每个点在 $[1,5]$ 之间随机一个点作为父亲的树可以让我过不了 $n\le8\times10^4$，这下数据水没说了。大家的4n或5n算法都是83分，而我的 $O(n^2)$ 算法有89分\doge 最后还剩30分钟，想了一下T3 $l=r$ 的部分分，感觉应该状态数很少，但是没想到怎么搜到这些状态（不会dfs第一人）。于是考试就在与T3和T1的常数斗争中结束了，并没有拿到更多分，最后是89+49+24=162 **后记** 两天加起来是100+77+0+89+49+24=339，不知道能不能有优异（优秀应该是有了） 这次又很多应该拿的分没有拿到：先是Day1T2没有想到回滚莫队不仅可以只插入，还可以只删除所以没有想到不带 $\log$ 的做法；还有 D1T3 没有时间写的20分。D2T2平方算法不会以及T3中没想到的深搜搜状态和卡常没有卡过去的分。 这次考试问题首先在于做题的速度，尤其是两天T1这种Ad-hoc，偏思维之类的题做题速度存在这问题；然后是回滚莫队这种较为基础而又不是很常用的算法一些基本的运用都不熟练，题也没怎么做；甚至对于状态少可以直接 dfs 都没有注意到。 可能发挥的比较好的就是各种乱搞的能力了，从CSP的模拟赛开始我就发现自己乱搞好像有点天赋（至少比assign这种计数强），这次D1T2暴力乱搞和D2T1的乱搞卡次数也都证明这种能力其实还行。