总结

· · 个人记录

前言:抽象

Day 1

T1 非常遗憾,没有看出可以用网络流,抽象,一直在想差分后乱搞,抽象。

T2 非常遗憾,没有学过希尔排序,也没有想到可以先跑精度小的,再重新插入,而且少想了一点优化,少了几分。

T3 非常遗憾,只打了两个 sub 的分,就连询问中间的一段都不会。

总之就是非常遗憾。

Day 2

T1 非常遗憾,没有“观察”出“简单”的性质,最后只有暴力。

T2 非常遗憾,完全没有思路,暴力也不想打(就 5 分)。

T3 非常遗憾,中间忘了,最后只有暴力。

前面忘了,中间忘了,最后三道题只拿了两道题的纯暴力。

很好的题目,使我的脑子飞舞。

我是历史学家,这就是史。

Day 3

T1 险些坠机,出得好啊!把暴力放过去了,分数最高的一集。

T2 比较遗憾,打了暴力,区间打牌,非常好的分数。

T3 非常遗憾,暴力没有调出来,太抽象了。

总之,数据出得很好,有一种暴力的美。

Day 4

T1 写了整场比赛,抽大象了,最后因为向零取整被 gank 了,挂了 20 分,然后因为常数太大又被卡了 50 分,太抽象了,不过还好在最后四分钟调出来了,没有爆零。

总之,常数太抽象了,写得就是依托,还封装了两层,寄。

Day 5

唯一一场题目名都是英文的。

三道题都是数据结构。

T1 比较正常,还算简单,成功地在最后半小时调过了,悲。

T2 没有想到过点画线,丸辣。

T3 到死也没有调出来,丸辣。

有的人 T1 三分钟就过了,有的人差点到死没有调出来,我不说是谁。

Day 6

T1 非常抽象,我一个点分治竟然能 T,不能理解,五万的数据,点分治 T 了,我怕不是复杂度写假了,抽象,挂大分了。

T2 非常抽象,暴力竟然能错了,而且还差得远。

T3 好活,看懂题了,丸辣。

总之,挂分场。

Day 7

T1 非常的好,乱猜结论,然后上树哈希,然后被卡了 40 分,抽象。

T2 暴力分给得很多,发现暴力可以上点乱搞优化,然后过不去。

T3 抽象,全场无人得分,(“我也不是很会证”“我搬的”“我们看下原题题解”)。

抽象。

Day 8

T1 寄飞了,少写了点东西,被一个点卡掉了(甚至只有一个点,数据很好),再加上子任务依赖,哦豁。

T2 暴力,后面没了。

T3 原题,但是不会,丸辣,看题解也不会(日语翻译也太垃圾了),丸辣。暴力抬走。

挂分,挂大分,抽象,寄飞了。

解题:

Day 1

T1

T2

T3

Day 2

T1

T2

T3

Day 3

T1

T2

T3

Day 4

T1

题意:给出 n 个区间 [L_i,R_i],求 \forall i \in [1,n] ,x_i \in [L_i,R_i] 的等差数列 x_{1\dots n} 的数量,对 998244353 取模。

x_i 表示为 x_0 + d \times i,那么就有 L_i \le x_0+d \times i \le R_i,即 L_i-d\times i \le x_0 \le R_i-d\times i,设 x=d,k=i,b_{i_0}=L_i,b_{i_1}=R_i,那么就有 y_{i_0}=-kx+b_{i_1},y_{i_1}=-kx+b_{i_1}

那么对于 d=x 的答案数,其就为 \max(0, \min{y_{i_1}}- \max{y_{i_0}})

考虑到对于 \min{y_{i_1}}- \max{y_{i_0}}(i_1,i_0) 总共只有 O(n) 种,可以直接上李超线段树算单点的最高和最低,然后二分,总共是 O(n \log^2 n) 的复杂度,然后我的常数过大。

代码链接

T2

T3

Day 5

T1

题意:给出数轴上 n 个点的下标 a_{1\dots n} 以及它们的权值 b_{1\dots n}。从 1 号点出发,设当前为 x 号点,每步可以走到 y 号点,当且仅当 L \le a_y-a_x \le R。其中 1 \le L,R \le 10^9,1 \le a_i \le 10^9 , 1\le b_i \le n。求到达 n 号点时,所经过的点的权值序列在排序后字典序最大为多少。不能到达输出 -1

显然,它的转移是一个滑动窗口,那么考虑单调队列,由于需要存下并比较两个序列,考虑使用主席树上二分加哈希,难度适中。

代码链接

T2

T3

Day 6

T1

T2

T3

Day 7

T1

题意:给出一棵有标号无根树的每一个点的邻居集合的集合,求有多少棵这样的树,对 998244353 取模。

考虑将原树上的点视作实点,然后对于每一个邻居集合建一个虚点,将它们连接,这样会出现一张每一条边所连的点都是一虚一实的二分图,容易发现图上不能有环,否则就一定没有答案,那么该图就可以分为两个不连通的树,然后找到这两个树的重心,不论有几个重心,都是一棵树选虚点重心为根,另一棵选实点重心为根,要求这两棵有根树同构,然后对于每一个点(只看一棵树),对于它的所有非叶子结点的子树,如果同构那么可以随意交换,即答案乘上阶乘。同构用树哈希判即可。

代码链接

T2

T3

Day 8

T1

题意不好说,上链接。

那么考虑对于每一个数,它每一轮最多向左移动 k-1,设它的左侧有 x 个数大于它,它移动的轮数为 \lceil \frac{x}{k-1} \rceil

容易发现,对于每一轮,除了第一次以外,都只会影响一个数它左侧大于它的数量,那么考虑记录下每一个数在第几轮会到达前 k 个,然后对于进行了操作的轮数加进答案,再算上每一个数自己的移动轮数减一即可。

代码链接

T2

T3