PKUWC 2020 AFOO记

因为CSP-S挂的并不厉害,蜜汁来到了PKU,所以有了这篇游记。

DAY 0

上午在机房颓废,中途还整了一个出校证。

九点多,两个THU的大神去拿笔记本和手机颓废了,不久被两个教练拉着和kx跑了出去。

似乎有一些晚(火车票是10点57的),于是直接上车开了出去(所以出校证并没有用上)。

然而车上已经有四个人,加上在外面拿笔记本的THU二人,显然并不是很友好。

然而这时突然出现一辆野生的公交车。

所以果断肉身(当然是车身)截断公交车,老吕把自己送上了公交,准备让老于送我们到火车站,自己再解决如何到北京的问题。

两三分钟后,THU的大神已经来到。

似乎这时意识到并不是很晚,所以果断撵上公交车,在公交车站再次肉身截断公交车,把我们四人都送上了公交。(所以公交车招谁惹谁了)

荡悠着来到火车站,大概四十多分,坐上火车刚刚好。

然后发现三个大神都有笔记本、手机能颓,只有我像个睿智一样干坐着。

然后发现确实是这样的,然后就自闭了两个小时。

本来说的是到北京之后和学长中午一起吃,然后发现到北京已经一点多了。

打个车到宾馆,顺便堵会车,已经接近三点了。

此时还没有吃饭,所以到超市随便颓了一点(卫龙真香)。

然而下午还要到PKU报到(此时两位去THU的大神也跟着打车去了)。

到了PKU,门卫似乎并不让进的样子。

出示报名表后,门卫表示:一个入营通知只能进一个人的这个。

于是NC大神神操作:“这个他们才能进我们是进不了的这个。”

还好教练才旁边,于是糊弄着把我们弄了进去。

于是去排队,排了一年之后终于排到,然后进去发现就并没有报名表,于是就很尴尬。

于是叫来在北大的$wzz$学长,成功找到了一个打印的地方,终于报上了名。

报名表上有一个是否选择linux选项,然后发现好像大部分人都没有选,然而已经不会用windows了,所以选上了。

晚上和三个学长在外面吃烤肉,然后得知了将一直停课到国赛的消息(虽然可能省选后我就AFO了)。

吃饭吃到6:35,然后看三个晚上6:40有课的学长骑共享单车回去,就感觉很惨。

DAY1

上午开营仪式,通知书上写了两个小时,结果四十分钟就结束了?

然后就很尴尬,然而此时遇到了巨神kai586123,于是与大神在咖啡厅颓废了一个上午。

中午在食堂突然发现北大送了150块钱的饭卡,然而只吃五顿饭。

把一个餐盘点满,只花了不到20,所以感觉颓不完这张饭卡,就很难受。

下午考试之前看了看虚树板子,看了眼burnside引理(结果都没考)。

十二点半已经入场,发现电脑并不是linux系统,只是有一个noilinux虚拟机。

打开虚拟机,敲好vimrc,然后发现这个玩意实在是卡的要命,码个代码都有延迟,很不顺畅,所以就自闭去用devc++了。

开考发现三个998244353,然后就自闭了。

T1这个数据范围,一看就很不好做,所以直接跳了。

T2这个玩意,一看就很不好打暴力,所以直接跳了。

T3这个玩意,一看就可以打,所以赶紧码啊。

因为保证一个变量的随机,打个表发现这个随机就会导致枚举莫比乌斯函数值不为0的约数的复杂度很低。

所以似乎是个显然的容斥,约数容斥,然后整个反演啥的就完事了?

码完发现伪的很厉害,所以自闭了。

疯狂的改,然后终于过了第一个包。

搞个分块,过掉了第三个包。

换一种分块方式,懒得算复杂度,然而感觉前四个包都能过,交上去发现只能过第一个和第二个包。

自闭了总共三个小时,感觉不是很有戏,于是合起来两个算法,交了个43分上去。

回去看T1,发现这个玩意的21分暴力是NOIP模拟赛的原题,直接大力dp就完事了。

回去看T2,发现这个玩意就不是很可做。

打打暴力和特殊性质,17分就到手了。

然后考虑将原题中的期望转化为总和除以方案数。

方案数并不难算,组合数暴力阶乘起来就好了。

还有二十分钟结束考试,突然想到只要分别考虑每个最终选到的集合的贡献,排完序后枚举左右端点,枚举中间选了多少个数、

然后分别考虑中间的数和两边的数分到哪些集合就好了。然而暴力做的复杂度是$n^4$的,交上去过掉了n=100.

然后可以发现这个玩意是卷积式,还剩十分钟赶紧码个ntt,因为没翻转调了两分钟。

$n^2$预处理之后直接卷积,暴力加就完事了,于是还剩2分钟的时候终于拿到了50。

然后发现有个13分的l=r部分分,瓶颈在于预处理。然后发现这个玩意好像也能卷积,所以接着搞就完了?

然而没有时间了,所以有13分没来得及打,有点自闭。

考完发现似乎题很难,21+50+43=114这个分数并不是很低。

吃过饭想与kx大神骑共享单车回宾馆,然而我们两个的手机一扫码集体暴毙。

于是自闭了只好打车回宾馆。

晚上疯狂背自我介绍稿子,然而感觉一直在颓废,并没有背进去。

DAY2

上午8点赶到北大,准备自我介绍。

第一个面试老师看起来很强,似乎并不是计算机专业的。

进行了一些自我介绍后,被教育了一通,表示我的自我介绍太弱智了,

没有说自己的兴趣爱好也没有表达自己的优势,并没有直击关键点,说的都是垃圾话。

给我整的很懵,然后问了问父母的工作,问了问兴趣爱好,胡诌一通上去就结束了。

然后听他们讨论,发现这个面试官好像教育了好多这场的学生。

第二个面试官看起来挺和蔼的,说话又好听,超喜欢在这里的。

然而问的问题有些难,突然问我对数学和物理的认识,又问我数学物理与计算机在思维方式上的区别。

这个问题就很恶心,于是胡诌一通上去。

虽然并不知道自己说了些什么垃圾话,恍惚之中我似乎说数学物理都是古老的学科,而计算机富有生命力。

然后就又被教育了,感觉这个老师好像是数学或者物理的,就自闭了,我只好随着他教育我不断点头表示赞同,同时缓解自己的尴尬。

第三个面试官面试我时已经是最后一场,看起来很放松。

因为吸取了第一个面试官的教训,我在自我介绍中加入了一些兴趣爱好(因为并没有,只好说兴趣爱好是读书)。

然后因为说了一些我读过一些历史书的垃圾话,突然被面试老师找到了他的切入点。

于是打断问我喜欢哪一段历史,并让我讲一段历史,这咋可能,就很尴尬。

我只好尴尬地说自己喜欢民国时期的历史。

然后突然陷入平静,似乎我应该讲一段历史,然而并不知道说一些什么。

然后就被提问了:1927-1937的黄金十年为啥突然结束了?

exm?我又不是学历史的。

然而1937这个时间点让我想到了抗日战争,所以说了。

然后又被提问全面爆发之前为啥就能发展?

exm?这我咋知道,就很尴尬。

然后又被提问为啥1936年突然联共抗日了?

exm?扯了扯张学良的那些事,说了一些垃圾话。

然后又被提问认为老蒋攘外必先安内的政策是否是正确的?

exm?然后我就回答这个玩意站在先代人的立场上我认为是错误的,但是如果站在当代人的角度我可能会有不同的想法。

然后又被提问热力学三大定律是啥玩意?

exm?于是扯了一些熵增啥玩意的。然后被裱这个玩意文化课不是学了吗。

然后突然就结束了,感觉要完戏。

所以面试就结束了,下午考试之前又复习了$pam$,虚树和$burnside$引理(然后又都没考)。

入场发现linux虚拟机照样难用,然后发现这个devc++改个模板还挺好用的。

1点开题。

这个T1看起来就很能二分,应该能做。

这个T2看起来就很数据结构,感觉也能做。

这个T3不是最小割树模板吗,虽然只有42分。

所以先码了T3的部分分,猜了几个结论都伪了,只好回去搞T1 T2。

回去看T1,先搞了个二分之后显然的贪心,然后发现这个玩意好像有点像栈,或许可以用线段树维护分治的操作。

看部分分,似乎是显然的括号匹配,只不过一个只能作左括号,一个可以作左括号和右括号。

然后发现这个玩意也是NOIP模拟赛原题啊,交上去就AC了。

看T2,发现这个玩意的暴力直接用ST表查区间最值,递归左右就好了。

记忆化一下就可以过65分了。

然后发现一个元素能造成的贡献即乘或者除决定于单调栈中元素个数。

然后发现这个玩意并不是很能维护。

打了一个线段树维护单调栈,然后交上去发现伪了。

突然想到离线询问,然后外面维护一个单调栈,就变成直接线段树维护变成逆元标记的弱智题了,交了一两次就A掉了。

然后发现我旁边的仁兄好像也打到了242分,已经自闭了很久了。

然后就感觉这场考的也不算差,想了很久T3,并没有结果。

考试结束,于是回到了宾馆,开始了晚上的颓废,并写下了这篇游记。

DAY3

上午颓废,中午来到PKU看大神们拿约。

吃饭时遇到 wzz 学长,问我考得咋样。

我只说考的还行,然后突然被奶了一口,说他当年也只觉得考得还可以。

下午来到结营仪式地点,不久开始讲题。

D1T1完全不会正解,D1T2的式子化的和正解一样,但是并没有看出来这个玩意还能再次卷积。

D1T3显然是莫比乌斯反演,看着ppt上一坨一坨手写的式子自闭了。

D2T1全场切,现在想来似乎$O(n)$的离线做法比线段树做法还要简单。

D2T2出题人的思路挺奇怪的,并没有听懂。

D2T3大概听懂了思路,因为存在流量为$10^9$的环,这个环上一定要割两条边。

于是将整个图划分为两个弧,只要割掉连接两个弧的边就好了。

这个割可以去更新一下答案,大概优化一下就能做到$O(n^2)$。

所以开始发奖。

三等奖念完,感觉二等奖稳了。

二等奖念完,感觉没有奖稳了。

然而最终上去领了一个安慰奖这样子。

原文地址:https://www.cnblogs.com/skyh/p/12081283.html