北大集训 2020 游记

Day-1

到宾馆入住,和 xzz 住一个房间,打了打数据结构。

Day0

报到日,室友按照 NOI 排名换掉了。

试机题是一个做过的题和一个用交互实现的通信题,写了个 6 分试了试交互题就跑路了。

晚上发现室友 21:00 睡觉,有点毒瘤。

Day1

开场看了看三个题,猜想 T1 的结论和二进制版本是一样的,剩下的就是个 k 进制线性基。T2 是个看上去比较 trivial 的数据结构,搞几个二分就完事了。T3 是交互题,看完题就跑了。

大概 9:00 写完了 T2,对着样例调了几分钟,一遍 AC。

然后开始写 T1,写了一个小时,瞎编了个 k 进制线性基,交上去爆零了。写了个暴力对拍,拍出一些错误,改完得到了 50 分的好成绩。又拍了很久拍出一个毒瘤错误,想了想发现不会修补,就溜了。

这时候大概还剩 1h,枚举了一些树上交互的套路,结果都做不了 T3(没想到剥叶子)。还剩 10min 的时候试图 rush 一个 T3 的 10 分,最后 1min rush 完,WA 了。

出来以为自己凉了,最后居然还有 rk30 左右,意识到并不是全场的水平都很恐怖。

下午去听了一波讲题,然而什么都没有听懂。自己看了看 T3 题解勉强会了 subtask1。

Day2

进场发现右边是 zjc,瑟瑟发抖。

开场几分钟 zjc 秒了 T1,我还没有推出答案式子,有点着急。8:20 左右猜了个式子写了个暴力,交上去爆零了。然后冷静了一下决定打表,打了下表得到了正确的式子,准备用不知道能不能过的莫队维护,写到一半才意识到是个可持久化线段树,大概 8:40 过了。

然后看 T3,一开始想分析图的结构,啥都分析不出来。突然想到用度数序列求强连通分量个数的方法,剩下的就是个简单差分,大概 9:40 过了。

还有 2.5h,我稳了。

T2 先花了很久推出了每一种 x 概率相同时的做法。又想到了转坐标系,以为转完以后和原问题没有什么本质区别(flag),就把坐标系转回来了。自闭到 11:50 准备弃疗写个 5 分,没想到用个 double 随机模拟,仍然在推式子,最后自然没推出来。

最后因为 T3 并没有全场过,T2 超过 5 分的人也不多,总排名还是上升到了 rk21。

下午问鸽子要到了 T2 的题解,看见”2n 个随机变量“就意识到做法了,于是鸽掉了讲题。认识到了自己是个 sb。

Day3

T1 以为是个分析性质的 DP 题,试了几种 DP 排列的方法都做不了,不过“每次在当前排列最后加入一个数,并将前面大于自己的数 +1”这种方法大概能做 50 分。

然后猜了个 T2 结论得到了 60 分。回去写 T1 的 50 分,先写了个状压,用状压打了个表,发现 subtask2 的答案是有规律的,这样就不用写 DP 了。

回去干 T2,意识到剩下的部分大概是个分块。突然想到 kdtree,觉得 kdtree 会比分块好写,并且复杂度也很优秀,怎么看都吊打分块(flag)。然后就调到了 11:00,调完才发现常数巨大根本没法跑,果断扔了这题。

又想了想 T1,以为正解也是和 subtask2 一样有规律的东西,可能是个一一对应。然而还是没有想出什么来。

最后补了 T3 的 30 分暴力,就下考了。

出来 xzz 和 Itst 连切两题,把我吓傻了。问了问 T1 是个行列式,顿时意识到了这题的难度(最后确实过了一大片)。T2 写个带 log 的分块能过,效率把不带 log 的 kdtree 吊着打。

没想到只掉了 3 名,总排名 rk24。

因为 T1 是降智题点到就会了,T3 觉得场上真出了也只有 zx 这种神仙能写,继续鸽掉了讲题。

Day4

进场发现是三个数学题。

先写了 T2 的矩阵树,再用矩阵树推了 subtask3,得到了 60 分。剩下一个循环矩阵行列式,但我不会求。

然后直接给 T1 套了个容斥,用总方案减去不包含指定边的方案,后果就是完全去不掉 q 组询问的复杂度。

于是给 T1 堆部分分,10:40 左右堆完了 75 分。

11:00 才意识到不用容斥就做完了,写了写,拿 75 分拍了拍,11:20 左右过了。

然后花了一些时间构造出了 T3 的 subtask1 和 subtask2。subtask3 没什么直接构造的想法,就写了个随机,随出了一组 20 个点, 45 条边的方案,拼一拼就完事了。还有一些时间,但后面的 subtask 完全不会做。

总排名略微上升了一些,变成了 rk22,成功在我校垫底了,不过也在意料之中,xzz 和 Itst 太强了。

下午直接坐飞机回去了。

原文地址:https://www.cnblogs.com/gczdajuruo/p/14130385.html