2024.5 五月征汴游记三合一

· · 个人记录

前言

难题熏得信人醉，直把杭州作汴州。

五月征汴，就是 5 月去杭州参加的 3 个 OI 比赛（清华营、北大营、亚太赛）。

THUSC

5.11

凌晨 2 点到余姚，早八神志不清醒犯蠢没买餐券。

试机赛熟练打出元旦激光炮，还记得上次是贺的 uoj 题解。T3 神秘造计算机题，不想管，交了个 666 拿了两分，润。

没电梯的 5 层考场哪个逆天设计出来的。

T1 什么神秘计数，跳。

T2 像是很厉害的构造，跳。

T3 像是高妙图论题，跳。

T4 怎么真是造计算机，跳。

跳了一圈回到 T1，坚信 T1 可做！

能量敏感度 l=0 似乎拆位就行，还有免费的 5 分暴力。

考虑 l=0 减去 \le l 部分，好像可以数位 DP？诶等等，直接统计 \ge l 就行。

$ O(Tw2^{2d}d) $（$ w= \log n_i =60 $）算法设计出来后，调了好久，因为状态量实在是大并且转移很复杂，不太好观察调试信息，造了几组 $ d=1 $ 方便观察。 交上去 75 分，卡卡常到了 85 分，先开 T2 吧。如果能完全自由构造的话可以构造 $ a...za...za...z $，就是我们每次考虑对于一个串找到匹配位后的最晚一个首次出现的字母，作为下一个匹配位，显然 $ a...z $ 平铺最优。考虑到当前串按照这种方式匹配到多少位置，余下的部分补成完整的 $ a...z $，之后不断平铺。 交上去，因为 0.5s 怕被卡常使用了二进制压位当存字符串的桶子，lowbit 找未出现的字符。居然过了。 回到 T1，发现这个 $ d $ 感觉有希望优化掉！对于每个数字第 $ w $ 位某种异或方式，总异或和的变化可以预处理，维度和敏感度的是否大于或小于的情况可以用位运算实现。优化掉后效果明显，样例 3 只有 0.3s 就过了。 过完 T1 后，T3 感觉不可做，直接拿了 12 分暴力走人。 T4 前四个点是加法构造，二进制快速乘喜提 4+3+2+0=9 分。手玩到了 10 左右的时候就烦了不想弄了。 第五个点很整齐，似乎是区间求和！线段树 10 分搞定，限制真的松。 因为空间很大，构造一个数字的代价本质上是构造过程涉及到数字个数，考虑记录每个数字一种最优构造涉及的所有数字的集合，然后把每个数字拆分成两个数相加，集合取并集就是这个数字的构造代价，取最小就行。 这个东西感觉很启发式，喜提 7+5+4=16 分，比较符合预期。 最后 30s 的时候，突然想到可不可以让拆分尽可能接近这个数的一半，效果明显，变成了 10+10+9=29 分，不过最后没时间提交了，悲伤。 Day1：100+100+12+26=238 分，群里大众分好高，害怕。 有人说 T1 略小于 T3，只打了暴力，呜呜呜。 ### 5.12 工程题翻盘！ 怎么又是游戏策略设计。 提交次数很足，好评！ 120s 总时限居然允许交 15 发，为评测机（鸭）捏一把汗。 T1 T2 居然是普及组小模拟！工程题总算不用拿超底分了。 先看规则介绍，弄不太清楚黄格子的困难模式限制，空格串不太好读，T1 弄了半个多小时。 前两题用了这么长时间，规则都弄不明白我还咋翻盘啊/kel T3 比 T2 水，因为没有 hard mode 的诡异限制，暴力搞定。 发现 T2 黄格子判定有更新，虽然不太确定交上去的 100 是 pretest 还是 system test，还是改了改。 看技巧介绍，感觉写得都比猜词的题解详细。懂了，工程题就是锻炼看题解能力。 信息熵统计很暴力，因为 $ T $ 很小，因为没有非法串所以 hard mode 也不难搞。 T5 不就是猜词吗？给了答案可行性加权和长远期望计算两种路，根据上次的经验多个提示（上次是上下界/信心树/神经网络）写一个就行，我选择更好弄的答案加权（因为看过猜词题解，题解里给的就是答案加权）。 只考虑信息熵拿到 82 分好成绩，自此我们凭借读题和普及组模拟能力拿到 482 分！ 加上答案加权，效果明显，直接搞到 90 分，调了参之后到 96 分。 考虑对两个 sub 分别设计参数，sub1 限制严扣分多先搞，估价函数是 $ f(x)=k \cdot ans(x)+mix(x) $，$ mix $ 表示信息熵，$ ans $ 表示猜测词成为答案的概率。 $ k=8.5 $ 时过了 sub1，sub2 49.41 分，考虑继续优化。不过最终评测好像是确定的单词，本地随机性很强分数波动很大，调参非常痛苦/kel 最后用二分逼近甚至试到了 $ k=6.67 $，因为本地随机性太强了所以调参也很难准确，后来用和我类似的估价函数的群友说是 $ k=4.5 $ 时能过，考完试出来后有老哥告诉我直接可能成为答案的猜测词加一个常数都能过。 Day2：100+100+100+100+99.41=499.41，两试总分是 $ 737.41 $ 分，二试很多人都是超高分段，群友有 $ 750+ $ 的，好紧张，不会又是二等吧。 等约非常漫长。 最后学弟告诉我我喜提一等，爽！ 明天北大营加油！ ## PKUSC ### 5.13 试机赛居然换题了，不会，暴力离场，暴力因为变量弄混调了好久。 文渊午餐是真厉害（懂的都懂），达到了世界餐饮最高标准——牢饭。 T1 怎么和上次夏季营一样还是字符串，看起来有点厉害的样子。T2 感觉有点计算几何，T3 最大权独立集的一些模型可能是典，但是我没接触过，只会树形 DP 暴力求解。 T1 感觉枚举下的位置没前途，回文考虑枚举中心轴，然后解决了 sub2。突然发现中心轴确定后回文串的一端就确定了，另一端也确定了，直接二分哈希搞定，封装了二分哈希函数。 要分为奇数/偶数长度，中轴在上方还是下方甚至中间，还有是否往下走过，一次过了/kel T2 一开始看成正方形必须四边与坐标轴平行，想着北大营为啥这么送，突然发现正方形可以斜着，我小丑/kk 没学过计算几何，根据平时的印象猜测凸多边形边界及内部与每条 x 轴重合的部分只有一段，考虑求出边与 y 轴平行线交点之后得出所有合法点。 正方形可以枚举两个点确定，研究了好久怎么计算出旋转后的坐标。$ O(V^4) $ 喜提 15 分，过了 $ V \le 15 $ 的 sub。 自测了一下 $ V=300 $ 的满正方形，发现带着 O2 优化 8s 左右就跑完了，有戏！$ O(V^4) $ 卡常的话先加点 inline，优化到了 6s 左右。判断很繁琐考虑直接弄出第二个点坐标的范围，毕竟是凸多边形，并且根据主从联动的结论确定第一个点的坐标和第二个点的一维坐标后第二维坐标范围必然是一段连续的区间，省去了很多判断，$ O(V^4) $ 怒过 $ V \le 300 $。 根据分值越少的 sub 越仁慈的规律，打算搞搞 sub1。因为是长方形所以算范围时还有点麻烦，发现 $ V \le 2000 $ 时 $ O(V^3) $ 过不了（悲） 莫名想到小奥正方形计数问题的策略，枚举边长，直接枚举某条边的 $ x,y $ 跨度，$ O(V^2) $ 解决。 最后 20 分钟不到，冲了一个 T3 的 11 分暴力，有惊无险。 感觉 T3 设计一个状态为点位、不选时 DP 值、选时 DP 值的树形 DP 还能拿点分，但是没时间了。 Day1：100+45+11=156，感觉如果不在 T2 耗那么长时间的话（我 T1 1h 左右就搞定了）T3 还可能可以多冲一档 24 分，不过也算还可以。 Day2 加油！ ### 5.14 T1 找周期，神秘结论题；T2 像是清新 DS？T3 像是乱搞题。 先死磕 T1，暴力 15 分，树形 DP 拼上去 35 分到手。 考虑正解，感觉像是树形 DP。但是拍了组 $ n=10 $ 全卡掉了。 用提交反馈得到没有无解且都是 2 的次幂。 感觉 2 的次幂比较整齐，可以很容易求出周期。 正难则反，想到排水系统的思路，从上往下分权值，意思就是把 $ 2^n $ 个物品放到点 $ 1 $ 后这个点会有多少个物品经过。 这个均分就行，用二进制压位高精度实现。 最后根据经过物品数量的 lowbit 求出周期，用十进制压位高精度（在树形 DP 中实现）即可。 此时已经过了 2.5h。 T2 考虑分块拿点分，写挂了调了好久，还被卡常了，寄。 T3 spfa 没写完，耻辱。 Day2：100+10+0=110。 希望大众分别太高。 ## APIO ### 5.18 比赛日 5.17 讲座好难/kel T1 考虑贪心最短前缀，记录入度之类的，无罚时过。 T2 好复杂，跳。 T3 考虑设计刻画一个数的信息，$ fa_i < i $ 想到取模 CRT，可以暴力跳，1 罚过。 T2 考虑 bus trip 类似的 DP 套路，10 pts。 T2 30 pts 不会，摆。 闲着没事写个乱搞，被 sub 依赖卡了/kk，数据点分治也救不了。 100+10+100=210，T2 部分分是真的少。 邻座老哥没调出来 T1，一车人没切 T3，但切 T3 的还是比想象中的多。 希望有金勾。