PKUWC 2020

Posted by Ghastlcon on December 23, 2019
CC 采用 $\text{CC BY-NC-SA 4.0}$ 许可,转载请注明:“转自 PKUWC 2020

$\text{Day }\mathrm{-1}$

坐了整天的高铁,头还是很晕的。

路上水了很久的群,不由得感叹这几年来物是人非了。想起以前养老院,还是个绘板群和则群啊。那时候群里满天 $\text{IP}$ 来着。

北京咋这么冷啊,感觉头都要掉了。

话说现在还是 $2019$ 年,那是不是应该还叫 $\text{PKUWC 2019}$ 啊。

住的地方有点神奇,甚至没有门面,是个类似公寓的地方。开门还爬出几只蟑螂……

$\text{Day 0}$

感觉要到 $\text{PKU}$ 的话要走东南门,那还是挺远的……为什么要住在这种地方啊。

$1.8\texttt{km}$

走了半天终于到了,结果进的是东门,转了会后发现自己毫无方向感,但是找到了理科楼 $1$ 。

$\text{zjt}$ 咋说他出来了,我没看到。转了会忽然发现远处有个人身上金光闪闪。凑过去问,果不其然又阿克提前离场了。

然后就是瞎逼吹,有啥说啥。他说要把饭卡花完,所以要高消费?跑到了农园里,搞了两杯神必烧仙草。

从东方到 $\text{OI}$,反正扯了很多乱七八糟的东西。期间还观看了天地人间完全放电的神奇纹理。

想去西餐厅高消费然后发现并不收卡。那就没啥办法了,只能常规饭堂消费了。

感觉菜品也是挺神必的,全是凉的。吃饭过程中交谈了对 $\text{esu}$ 与囧的看法,甚至成功达成了共识,很开心(

想起文文新闻曾经直接提醒过我,你不去做这些事就没有人做这些事了。

最后没啥办法,只能又买了大量饮料,看了会感觉没啥好的就啥都没拿(

出来的时候在地方看到了“落户天津”把我笑傻了,直接拍照发给了 $\text{Ressed}$ 。

高考多考 $100$ 分

其他集训队老哥有点惨,土豆 $\text{OJ}$ 又挂了,延时了好久才出来。

报到的时候 $\text{zjt}$ 跑了并且留下了句“明年见”,现在想来好像挺有道理的。

草我没带获奖证明材料的复印件啊,这是什么鬼啊还得单独去跑。

话说签到表上有列“能否使用 $\text{NOI Linux}$”,我想知道要是填了否会不会安排 $\text{Windows}$?


回来搞好之后就跑去了 $\text{THU}$ 转了会,顺便找了个打印店。

这个打印店藏得好深啊,完全找不到啊。

有点无聊,写了个题才去吃饭。

羊杂碎,不是很能接受


晚上没啥好说的,用流量打则。

感觉跟 $\text{Rose_Max}$ 这种水平相近的人交流还是很棒的。

$\text{Day 1}$

挺糟糕的。

上午开幕式很简单就结束了,甚至只用了 $40$ 分钟。结束后没地方可去于是跑回来睡觉。

下午机试机房位置有点偏僻,转了很久才到。似乎全部都是 $\text{Windows}$,然而并没有管理员权限。

话说我的密码里有个子串是 $\text{JSB}$(

$\text{P1}$ 排列

给 $1$ 到 $n$ 的排列 $p$,将所有字典序小于等于 $p$ 的排列按照字典序从小到大连接起来记为 $q$,例如 $p=\langle3,\,1,\,2\rangle$,那么 $q=\langle1,\,2,\,3,\,1,\,3,\,2,\,2,\,1,\,3,\,2,\,3,\,1,\,3,\,1,\,2\rangle$,求 $q$ 有多少个本质不同的子序列。$1\leq n\leq 50$ 。

发现不会,只会找到前个颜色的暴力动态规划。于是打完 $21\%$ 就不会了,剩下的时间也没搞出啥。

$\text{P2}$ 火山哥的集合

有 $n$ 个结点,每个结点有个权值。每次随机选两个不同的连通块合并,直到剩下 $k$ 个连通块为止。贡献为 $\sum_S(\max S-\min S)^2$,其中 $S$ 表示每个连通块。对于 $k=l,\,l+1,\,\cdots,\,r$ 都回答。$1\leq n\leq 2\cdot10^5$ 。

其实可能这个题比较可做,但是并没有想过。打了阶乘暴力和 $k=0/n-1$ 就跑路了。

$\text{P3}$ 数论结构

有 $n$ 行 $m$ 列的矩阵,初始全为 $0$ 。先有 $x$ 个修改 $\langle s,\,l,\,r,\,v\rangle$ 表示把所有格子 $(a,\,b)$ 满足 $a\perp s,\,l\leq b\leq r$ 都加上 $v$ 。再有 $y$ 个询问 $\langle s,\,l,\,r\rangle$ 表示询问所有格子 $(a,\,b)$ 的和。$1\leq n,\,m,\,y\leq5\cdot10^4,\;1\leq x\leq10^5$,答案模 $2^{32}$ 。保证 $\boldsymbol s$ 是随机的。

有个分档是 $m=1$,那只要快速找出所有和 $s$ 互质的数就行了。感觉只会分解质因数然后暴力组合。写完发现跑了 $4.5\texttt s$,死活卡不进去,人都没了。


差不多是打完暴力就跑了,获得了 $21+18+19=58$ 分的好成绩,我觉得打铁稳了。

感觉……挺爆炸的?明天好像要面试于是睡得比较早。

晚饭没吃饱,找了个神秘羊杂碎店,发现根本不能接受这种独特的气味。

睡前好像还玩了挺久的则来着。

$\text{Day 2}$

感觉前几天的早餐太神秘了,令我感到生理不适。

于是今天就跑到校内了,感谢 $\text{KsCla}$ 。

$\text{P1}$ 火山哥与打铁传说

你有 $n$ 个 $1/1$ 的鱼人,其中部分鱼人带有剧毒。你必须按顺序使用这些鱼人攻击,所以实际上给出的是个 $0/1$ 序列。有 $q$ 个询问,每次给出 $x$ 和 $k$ 表示对方有 $x$ 个 $10^9/10^9$ 的鱼人,你只能使用你的前 $k$ 个鱼人。你需要求出最大的 $y$,满足即使对方多放下 $y$ 个 $10^9/10^9$ 且带有圣盾的鱼人,你也能将其全部消灭。$1\leq n,\,q\leq 4\cdot10^5$ 。

感觉这个绝对是签到题,这种题搞不出来就凉了啊。想了会感觉把它变成括号序列,然后把 $-1$ 出现的地方后缀都 $+2$,实际上就是找 $-1,\,-3,\,-5\,\cdots$ 的长度。因为相邻的差值的绝对值最大为 $2$,因此找最小值就行了。

交上去 $1\text A$ 了,有点开心。

$\text{P2}$ 火山哥与分式

给个分数,从上往下写出,共有 $n+1$ 个数和 $n$ 条横线。有 $q$ 个询问,每次询问区间 $[l,\,r]$ 的求值结果。$1\leq n,\,q\leq2\cdot10^5$ 。

先搞了个暴力,从小到大考虑分数线长度然后用个并查集缩起来。

过了会感觉从小到大没前途,于是换了过来从大到小,然后考虑每个数要么在分子要么在分母。实际上决定在上还是在下的因素就是单调栈长度的奇偶性。那么暴力单调栈长度,然后变成平面覆盖单点查询可以通过数据随机。

写完之后感觉不会了,去把 $\text{P3}$ 暴力写了。回来看发现需要支持的是单调栈内的位置全局加,那我搞 $3$ 个线段树,然后整体打标记大力讨论好像就搞完了。

然后直接交,爆 $0$ 了。

别吧,这种东西好难调的。划了会代码发现我线段树乘完之后没模,并且大概有 $4$ 个地方……模完之后交上去过了,有点开心。这时刚好 $17:00$ 。

$\text{P3}$ 最小割

给个 $n$ 个点 $m$ 条边的带权无向图,边权不超过 $10^4$ 。额外连接 $n$ 条边,第 $i$ 条边为 $i\overset{10^9}\leftrightarrow(i\bmod n+1)$ 。定义 $\mathrm F(s,\,t)$ 为点 $s$ 到点 $t$ 的最小割,求 $\sum_{i=1}^n\sum_{j=1}^{i-1}\mathrm F(i,\,j)$ 。$1\leq n\leq 7000,\;1\leq m\leq 3\cdot10^5$ 。

写完 $21\%$ 暴力就跑去搞 $\text{P2}$ 了。

搞完之后想了 $40$ 分钟无果,感觉不能停留在暴力分。于是用 $\text{Gomory}$ 树搞了个优秀点的暴力,交上去获得了比暴力多 $0$ 分的好成绩。

别吧,我 $\mathrm O(n^3)$ 链最小值求答案都能跑不过去?赶紧把它换成倍增求,然后发现死活调不过样例了,心态没了。现在想来,是因为倍增的最后少跳了 $1$ 步(

等等这档分 $n=300$ 啊, $n^3$ 是 $10^7$ 级别的啊,瓶颈根本不在这里好吗!吓得我赶紧把倍增删了,然后手动加了个 $\texttt{pragma optimize}$,还是暴力分。

这个时候已经 $17:58$ 了。看来这就是命运的安排吗拿不到这档了。划了会代码,发现我 $\text{Dinic}$ 的分层 $\text{BFS}$ 用的 $\texttt{std::queue}$,这个东西好像是 $\texttt{std::deque}$ 实现的?

把这个换掉吧,虽然感觉也没啥用?换完发现变量重名了,急急忙忙随便改了个名字就交了。

提交时间是 $17:59:30$ 。刷着刷着忽然发现有两个蓝色,草真的过了 $\text{subtask 2}$!

感觉整个人都高潮了,到外面去想拿个手机回来拍照发现已经被关掉了。

好像人均 $\text{AK}$ 了,甚至有人说 $300$ 的比 $200+$ 的人数要多,那我是不是又凉了。


因为没活干所以跑去高消费了,顺便在 $\text{KsCla}$ 面前把某些东西瞎逼批判了会。

奇奇怪怪的心路历程就不写出来了吧。

晚上本来想晚点睡的,结果感觉老了于是也没多晚就睡了。

$\text{Day 3}$

起床跑去交复印件,然后又跑回来。

薯片真好吃。话说我的输入法居然已经可以联想这句话了。

然后刷了几个小时的知乎,然后又跑过去吃饭。果然饭卡最后是用不完的,是不是又得买大量饮料了啊。