Day -7 ~ -1

来自广东若干所学校的一些参加 SC 的巨佬来我们学校集训，请到了 zkw、pb、jly 等巨佬给我们安排了若干场杂题选讲和模拟赛。

Day 1

上午

余姚宾馆。

吃早饭的时候发现绍一中跟我们又双叒叕跟我们住一家宾馆了，同时还有好几所其他的学校也在，因为大多没穿校服就没认出来了。

早上报到，排了半天队轮到我们的时候我们突然发现教练并没有给我们带盖章的申请表 /jk，最后把教练拉过来备注一下“没有材料”才拿到牌子。

试了一下机器，i3 十代 + NVMe + 8G RAM + 我们机房同款键盘 + 大显示屏 + 正版 Win10！配置好到爆炸。是 IOI 赛制，在 openjudge 上进行。试机题一道都不会做。

中午在余姚中学对面的麦当劳吃，遇到了一大堆同样带着牌子的巨佬，感觉还没上场就已经爆蛋了（

下午

然后是下午的比赛。

开始后直接看 T1，立马想到了维护每行每列分别的和。记 $r_i = \sum_{j=1}^{n} a_{i,~j},~c_j = \sum_{i=1}^{n} a_{i,~j}$。显然我们只需要知道 $k-1$ 次变换后的所有 $r_i$ 和 $c_i$ 即可直接推出结果。稍微推一下式子可以发现 $r_i=r_i' \times n + sum,~c_i=c_i' \times n + sum,~sum=sum' \times 2 \times n$ 其中 $sum = \sum_{i=1}^{n} \sum_{j=1}^{n} a_{i,~j}$，$r_i',~c_i',~sum'$ 分别表示对应值在变换前的值。显然每个 $r_i$ 和 $c_i$ 仅与 $sum$ 相关，分别用 $2 \times 2$ 矩阵依次算出每一个 $r_i$ 和 $c_i$ 在 $k-1$ 次变换后的结果就可以了。复杂度 $O(8logk+16n+n^2)$。

大概在比赛开始 25min 后就切掉了 T1，感觉状态还算良好。

然后看 T2，大概有一个奇特的想法：将原序列拆分为若干单调上升子序列的集合，每个独立子序列以链表形式存储，每次 $1$ 操作删除区间内每个子序列的最小值（需特判区间边界位置情况）。原本还需要将子序列的最大值拷贝一份但是由于不存在贡献且影响后续操作，通过记录 $pos_i$ 表示每个值对应的真实位置。只需要把整个区间的 $pos_i$ 区间加即可。同时考虑动态维护 dp 数组 $f_i$，$f_i$ 表示 $i \sim n$ 区间的最终答案。每次修改删除一个点时只需要将该点至其左侧最左边的比他小的位置之间的所有 $f_i$ 全都减去该点的权值即可（因为显然这些点最终的答案序列中一定都会存在这个被删除的点）。至于 $2$ 操作询问，找到给出区间对应的真实区间（即 $[pos_l,~pos_r]$）内的最大值的位置 $p$，输出 $f_{pos_l}-f_p+a_p$ 即可。由于一些高复杂度操作都能够被均摊，时间复杂度大约是 $O(qlogn)$，多处用到了线段树、树状数组等数据结构，代码相当难写。

显然这个做法单讲出来就能让人听懵，我花了将近一个钟头的时间让他过了样例，但在接下来地一个半小时内它一直保持过样例但是拿 $0$ 分的状态。此时只剩下两个小时了，我决定弃掉这道题并且去肝 T3。

打开 T3 一看，是工程题。我想着工程题我在行，于是我打算接下来的时间从 T3 的第一个 Subtask 冲入，如果还有时间的话再尝试写一下后面几个 Subtask。毕竟 T3 的 Subtask 分值相对于 T2 来说高了不少，我认为冲 T3 相对来说更加划算。

实现的时候我同时尽可能降低一些基本操作的复杂度（例如将牌组合），等我写完并测试完判牌类型、分数等模拟内容时大约已经只剩一个小时了。看到后面的期望部分，我意识到它可能没有我想的那么简单，于是先去 T2 写了 7pts 的暴力，写完又重新看了看 T2 的几档暴力分，花了一些时间想了想，觉得都不大有时间去写了，于是又回到了 T3，此时只剩下半小时了。

但是由于时间不多这个时候可能是有点慌了，期望式子写错好几次，到最后竟然完全推不出来了，到考试结束自然也没有在 T3 上拿到一点分数……（现在看来当时真脑瘫这式子都推不出来）

$100+7+0=107$。我菜死了，不知道比大众分低了多少。

Interesting Things

顺便再讲些奇妙的事情。

PKUSC 的考场中竟然有同桌一说，跟隔壁的考生是在一张长桌上的，而且中间没有隔板，屏幕又很大……只要稍稍偏转头部简直就能把对方的代码看的一清二楚……

我是 $1$ 号位，从开场开始我就注意到 $2$ 号位的老哥在频繁往我的屏幕上看。我在纸上大概推了五分钟就推出来了，然后开始写代码。

由于我注意到他在频繁转头，所以我特别注意了一下他手上的动作。

我写了一个矩阵类，我看了他一眼，他也写了一个矩阵类。
我写了一个矩阵快速幂，我看了他一眼，他也写了一个矩阵快速幂。
我写了输入和预处理 $r_i,~c_i,~sum$ 的部分，我看了他一眼，他也写了输入和预处理 $r_i,~c_i$ 的部分（看起来没处理 $sum$）。

我觉得应该没有那么巧的事情，于是我快速把我的矩阵写了下来并且在两三分钟内加快手速快速写完了剩余部分并且提交。提交的时候就看到他停下了手上的动作看着我不断刷新评测界面……然后我 A 掉了，快速转到了 T2，关掉了 T1 的代码。然后我就看到他的代码就不动了，他在纸上反复推矩阵……

后来也不知道他 A 了没有，后来冲 T2 的时候一直很急也就没有关注他了。（反正我也没拿分抄了也没用）

后来听说好像是 tony102 的学弟。

Day 2

上午

先是拍了合照。

然后去余姚中学梦鳞分校看 NOI2021 赛场。然后才发现在现场的就我不参加 NOI2021。听校长讲寝室、食堂咋的咋的好，然后到这些地方走了一遍。考场几百台机器从上到下全是全新的老实说真的有惊到我。但是老实说看起来寝室、食堂啥的比海亮差挺多。我爱海亮。

中午听说学校食堂提供免费午餐。去食堂的路上我们几个就调侃说“世上没有免费的午餐”，然后午餐还真是有点一言难尽……稍微吃了几口就倒掉了，我们几个人又跑到了麦当劳去好好吃了一顿……

下午

然后是下午的考试。

坐在第二排靠中间位置，签名的时候惊奇地发现我左边坐着的就是 zqy 巨佬（啊他真是太帅了）。

开场依旧先看 T1，我稍微想了想之后想到将每条边分开来算贡献，完善一下想法之后发现已经过去半个小时了，然后看到 zqy 已经开始敲代码了，我感觉我太慢了然后也开始对着我的式子开始写代码。之后又发现我的式子因为最开始写得丑有好多处纰漏，然后发现 zqy 已经切掉了，然后开始反反复复修改式子，反反复复部分重构代码，终于在开始两个小时之后切掉了，比 zqy 整整慢了一个钟头。

zqy 真的太强了啊！

然后我打开 T2，然后想到了一个神奇的贪心：显然对于 $a_i \mod c$ 的部分能用券就用券，其他部分先不用券，处理完全部菜品之后再开始尝试撤销操作，撤销时直接分类处理整除 $c+1$ 的部分（撤销 $1$ 张券的生成机会，再用 $c$ 张券将对应位置填满）和余数的部分。显然这个贪心一眼就是错的，这并没有考虑到自己在尝试撤销一张券的时候到底是不是真的有手上那么多券了。但是那个时候头一晕没有发现这个显然的问题，看到样例过了就直接提交。是 $O(nq)$，如果写对的话能拿到好几个 Subtask 的分。

然后我遇到了超级无敌神奇的事情。我其实已经同样准备好 WA 飞的准备了，结果过且仅过了 Subtask 3。

诶但是 Subtask 1、2、3、4 是数据范围呈梯度的几个情况，偏偏 Subtask 1、2、4 全部 WA 飞而 Subtask 3 A 了？

稍后我很快发现这个贪心做法显然的错误，然后开始暗自感叹造数据者提供的福利。

之后我开始尝试改进我的贪心，加入更靠谱的可撤销操作，但是写到最后一个半小时的时候还是没有什么进展，然后开始考虑去看 T3。

打开 T3，一看是一个神奇概率题，原以为花点时间手推一下至少能过几个 Subtask 的（毕竟前几个 Subtask 的数据范围实在是太小了），接着我花了半个小时的时间开始尝试攻破 $n=3$ 的情况。然而由于我数学实在太烂并没有推出来……

然后回到 T2，用暴力 DP 写了前两个 Subtask，配合特判加之前的玄学错误贪心拿到了 23pts。

再看 T3，随便交了一个输出 $1$ 的情况拿了 $5$ 分。这个时候只剩下半个小时了，由于我意识到几乎不可能调出来 T2 了，于是一直都在尝试推 T3，然而并没有推出来。

$100+23+5=128$。然后还是比大众分低好多，我太菜了。

Day 3

上午

“我这烂分数怎么可能能进面试啊。”

早上在酒店里还跟 jdsb 打赌说什么进面试 nz 啥的事情。黄教练在我们出门前就打 QQ 电话跟我们说如果没有参加面试就做前几天的四校联考题，吴教练还提前跟我们说好了如果到那边面试名单上没有名字就直接打车回酒店的……我在学校门口从出租车上下来的时候我都准备好再回到出租车上来了。

然后看了眼名单，发现我竟然进面试了！PKU 真照顾我这初三弱鸡！

两场面试，分别在 8:35 和 9:55，算是最早的一批吧，加上最开始我还以为会问啥学术相关的问题的，然后就挺紧张的，快面试时就一直在回忆各种算法。

第一次面试，面试官就说了“自我介绍一下”，“对北京大学的看法”，“文化课怎么样”，“在学校的文化课班里怎么样”，“学校里运动不运动”，“家里有没有弟弟妹妹”，“对弟弟妹妹有啥看法”，“有啥兴趣爱好”，“说一下让你记忆最深刻的事情”。大部分问题我都轻松回答了，唯独最后一个问题，我寻思着我平日每天泡在机房里哪里有啥记忆深刻的事情……最后支支吾吾说了些模糊的答案。

呼还好没问啥学术问题，感觉跟闲聊没差多少。是 5min 面试时长，然后一个北大的老师坐在你对面面试的方式。

然后是第二次面试，似乎前面的人的面试时间都放短了，我 9:50 就被叫到了。这次面试官坐得离我更近，伸手就能碰到对方的那种距离。有了第一次的经验，我也更加自然些了。面试官大概就问我“哪个学校的”，“是哪个教练在教”，“你在文化课班里怎么样”，“做不做体育运动”几个话题。感觉还没有聊多少话题就结束了，出门一看才面试了三分钟……

总的来说感觉不错，比我想象中的简单很多。

Interesting Things

听 jdsb 跟我说他第一次面试的部分阳间对话，根据他的描述大概是这样的：

• 面试官：“海亮高级中学在哪里啊？”
• jdsb：“在诸暨。”
• 面试官：“诸暨在哪里啊？”
• jdsb：“在绍兴。”
• 面试官：“离余姚这边有多远啊？”
• jdsb：“大概两小时车程。”
• 面试官：“那离杭州有多远啊？”
• jdsb：“也是两小时车程吧。”
• 面试官：“哦，那诸暨在绍兴的哪边啊？”
• jdsb：“下面。” （指的是南边）
• 面试官：“下面是哪个方向啊？”
• jdsb：“西边。” （据 jdsb 说被问懵了，那个时候想说南的说）

---

然后听 Lenstar 描述他听到的阳间问题：

语段 1：

• 面试官：“你也是海亮的，之前我也有看到一个海亮的学生……（翻看名单表）哦是叫***（jdsb 真名）的，你认识么？”
• Lenstar：“认识。”
• 面试官：“那你比他强么？”
• Lenstar：“……（懵逼了一会）现在我高一他初三，目前我还是比他强一点的。”

语段 2：

• 面试官：“你为什么叫***（Lenstar 真名）”
• Lenstar：“……（一脸懵逼然后瞎编了一段）”

下午

午休了一下然后就到闭幕式去了。

闭幕式上 zyy 巨佬讲解了一下这两天的六道题。老实说感觉讲的速度比前几天 jly、zkw 几个巨佬的杂题选讲速度慢多了。至少听完后我的脑子告诉我我大概全会了，虽然手不一定觉得。

然后是发奖。这个弱鸡只拿了优秀，只能看着同校的优异巨佬在那边签合同……

总结

虽然这次 PKUSC 考的并不是非常好，但是至少我认为我拿到了我应该拿到的分数，并没有冤枉地失掉不该失的分数，并且总体来说发挥还算良好。

接下来我需要继续努力，提升自己的水平，争取在明年拿到更好的成绩。