PKUWC 2024

· · 个人记录

------------ ## day -1 随机游走。重庆不愧是山城，让人体会到自己是三维生物。 看到一所建在悬崖上（？）的学校。在这上学的同学们如果 【】 了是不是可以直接 【】，解锁新的 remake 方法了属于是。有点丧病。 ## day 1 报到。合影。试机。座位在 $\textbf{c}\color{red}\textbf{rying}$ 旁边，压力倍增。 听说试机题三年没换过，怎么这么懒。 听说 goodier 终于（。）会了试机题，做法听起来比我的牛。 听说模二意义下 $(1<<k)-1$ 可能会是负数。 xsap 成为了【**高贵的 RDFZ 教练**】（有官方认证的红色教练牌哦），看起来真的有点叶师傅的气质，不过没拍下清晰的照片。(⌒▽⌒)。 试图去贵宾接待室/教练休息室，但是笑场了。哈哈哈。 好像忘记写打 generals 的亮眼战绩了，那就不写了。 ------------ 开题，期待一下有没有我喜欢的随机化题？ **T1** 似乎是括号串手玩猜结论。玩出来合法括号串是后手必胜的充分条件。 想了想基于括号串变化的连续性，一个不合法括号串必然有合法的前后缀（当然包括空串），所以前面的条件也是必要的，所以签了到。 **T2** 看起来很神秘，完全感受不到正经做法是啥（线性规划？数论？），那正好随机化。 写了随机数据生成器。写了随机调整。通过了 sub 1。 把随机调整改成随顺序贪心调整，还是只能过 sub 1。 修改初始值的范围，贪心策略变成从大到小随机地倍增。本地 $n\leq 8$ 基本都跑出来了，调了几发过了 sub 2。 $n\leq 14$ 出解概率好像不太高，似乎也没办法优化了，尝试 T3。 **T3** 按照题目描述一步一步写就可以获得 40pts。 **T2 T3** 换着看了一百年。 忽然找到了 T3 从子树向根考虑的贪心方法，于是对 $S_1$ 判定可以做，但计数还是很困难。 **T2** 把贪心调整方法改成之前用过的随机三分（我觉得把许多完全错误的方法在随机化上乱拼往往比较合理）到比较小的范围然后暴力查，从前三优解里面选一个。本地出解概率大概到了 $90\%$，但是交几发还是过不了 sub 3。 胡乱调参，本地最高连续三十秒都能跑出解，但一直交到提交次数上限还是过不了 sub 3。( ；´Д｀) ------------ 旁边的超级大神也不会 T2。 考完之后有人跟我说 T3 是简单题（？我无法这么觉得，但是可以膜拜他，orzorzorz。 T2 是区间 dp？dp？dp？dp？dp？？？有点太神了。 ## day 2 goodier 发动了技能「自我开盒」：【大家好，我是bezzfdr】。有点没绷住。 路上见到不少很可爱的猫，但是它们不理我。喵喵喵。难道是我发出的猫叫声不好听吗（？yiw（ ------------ 理论上来说，今天是不是要来【数论】【计算几何】【ETT】了？如果不能放阳间题的话就让全场都保龄吧谢谢喵。 **T1** 只需要用 1,2,3,4 拼出 5,6,7,8（四方 dp）是显然的。然后直接找正确贪心策略是困难的，但是根据拍子猜结论是容易的，于是签了到。 **T3** 扫描线把序列和时间轴换一下是最近见过的 CF 套路（我在 Hello 2024 F2 口胡的暴力 ds 做法？交换之后用 segbeats？），然后单点修维护对栈的操作序列。 ——这个我好像也见过？goodier 给我看过加强版（相当于多个栈，还要哈希，这次 T3 啥都不需要），名为 CF1340F，那么貌似用我当时口胡的单侧递归线段树就是对的。 先打 sub1 暴力，然后冲正解（冲不出来也没关系，因为 sub2 和 sub3 可以在里面一并写出。）然后幸运的是冲完了，以及我双 log 怎么不到 100ms，数据随机的话范围能不能开大点。 **T2** 暴力和 m=2 都不难。最后 1h 发现可以按照值域填数状压，$O(nm2^n)$，尝试卡常过 $n=22$ 未遂，不过已经够了。 ------------ 这赛季每场考试均识别出了一道原题，运气有点太好了，希望没有把省选的 rp 耗光。 ------------ ## ？ 一些与考试无关的事情。 这次有家里老人陪我来重庆，感觉很是开心。 个人家庭原因（？，以前在具有象征团圆意义的月亮下面总会破防，但是这次没有。记得前几天看见颇为美妙的星星和圆月，忽然觉得， 月亮依旧会洒下最皎洁的光辉，就像无所谓缺过什么那样。 就当作提前过年了吧，希望我喜欢的和喜欢我的亲人们/朋友们在新的一年里都平安顺遂(≧▽≦) （完）