PKUWC 2019~2020 游记

· · 个人记录

我也不知道是 2019 还是 2020。

预测得分：0+0+0+0+0+0=0

既然收进集合贴了还是认真写吧

Day \ 0

上午坐火车到了北京，车上订正了一下前两题 PKUWC 模拟里面没做出来的两道题，顺便学了一下 FWT。然后做地铁去了 PKU，报道的时候前面一堆巨佬，然后领了两张饭卡和一张营员证，回宾馆。

晚上就颓了一会，想写一下线段树合并和线段树分治的板子，结果后来也懒得打了。

Day \ 1

早上开营仪式，感觉一般般，不去也行。

下午早早到食堂吃饭，然后打了个多项式 exp 优化背包的板子，因为我觉得一会肯定考多项式（事实上真的考了，但是我不会）。

到了机房先打了个多项式求逆熟悉一下键盘，然后比赛就开始了。

先看 T1，九条可怜...一点都不会。

再看 T2，显然是个带有 PKUWC 2018 风格的计数题，应该和多项式有关，想到了枚举最大最小值算概率，先口胡了一个式子，可以 NTT 优化，然后发现是错的，缺了一个容斥...感觉我也做不出来了。

然后又看 T3，又是吉老师...刚开始觉得是个水题，但是想了一下发现不是很简单，看了一下 m=1 的部分分，这个很简单，稍微莫比乌斯反演一下就可以做 O(n\sqrt n)，顺便可以水掉 n,m\leq 5000 的数据，于是拿到了 43 分。

后面一直在推 T2，结果写了个 O(n^3) 容斥还写错了，只好打 9 分暴力离场。

还如不滚回去学文化课。 --- ## $Day$ $\ $ $2

早上是面试，大家都说比较轻松，我觉得也不是很轻松。

第一个和第三个老师都还是很聊得来的，第一个老师问我为什么会接触 OI，我说学过 c++，然后就和我聊 c++ 语言特性；第三个老师问我文化课怎么样。第二个老师太恐怖了，问我去过什么地方，我没去过什么地方就很尴尬，聊了三四分钟说“行，那我没什么可聊的了”，太可怕了。

中午吃午饭的时候干脆没碰电脑。

下午开题，原来想着可能 Day\ 2 会比 Day\ 1 简单一点点，开题以后发现简单的不是一点点啊...

先看了 T1，感觉这是个 SB 题，五分钟口胡算法，然后把自己叉掉了，然后又五分钟口胡了一个算法，然后就 AC 了。

再看 T2，感觉也是个 SB 题，今天对数据结构选手这么友好啊？但是不是立刻有思路，先看了 T3。

看到 T3 基本上确定了今天要用 dinic 暴力水，于是就干脆先不看了。

回看 T2，发现和单调栈有一定关系，是一个层数的奇偶性计算，一开始想的是建一个树然后做子树操作，然后分析了一下发现这个树的前序遍历就是原序列，所以只要做区间操作就可以了，然后就变成了一个线段树入门题：区间取逆+求区间乘积。写完了 T2 以后总时间大概过了 2h。

T3 又看了下发现额外边很有用，一定割掉两条，再看 n\leq 7000，那就 O(n^2) 枚举吧，然后发现问题是矩形和+矩形 \min，一开始脑子抽风了，写了个二维 BIT 和二维 SGT。交上去只过了 1000 的点，意识到要去掉 \log。发现矩形和直接前缀和一下就行了，然后这个矩形 \min 有特殊性，只要维护前缀列和后缀行的 \min 就可以了，然后就写了一下。

交了一发，7000 的点还是 TLE 了？发现这个常数很大，然后就一直卡常，从 3:50 卡到 4:30，交了 17 次，过了。

这次 PKUWC 总分 0+9+43+100+100+100=352

Day 3 结营，也挺好玩的。

首先是讲题，讲题人：

D1T2：这是我出的一道题，我们可以将答案写成这个形式，然后推一下式子，发现 h(k)=...，g(i,k)=...，我们可以很方便的用快速傅里叶变换做出来，我就不详细说了，然后是 f(x)=...，在算出 h,g 的基础上也是快速傅里叶变换一下就好了。（台下寂静）

D2T1：这道题比较简单。（真的比较简单）

D2T2：这道题，只需要建出笛卡尔树，然后做一个类似线段树合并的算法就可以了，但是我们看到考试中大多数选手都采用单调栈解决了这个问题。（我用的单调栈）

D1T1：首先想到用矩阵乘法解决这个问题。（后面我都没听懂）

D1T3：这道题首先我们莫比乌斯反演一下，这里我不详细说了因为我也不知道吉学长写的是什么（看到密密麻麻的手写数学式，台下爆发出掌声），然后我们看一下复杂度分析，因为 s_i 随机所以我们可以用积分证明复杂度是对的。（感觉我做了将近一半的分数也挺了不起的）

D2T3：我们首先普及一下最小割树，然后分析一下一定要删两条额外边，所以我们在此基础上做 n 次 O(n) 的最小割就可以利用最小割树来确定所有最小割了，但是我们看到在考试中大多数选手都采用了预处理后 O(1) 的算法计算最小割。实际上呢这道题还有 O(n^{1.5}) 的算法，但是因为 D2 要降低难度所以删掉了一档最难的部分分。（我连最小割树是啥都不知道也 AC 了鸭）

然后就是发奖了。

Q：这次哪些人拿了一等奖啊？

A：人数太多不一一列举了。xxx，xxx拿了二等奖，xxx，xxx拿了三等奖，除此之外都是一等奖。

我一等，寻思着是不是看我初三，所以送了个安慰奖啊。

之后和同样一等的 gyr 聊了会天拍了个照。

收获品：3992977412(=4\times 998244353)，27 条可怜， 3 座火山，1 张没什么用的奖状和 3 天白吃白喝。