PKU/NOIWC2025 游记：星夜狂想

· · 生活·游记

13th

乘坐地铁首班车到达机场。CA4553 CKG->HGH。

下午从酒店骑自行车花费约 2h 到达绍兴城区，发现鲁迅故居已经关门了。于是简单观察了一下三味书屋，遂返程。晚上去 zyf 房间玩了一个神秘文字解谜游戏，还看到一套女装。

如图是阳明故居附近的小路。不知道为什么绍兴和余姚要抢王阳明。

14th

上午去 PKU 报道，大规模遇到 hba 选手。

下面是下午的考试记录。

T1 一看题，玩了两个简单的数据发现玩不出来，于是跳过。T2 是神秘数据结构，尝试扫过来扫过去都扫不出来，最后搞了一个 O(n^2\log n) 的线段树，获得 24 分。T3 对着特殊性质搞了一圈发现分析错性质了，最后只有 Sub1 暴力 SG 函数的 10 分。

然后注意到 T1 可以转化为完全图上选最少的边染色，使得任意大小为 x 的导出子图中至少存在一条边被染色。对 x=3 的情况打表输出方案发现选边方案恰好形成两个大小均匀的团，结合 x=2 的情况猜测是把图分成均匀的 x-1 个团进行染色即可，合法性显然，于是尝试并通过了 T1。

最终得分 134。

晚上去万达吃饭，尝试了古茗的姜黄新品。感觉不错的。

15th

上午水了一节讲座，面到可爱的 1-96。中午对绍兴一中的宿舍情况进行了考察。

下面是下午的考试记录：

T1 是交互，考虑这些操作能组合问出来的信息。注意到变量太多，不妨主元固定两个点 x,y，通过 n-2 次询问可以找到该链上最大子树深度对应的点 p。这个点在某些情况下是直径端点，若不是，则以 x,p 固定再问一次得到另一个点 q，则 q 一定是直径端点。比较 p,q 在询问时得到的子树深度，较大的一者是直径的一个端点。此时，固定直径一个端点和另一个点，可以问出另一个直径端点，于是做到 4n。

考虑一些优化，你发现若 p 是直径端点，则第二个 n 固定 x,p 的询问已经完成了第三个 n 需要干的事，下一次询问 p,q 即可；否则考虑固定 x,q，可以证明问出来的结果一定可以是 p，同样问 p,q 即可，于是做到 3n。前两个 n 需要用 in 特判链长度等于 1 导致询问出来的最小值不等于链长的情况。

T2 发现了一些性质，先写了 c=1，再尝试写了 O(n^2)。很遗憾似乎因为某些细节问题，没调出来。

T3 写了一些搜索和 dp，获得 36 分。

最终得分 147。

晚上仍然去万达吃饭。

16th

上午去酒店附近的瓜渚湖散步。日行一万步，健康一辈子。成功走完了一圈。

中午和北京来的大部队回合，进行一个饭的吃。

下午去了鲁镇一套的景区。有大量人在那里团建。

晚上在万达广场与 zxx 家长群的家长们完成会见。成功见到可爱的 KE。

17th

前一天走累了，上午在酒店睡觉。下午去报道，晚上参加了开幕式。最好看的节目永远是杜子德讲话。

我说不一定！

在宿舍门口成功捕捉 irris。线下的 i 宝好可爱！

18th

上午听 zak 讲随机化（1/3）。下午是高级图论。

吃完饭之后在天台上看到日落。于是进行了随机拍摄。

日薄西山，气息奄奄。人命危浅，朝不保夕。

晚上营员交流观测集训队选手与时间赛跑。

19th

讲了神秘 AI 和 Kubic 的思维题。晚上成功领取密码条，但注意到密码条上并没有密码。

20th

考试日。注意到 T1 的名字是猫~娘~粮。

下面是考试记录：

T1 在读题过程中注意到加粗的“值域在 1\sim m-1”，以及每种猫粮袋数竟然都恰好是 n！于是得出每只猫恰好两袋猫粮的结论，接下来就好做了。

T2 一眼看上去很吓人。在 B 性质下，观察到一个从高往低的决策顺序，每一次只会把 0 变成 1，于是获得了一个 28 的搜索。想了一些进一步的策略，但没有进展，先去开 T3 了。

T3 首先离散化的观察是显然的，于是有 40 分。为了简化运算，我把原来的单点操作泛化成对每一个点都进行前后缀的修改，然后发现这样的操作是相当难以维护的，曾考虑了用吉司机线段树维护斜率等各种奇怪东西，还是维护不出来（现在看来，把单点修改变成全局修改的行为是相当不合理的）。于是我先用最开始的单点修改的思路写了一份暴力打算继续想 T2。当我写完后，对着式子观察了少量时间，发现把带 m 的项拆开后分别维护，是可以简单整体 dp 的！于是随便写了一个线段树就过了。

很遗憾的是，最后剩余的时间大概只有 20min，没有做出更为有效的观察。最终得分 228。

晚上文艺汇演进行了《锦鲤抄》的唱。台上听伴奏声音好小！基本听不见。

assgin3 组合的蜂鸟有点疯的。

21st

再次讲随机化与算法设计，较为困难（2/3）。下午听花花的科技。

晚上去 9107 唱歌，并进行 gen 的打。太困难。

22nd

上午是高级图论科技。下午怎么还是随机化？？（3/3）

晚上去简单观察了一下模拟答辩。

23rd

上午集训队答辩。杜子德的提问好有意思啊哈哈哈。

最后还是传统的 1234 进国家队。dx 没进有点可惜啊！

下午颁奖，成功获得 Ag。

晚上好无聊！找了个天台唱歌。忘了哪天在一个视频的 BGM 听到一首歌非常好听！是周慧敏的《最爱》。翻出来唱了几遍，感觉歌词写得很好啊！

潮汐退和漲 月冷風和霜

夜雨的狂想 野花的微香

伴我星夜裡幻想 方知不用太緊張

后面还有一点尾巴晚点更新。

24th

上午在学校随机游走。10:30 左右集合去门口拍合影。然后把大件行李扔到萧山。

然后和 zxx、szm 找了个地方吃烤肉。没有叫到 irris。

饭后 szm 打车去绍兴北了，于是和 z 宝一起坐地铁去杭州，路上遇到了 dx 和 sk。

最后在建设三路下车换乘，和 z 宝说再见。

还记得去年 PKUSC 也住在建设三路附近。那是一段旅程的开始，现在，他又是一段故事的结束了。

3U8088，准备回家......

（写到这里的时候在机场等待登机，前序航班似乎晚点了。）

后面还有一点尾巴晚点更新

正点到 T2 啦！不过行李出来好慢/shui。

后记

从前面的歌词里摘取若干关键字，给游记取了名字。希望这段旅程中的一切美好都能成为未来路上的星光。

在最后贴上这次换到徽章的全家福。

祝大家新春快乐！