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(nsqrt n)),顺便可以水掉 (n,mleq 5000) 的数据,于是拿到了 (43) 分。

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

(Day 1) 只有 (0+9+43=52) 的可能只有我了。

还如不滚回去学文化课。


(Day) (2)

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

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

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

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

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

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

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

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

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

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

三道签到题,人均 (300)


这次 (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 imes 998244353))(27) 条可怜, (3) 座火山,(1) 张没什么用的奖状和 (3) 天白吃白喝。

原文地址:https://www.cnblogs.com/ix35/p/12101532.html