djwj233 的博客

djwj233 的博客

NOIP2021训练记录

posted on 2021-10-25 21:32:42 | under 计划 |

开这个坑主要是因为原来那个东西长度已经爆炸了。

10月25日

洛谷上连 IOI2021 的题都没有(

听说这题场切,过来写写。

糗大了,还不会做

原来我又 nt 了,直接乱贪心就行了。

10月26日

下午模拟赛又是一场不可做/yun

看到 $\text{\color{black}Z\color{red}CETHAN}$ 在写这题,过来看看。于是发现这是一个思博题。

10月27日

今天没有模拟赛,本来想学学 AC 自动机,但是看到之前有一道题目没写过,过来补补。

果然不会。

难点在于如何从 $\mathrm{Bd}_i$ 转移到 $\mathrm{Bd}_{i+1}$,我刚开始以为只有长的几个会被删除,但是后来发现这样是假的。

之后看了题解,因此写出来的东西就和 jiangly 本质相同了。

这个题给了一种维护 $\mathrm{Bd}_i$ 的做法

10月28日

开了 AC 自动机的坑,啥都没打。

10月29日

没有模拟赛,好耶!

打表找规律,没了 人没了。Code

看到 $\text{\color{black}Z\color{red}CETHAN}$ 在写这题,过来看看。于是发现这是一个思博题。

晚上通宵打 CF/se

11月1日

由于太菜,所以想做黑题就必须要有点提示。

瞄了眼题解发现代码不长,于是开始做。因为瞄了眼题解,所以我们考虑建图。

显然我们需要把每个操作当成一个点来跑最短路。我们把这个过程画成二维的形式,发现一次治疗对应着图上阶梯状的一块,如果两块有公共点则说明可以连边。

这样暴力建图边数就是 $\mathcal O(n^2)$ 的(以下 $n$ 均指题目中的 $m$),显然过不去。

我们先写出这个东西的形式,$(i,j)$ 间有边,当且仅当:(以下有 $R_i\le R_j$)$$ R_i-L_j+1\ge |T_i-T_j| $$ 我们考虑对 $T$ 一维排序,然后去掉绝对值,移项:$$ \begin{cases} R_i-T_i+1\ge L_j-T_j & T_i\geq T_j\\ \\ R_i+T_i+1\ge L_j+T_j & T_i<T_j \end{cases} $$ 我们发现不等号两边已经只和 $i,j$ 之一相关了,但是还是不会做 qwq。

学一个线段树优化建图的东西,我们考虑去对 $T$ 建线段树维护这两个值,然后每次不保存这个点能到达的所有边

那怎么做呢?我们考虑到 Dijkstra 的性质以及本题入边权值固定的特性,当前已经被更新过的点一定不会被更新。

所以我们在松弛一个点时,在势能线段树上 DFS 一遍,总点数是 $\mathcal O(n)$ 的。

总复杂度 $\mathcal O(n\log n)$。Code

11月2日

一道 CF 2300 的题在洛谷中是黑

Code

这个 djwj 菜得不行,靠做 ABC 的 C 谋生

Code

11月3日

和 cmll02 VP 了一场 gym,被带飞了

11月4日

看到 $\text{\color{black}Z\color{red}CETHAN}$ 在写这题,过来看看。于是发现这是一个思博题。

Code

黄题,不会,看了题解。$$ \vec{a}\vec{b}+\vec{a}\vec{c}+\vec{b}\vec{c}=\dfrac{1}{2}((\vec{a}+\vec{b}+\vec{c})^2-\vec{a}^2-\vec{b}^2-\vec{c}^2) $$

$$ =\dfrac{1}{2}((\vec{a}+\vec{b}+\vec{c})^2-r_1^2-r_2^2-r_3^2) $$

故 $(\vec{a}+\vec{b}+\vec{c})^2$ 应尽量小,那么能取 $0$ 则取 $0$,否则取三者共线。

Code

绿题,不会,看了题解。原来上界是 $\log n$......

不过我用的做法是记录最大值、次大值。Code

11月5日

我们设 $f(x,y)$ 为已经枚举到 $x$,选了 $y$ 个的答案,有:$$ f(n,m)=f(n-1,m)+(n+1-m)f(n-1,m-1) $$ 我们发现这和第二类斯特林数的形式$$ {n\brace m}={n-1\brace m}+m{n-1\brace m-1} $$ 很像。打出两个表,我们发现实际上有:$$ f(n,m)={n\brace n-m} $$ 那么直接计算即可。Code

紫题,不会,看了题解。

神仙构造题,Code

想了半天,最后发现就是个树剖板子(

11月8日

好长时间没记了呢......

神仙博弈论,懒得记了,反正也不怎么会。

Code

11月9日

DSU on Tree 板子题。Code

胡出了 70pts 做法,然后看了题解,大致会了。

打算明天再写。

11月10日

今天没有模拟赛!!!

AGC 的题,来硬刚,然后刚不出来。瞄了一眼题解,发现结论是 $\dfrac{cnt0_i}{cnt1_i}$(((

然后就是用堆维护点集,并查集维护形态的常见套路了。

那么为什么是这个结论捏?因为不同的取法产生的贡献是乘积形式的。

Code

11月12日

思波题。Code

我是傻逼!!!

总的说,碰到求幂的和的问题不能直接硬刚,要考虑一个维护幂的思路。

Code

经典题。二分答案,然后把大于等于 $x$ 的数写成 $1$,然后用线段树维护 $01$ 序列的排序。

Code

然后打 CF。

11月16日

就是上次 ABC 的 D 的一个应用(

Code

简单 DSU 练手题。Code