pkuwc游寄

· · 生活·游记

Day1

见到了六年级大佬，感觉被单调队列了。通过讲座第一次知道 pku AI 好像比 thu 牛（？）。

试机赛怎么这么难，T2 一分没拿，好在 T1 勉强切了。

开打前就敲了一个头文件，其他蓝的敲，直接睡了。醒来后开的 T1，思考一下发现 a>b+1 是不难的，其他情况大胆猜测 \frac{(a+b)\times(a+b-1)-a\times(a-1)}{2}+1，提交发现还过了 a=2 的点，手推了下 n=3 的情况，大胆猜测尽可能平均分成 a-1 个完全图，过了。

然后开 T2，怎么是困难数据结构题，跳了，看 T3。T3 读懂题面后感觉很难，滚回去把 T2 24pts O(n^2\log n) 的暴力跳lca+暴力去重的代码写了，继续想了一下后感觉一点不会，去开 T3，此时 1h30min。

T3 直接思考特殊性质，一番思索后无果。尝试写 O(nmk) 暴力 dp，dp_{i,j} 表示从第 i 个点开始，从第 r=j 时能否获胜，从它的所有可达节点转移，写了没过，此时 2h30min，非常恼火。

想了一下后突然发现要强连通分量缩点，然后就成了一个 DAG，然后注意到对于每个点它所有的可达节点所有可能获胜的 r，它的直接子结点一定一定包含所有这样的 r，强连通分量内的转移和孤点特判一下就可以做到 O(mk)。花 40min 写过了 20pts，感觉这就是最终得分了。

由于不会 T2 继续想 T3，于是发现特殊性质 B 只有最小能达到 r 的是重要的，直接分讨一下好像就对完了。10min 写过了 50pts，又 10min 写过了 75pts，还有半小时尝试推正解，未果。

Day1：100+24+75=199

Day2

上午非常好讲座，和在大学听讲座一样（什）。

比赛先开的 T1，拼尽全力无法战胜，1h 了还是 0pts，这也太难了。看了眼 T2，我测怎么我连 O(n^3) 都不会，就写了个 c=1 的贪心跑路。T3 直接打 O(nb\ln(n)) 暴力 dp，7s 跑不过 n\le 5\times 10^6，b\le 40，只拿了 n\le 10^6，b\le 40 的点，回来看 T1，此时 2h。

瞎构造了一番，我好像会 4n 了，直接开写，这时还有 1h30min。

开写后发现这代码难写的跟什么一样，思路是随机选两个点（其实是 1 和 2），找到一个 离这两个点路径深度（距离）为 1 的点，然后利用这两个点找到与 离这两个点路径深度为 1 的点 的相邻的点，再找到离 离这两个点路径深度为 1 的点 和 离这两个点路径深度为 1 的点的相邻的点 的路径最远的点，再找到和 离离这两个点路径深度为 1 的点和离这两个点路径深度为 1 的点的相邻的点的路径最远的点 的相邻的点，再找到离 离离这两个点路径深度为 1 的点和离这两个点路径深度为 1 的点的相邻的点的路径最远的点 和 离离这两个点路径深度为 1 的点和离这两个点路径深度为 1 的点的相邻的点的路径最远的点的相邻的点 的最远的点，此时 离离离这两个点路径深度为 1 的点和离这两个点路径深度为 1 的点的相邻的点的路径最远的点和离离这两个点路径深度为 1 的点和离这两个点路径深度为 1 的点的相邻的点的路径最远的点的相邻的点的最远的点 和 离离这两个点路径深度为 1 的点和离这两个点路径深度为 1 的点的相邻的点的路径最远的点 即为所求（？）。

但是还需要特判 n=1、n=2、两个点相邻的情况、没有深度为 1 的点的情况、最远点深度为 1 的情况、最远点就是初始两点之一的情况等，最后还剩 30min 才把代码主体写好，加上交互库有 300 行。

过了样例一交，WA 0pts。

使用瞪眼法观察发现样例里点 1 和 2 一定相邻，于是手造了一个这个 case。 发现 ansWA 了，原来是没找到深度为 1 的点，原来深度算错了，交一发 WA0，继续手造 hack，又 hack 掉了。 哦哦，特判深度为 1 的点为初始两点时特判错了，交一发，WA0，此时还剩 13min。

造了几个 hack 都过了，于是开始静态查错，发现最后一次找最远点时，如果恰好是初始两个点就错了，这时只剩 7min 了，只能尝试改成 6n 或更劣的，改改改，改完了还剩 5min，再不过就要 day2t1 爆0了。

我测，还是 WA0，这下真完蛋了。

这下盲猜错在了 1 与 2 相邻上，先来随便造个 hack。 怎么过了，再造一个。 我测，ansWa 了。我测，我求出来的最远的点有什么作用吗，烧烤一下确实没作用，那路径上的最小值有作用吗，也没用到啊，那我再跑一遍是为啥，我测，原来敲错变量名了，赶紧改，改完了，我看着电脑上的 17:00 陷入了浅浅的沉思。

我电脑时间快 1 分半啊，交一发，怎么评测怎么慢。

最后还是 WA0 了，D2T1 一分没得。

但这是我的想象，最后过了 50+pts，评测完时间是 16:59:07 左右，我非常激动所以直接不小心把窗口全叉了。

然后我忘记我每题具体得多少分了。

如果有好心人记得的话可以告诉一下。