PKUSC 2021 游记

UPD：翻到一篇题解博客

Day 1

早晨起来肚子巨痛无比，没吃早饭又拉不出来。早饭恰了点粥，教练整了点奇奇怪怪的药，稍微好转了一点点。

9 点去报到，拿了个牌和日程表，中途遇见GVZ和YYH，都是老朋友了，然而我肚子实在不太舒服，没法谈笑风生。

让人意外的是有试机和试机的题，上去机房发现是 Win10 系统（比赛时用的电脑是 Win7），没有虚拟机但是有 Gvim。这也 OK。

试机题的 T1 挺能做，T2 由于肚子不舒服，还没看就回酒店了。

回酒店又开始坐马桶，在一顿哼哼啊啊的挣扎（？）之后我的的腹痛奇迹般地好了。

中午去吃了一家湘菜馆，味道很不错。不过由于肠胃原因不敢多吃。

然后就到了比赛时间。这回是 IOI 赛制。

开场走一个 T1，是个傻逼题，写了 1h。然后花 1h 写了 T2 46 分（前 2 个 Subtask）。

T3 是祖传的扑克牌题，写了 2 个小时各种调试写了第一个 38 分的 Subtask。第二个 Subtask 写完的时候只有 5 分钟了，交上去还 T 了，没时间卡常，丢了 41 分，有点悲。

旁边那位老哥写了个 100+46+79，是我的目标。我只写了 100+46+38。心有余而力不足。

晚上去吃了一家据说很有名的面馆，味道很不错。

差不多就这样，早点睡，准备明天翻车。

附送 Day1 题面：

Sum Transformation

给出$n\times n$的矩阵$A$和$m, P$，定义$f(A)$表示对矩阵的变换，将$A_{ij}$变成$\sum_x A_{xj} + \sum_y A_{iy}\pmod P$。求$f^m(A)$。

$n\le 1000, m, P\le 10^9$。

B （忘记标题了）

给一个序列$a_1, \ldots, a_n$和$m$次操作：

• 1 l r：对$l\le i < r$令$a_i \gets \max(a_i, a_{i + 1})$。
• 2 l r：计算$a[l, r]$的前缀唯一最大值的和。前缀唯一最大值指满足$\forall l\le j < i, \; a_j < a_i$的$a_i$（$a_l$也算，$l\le i\le r$）。

$n, m\le 3\times 10^5, a_i\le 10^9$。

德州扑克

真的有人想要看这题的题面吗（憨笑色）

Day 2

上午安排参观了 NOI 决赛场地。

安排参观寝室，结果进的是女寝……这就是余姚吗。

然后下午就打 Day 2。

T1 是个简单换根题，T2 我并不会初步转化然而还是骗了 35 分，T3 骗了 5 分，大众分可能是 155，我只有 140。

感觉进不了面试了，悲。

老规矩，放一个题面。

A

给一棵$n$个点带标号的树，要删除一条边再加入一条边使得仍是树，问所有的改动方案形成的树上的所有路径的长度和，即$\sum_{i} \sum_{j} \text{dist}(i, j)$。

删的边不同或加的边不同就算不同的改动方案。

$n\le 3\times 10^5$。

B

有$n$个菜，第$i$道菜价格$a_i$。你要依次买菜。

对于一道菜，你每花费$c$元 RMB 可获得一张价值$1$元的代金券。代金券可以在之后的买菜过程中使用。

有$m$次单点修改。对于每次修改询问改后你要花费多少钱才能买下所有菜。

$n\le 3\times 10^5, c, a_i\le 10^{12}$。

C

有$n$个$[0, m]$内随机的实数变量$x_1, \ldots, x_n$，问满足

$$x_i + k \le x_{i + 2} \;\;\forall i$$

的概率，输出模$p$意义下的答案。

$n\le 50, m, k\le 150$，$p$是质数。

Day 3

进面试啦，狂喜。

面试分两场，每场$5$分钟，实际上就是和两个教授闲聊五分钟。旨在判断你是个正常人。

下午就颁奖了。拿了个优异。

当晚就飞回成都了。