PKU/NOIWC2025 游记：星夜狂想

13th

14th

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

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

最终得分 $134$。

15th

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

17th

我说不一定！

18th

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

19th

20th

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

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

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

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

21st

22nd

23rd

潮汐退和漲 月冷風和霜

夜雨的狂想 野花的微香

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

24th

后记