PKUWC 2025 游记

lzm0107 · 2025-01-18 22:11:57 · 生活·游记

Day 0 (1.13)

下午到达酒店，按理来说应该两个人一间房间的，但我们有九个人，所以喜提大床房一间。

晚上去吃地锅鸡。

“你跟他说我们是重庆的，给我们上特辣。”

“啊？”

玩狼人杀，抽到预言家，但查了一个好人和一个自刀狼就被女巫毒了（？

晚上电脑和手机被收了，于是开始研究酒店的语音助手和电话，给 @LZYAC 房间打了两个电话结果他们没接。

Day 499122177

本来应该是 7:40 起床，然后被 @LZYAC 6:40 敲醒了，经过交流才知道我昨晚打电话时他们已经睡觉了。

吃完早饭前往龙山书院，到了之后才发现我们九个好像就我没背着包出来……

然后一整个上午都面临非常非常非常严重的水资源短缺，直到 12:20 试机前才买到两瓶水。然后考场旁边就出现了几箱水并且可以自取？

注意到考场发纸但不发笔且我的笔袋在酒店里。不过没事反正我 CSP 的时候也没用过草稿纸。 但我 NOIP 草稿纸不是写满了？不是写满了？不是写满了？

Day 1

T1

注意到这题十分熟悉，但我没管，猜测策略只有两种：

1. 将当前的第一节电池与其他所有电池进行测试直到成功或可以证明第一节电池为坏电池为止。

2. 将当前的第一节电池与第二节电池测试，不成功直接丢掉。

于是考虑 DP，f_{i, j} 表示当前有 i 节好的与 j 节坏的，最坏情况最少猜测次数。复杂度为 O(ab)。

显然错误。但为什么这题这么熟悉呢？回忆一下，原来我在去年不知道啥时候做过这题的一组 a = b = 4 的数据啊，回忆一下当时怎么构造的。

7
1 2
1 3
2 3
4 5
5 6
4 6
7 8

观察一下

1 2
1 3
2 3

它的意思是使用 3 次机会确保前 3 节中至多 1 节为好电池，然后直接丢弃前 3 节电池。

再仔细思考一下，这意味着可以使用 k\choose 2 次机会确保前 k 节中至多 1 节为好电池，然后丢弃前 k 节电池。

因为是最坏情况，所以前 k 节中必定有 1 节是好电池。

将其加入到转移中，此时复杂度为 O(a^2b)，400ms 轻松通过。虽然我也不知道为什么是对的。

T2

排序去重 + 树剖求 k 级祖先有一个 24pts 的暴力，啥也不管直接写了。

感觉可以离线询问然后枚举 x，对于每个 x 的询问像 P1972 一样扫描线处理，时间复杂度为 O(n^2\log n+m\log n)，也是 24pts。

在扫描线中将树状数组换为 O(1) 修改的分块就可以 O(n^2+m\sqrt n) 了，看起来还是过不了 Subtask3，但观察到时限给了 4000ms，由于 A 题带给我的对于评测机的信心，我决定写一下这个东西。

TLE 24pts

加了个快读仍然 24pts，跑路去做 T3 了。

T3