广大附中游记

zimindaada · 2020-01-18 21:09:49 · 个人记录

Day 0 （2020-1-14）：

今天一考完期末，就立刻被拉到了广大附中去集训了。这里的宿舍床板挺小，我床单子大了一大截，不过倒没有文字。同宿舍的增城校区的宿友挺儒雅随和的样子，没怎么指手画脚。

Day 1：

今天一来，就来考了一场试。提高组的题。

T1：一道简单的期望计算，n≤10^{18}找规律，发现答案可以O(1)求。便打了O(1)交了上去。但是！由于中间直接爆了long long，导致取模的时候取模了负数，答案就错了 （哪个狗想到的负数取模得负数的）。

T2：我看了，想不出正解，有什么好说的？看了一个小时，最后打了个全排列，拿了个20分。正解是一个很神奇的DP，通过一个很神奇的取平均数压缩了很多的无用状态。

T3：很明显一道区间维护题，但这状态没想出来，因为有很多5个东西要维护，以为是什么高级结构，就打了个dfs骗了10分。结果就是线段树，维护了5个东西可能发生每种情况的全排列。

考完了试就讲题，一点都没有听清，下午改了一个下午的题，还听了省选组讲作业听清了也听不懂。晚上讲了线段树合并的几道题，大概学了一点，这几天就一直在调线段树合并。

Day 2：

今天依然是一场提高组的考试

T1：类似小学的奥数的一道题，求两个中点，然后计算。100分。

T2：我 炸 了。考试的时候被那个d坑到哭，加上牛的个数不确定，导致最后连暴力都打不出来。（n≤100连Dfs都难打）。答案是个DP，把每个点都做一遍根，记搜一遍，就完了。他的状态设计的很好。将dp[i]设置为以i为最高的点的连通块的数量。本来我考试最后时已经把状态和转移式子推出来了，结果卡在了一个判断差在不在d以内，结果一个if判断就完了。

T3: 我 又 炸 了。看了题，也是一片茫然。看起来很像一个最小生成树，可是想不出以什么作为树的边权。遂打了个暴力dfs，拿30分的暴力分，结果一个点多组数据时没有清空数组导致GG，反而骗样例骗到了10分。正解要用到Dinkelbach算法来做，而90分可以用Prim/Kruskal卡常拿，通过推式子+二分答案推出边权维护的东西。

下午和晚上是广附的拜年祭，下午有校园集市，晚上就是校园春晚。我晚上改完题后基本准点看了校园春晚，有几个唱的不错。

Day 3

考的提高组。

T1：心 态 大 逆 转。一开始就手推出了一个用排列推出来的O(n)式子，只差一点：O(n)求定长的合法括号串的个数。然而随着时间的流逝，我发现我只推的出来O(n^2)的，而且就当我放弃正解转求部分分时，发现式子本身就是错的。看着考场上看着其他人一个个推出式子提交100分，再加上后面一道题都不会，我感觉我连送分题都做不出来。心态崩了。结果……考完后一评测，除了几个人，其他人式子推错，也没拿到分。而我打了一个n=m的5分，反而很赚。正解就是dp

T2：不会。输出-1。完事了。正解二分图+圆方树/bfs。不会。

T3：不会。打了个暴力，拿了20分。正解是个神奇的dp。到现在都想不清为什么那么打

下午听了广附那边北大的大师兄讲的组合数学的基本内容，如二项式定理，求组合数的方法等。听懂了。

Day 4

今天没有考试。上午昨天那个大师兄继续把组合数学讲完了，然后讲了可持久化线段树（主席树），大概听懂了，晚上做了模板题。下午听另一个北大的数学巨佬大师兄讲莫比乌斯反演和欧拉函数。那个我记了笔记，证明什么没怎么听懂。

晚上，就在我刷完主席树模板题的时候，我就被通知要回家了。