2024.8.19：

A：

模拟题。

B：

直接搜索。

C：

原题可转化成寻找二进制下后缀连续1的个数的所有可能，将所有数反转，存进线性基再枚举即可。

D：

n小的情况直接上最小乘积生成树，大的情况用凸包合并。

2024.8.20：

A：

推公式，发现是求动态逆序对，可用树套树/cdp等方法解决。

B：

考虑分治，再用线段树维护即可。

C：

可以转化成二分图最大权匹配，但点/边数过多，贪心，只选择前$2nk$大的边和对应点，可以大大降低总点数，由于是稀疏图且点数较少，用mcmf可以解决。

D：

析合树板子，也可以离线下来用线段树和单调栈维护。

2024.8.21：

A ：

明显是个背包，不过有点麻烦，需要支持撤回，用可撤销背包维护即可，枚举哪一个掉进魔法洞直接把 for 循环倒过来做
一遍就可以了

B ：

考虑对每个$s_{i}$，先将$s_{i}$中的$M$个字符串都只保留其中最短那个的长度，再将$s_{i,j}$一位一位地依次串起来，得到字符串$r_{i}$(例如：$s_{i}=\{ abcde, fghi, \operatorname{xxxxxx}\}$，先将它们长度都变成 4 ，$\{\mathrm{abcd} , \mathrm{fghi}, \mathrm{xxxx}\}$，然后串起来，$r_{i}=\mathrm{afxbgxchxdix}$）。

然后将$r_{i}$放进 trie 中，和$M=1$类似的，对树上每个点计算出以它为 LCA 的点对个数，它对答案的贡献是$\left\lfloor\frac{\text { depth }}{M}\right\rfloor$(depth 为该点深度) 。

C ：

给每行赋予一个随机值$w_{i}$，用于哈希，预处理$s_{i, j}$表示$b$矩阵第$i$列，等于$j$的行的随机值的和，然后枚举每一行，检查是否合法就行了。

D ：

考虑吉司机线段树，维护$a$最大、次大值，对应的$b , c$的最大、次大值，将询问离线下来即可。

2024.8.22：

A ：

很明显倒着模拟与正着模拟等价，所以从后往前枚举即可。

B ：

考虑有效的值数量很少，用map维护，直接搜索即可。

C ：

观察性质，发现在最优情况下，一个点与其对应的前缀最大值和后缀最小值之间至少存在一条边。

考虑树的性质，对$n-1$个点，每个点连出一条边即可得到最小值。

直接这么贪心连边显然不行，因为会出现环（example：0 1 -1 1，这里1和-1会相互连边）。

所以先排序，用若干个最小值将原数列分为若干个连续段，使得段内每个数对应的后缀最小值相同。

从前往后操作每个段：

• 对于非段尾的数，要么与前缀最大值连边，要么与段尾连边，取$min$即可。

• 对于段尾的数，自身为后缀最小值，所以只能与最大值连边，但考虑若段内产生前缀最大值，必定与段尾连边，所以只能选择之前段中的最大值。

D ：

思路就是询问时$\Sigma^{2}$枚举字符，然后实现$O(1)$计算这两个字符在询问区间内的串长就可以过掉，考虑维护每个相同字符的管辖范围，用nex数组记录，每次直接跳就行。

2024.8.23：

A ：

考虑合法分割的性质，要么大小为偶且均合法，要么为奇且存在一个不合法，前者为子树大小相乘，后者为合法的点数相乘，用树形dp维护，再考虑换根转移，用前缀和维护，这样可以计算出每棵树子树的答案，最后枚举每条边断掉后的贡献即可。

B ：

可以观察到最小时间等于N 减去补图的最大匹配。可以证明本题的答案和补图的最大匹配是双射（具体的映射应该很好猜），那么我们对于一组最大匹配只需要一直找入度为0的点就可以排出一个操作顺序。

2024.8.24：

A ：

维护每个数可出现的区间，将区间长度乘起来即可。

B ：

建立SAM，将概率模型建立在自动机上，消元，用维护无向图的方法维护即可。

C ：

考虑搜索，朴素算法过不了，所以用bitset维护加边情况，可以降低很多复杂度，卡卡常就过了。

2024.8.26：

A ：

经典组合数求解，从一个障碍点向下一个障碍点转移，方案数可以用组合数处理，需要用lgv引理优化，复杂度较优。

B ：

可以分为非等边的等腰三角形、等边三角形，和普通三角形，前两个可以分别计算，最后一个用离散二位数点维护。

C ：

用ax+b表示每一条边，将代入矩阵树定理中，将a表示成矩阵A,b表示成矩阵B，首先将A消成单位矩阵，同时对B乘上$a^{-1}$，现在我们要求的就是$xI+B$的行列式，我们考虑将这个矩阵消成海森堡矩阵,在消元完之后我们就可以将矩阵的值表示成一个n次多项式，计算自然数幂和即可。

2024.8.27：

A ：

用dp求出和为sum，只由j以上的素数构成，且长度为i的方案数，搜索时加上方案数，若小于l则直接跳过该分枝，否则直接展开输出。

B ：

将序列上AC自动机，再自动机上进行期望dp转移即可。

C ：

维护序列哈希，$O（1）$维护修改，每次直接查询即可，最好使用umap防止卡常。

D ：

双指针维护前后缀+ST表，求个路径交即可，比较简单。

2024.8.28：

A ：

对一个下标的修改次数分类。设一个间值$B$，对修改次数$>B$的下标使用$\mathcal{O}(n+q)$的暴力。

B ：

实际上，根据算法中的$t$，整个算法可以描述成: 初始$t=n-m$，每次若$t<0$则进行$R$(同时$t$加$n$)，若$t>0$则进行$U$（同时$t$减$m$），若$t=0$则停止；

如果交换$n$与$m$也有同样的描述（交换$n$与$m ， R$与$U)$。

若$n=1$直接快速幕，若$n>m$就交换$n$与$m$（也要交换$R$与$U$），若$n<m$，则令$p=m \bmod n, q=\lfloor m / n\rfloor$，那么也可以描述成：先进行$R^{q} ， t=n-m+q n=n-(m \bmod n)=n-p$，每次$t<0$则进行$R$(同时$t$加$n$)，否则进行一次$U R^{q}$(同时$t$减$(m-q n)=p$)，则把$(n, m, R, U)$的情形化为$\left(n, p, R, U R^{q}\right)$的情形，即辗转相除。

每次计算$R^{q}$用快速幕可以做到$\mathcal{O}(\log q)$，同时$n m$至少降到原来的$1 / q$。

C ：

可以暴力建最小割树取得70分暴力分，考虑正解，我们反复操作直至图上不存在一个凸包为止，这样我们就建出了最小割树。对于每一条边的贡献我们按照克鲁斯卡尔贪心地去计算即可，注意到我们删去一条边的过程，我们如果删去一条边，那么就意味着需要在找到端点的最短路的同时将最短路上的边加入外层边集合。由于原图是一个凸包，按照标号的规律，就可以简单地通过对编号排序实现边的极角排序。

2024.8.30：

A ：

考虑 DP，设$d p[i][0 / 1]$表示$[1, i]$正确划分的方案数，其中最后一段是否合法，当$\operatorname{gcd}(D, 10)=1$时，相当于是$p r e[j] \equiv p r e[i+1](\bmod D)$，直接开个桶就好。当$\operatorname{gcd}(D, 10) \neq 1$时，设$D=2^{x} 5^{y} m$，那么相当于要求$\% 2^{x}, \% 5^{y}, \% m$同时为 0 。

对于固定的$i$，在$j \leq i-20$以后$s[j]$的贡献$\% 2^{x}, \% 5^{y}$都是 0 了，只用考虑$m$的限制，此时同样可以对$\% m$开桶。对于$j>i-20$直接暴力即可。

B ：

考虑到幸运数字的数目很少,考虑直接爆搜+剪枝即可通过。

C ：

我们发现，从删掉$(i, i+1)$移动到删掉$(i+1, i+2)$产生的影响并不多，严格来说均摊变化量是$\mathcal{O}(P)$的。开一个线段树，相当于每次做区间$+1 /-1$，查询全局$>0$的位置权值之和。

D ：

我们发现可以$\mathcal{O}(1)$计算出$d i s$的上升和下降段分别是多少，在最终的结果数组里打一个差分标记即可。注意需要特判$i=0, K$等情况。

2024.9.2：

A :

先看整数部分，我们设$f_{i, j}$表示考虑到$x_{i}$，所有情况下和的$j$次方的和 (期望除一个方案数就行)，则有：

$$\begin{aligned} f_{i, j} & =\sum_{p=l_{i}}^{r_{i}-1} \sum_{t=0}^{j}\binom{j}{t} f_{i-1, j-t} p^{t} \\ & =\sum_{t=0}^{j}\binom{j}{t} f_{i-1, j-t} \sum_{p=l_{i}}^{r_{i}-1} p^{t} \end{aligned}$$

我们发现后面是一个自然数$t$次方和的形式，可以插值轻松求出。这部分复杂度是$\Theta\left(n k^{3}\right)$，预处理一下就变成了$\Theta\left(n k^{2}\right)$。

再考虑小数部分，这就是所有数取值范围都是$[0,1)$的那一档部分分。考虑最后$\left\lfloor x_{1}+x_{2}+\ldots+x_{n}\right\rfloor$的取值不会超过$n$，我们对 1 到$n-1$都求出取到它的概率。

我们设$s_{i}$为$\sum_{j=1}^{i} x_{j}$的小数部分，容易发现，$\left\lfloor x_{1}+x_{2}+\ldots+x_{i}\right\rfloor=\left\lfloor x_{1}+x_{2}+\ldots+x_{i-1}\right\rfloor+1$当且仅当$s_{i}<s_{i-1}$。

我们不妨将$s_{i}$替换成$s_{i}$在整个数列中的排名，最后会的得到一个序列。

显然所有$n!$种序列出现的概率都是相等的。考虑dp，设$g_{i, j}$表示长度为$i$的序列有$j$个位置满足$s_{i}<s_{i-1}$的方案数。

我们从小到大往序列里插数。有四种情况:

1.插在开头，从$g_{i-1, j-1}$转移过来。

2.插在结尾，从$g_{i-1, j}$转移过来。

3.插在一个满足$s_{i}<s_{i-1}$的位置中间，从$j \times g_{i-1, j}$转移过来。

4.插在一个满足$s_{i}>s_{i-1}$的位置中间，从$(i-j-1) \times g_{i-1, j-1}$转移过来。

所以我们得到方程:$g_{i, j}=(j+1) \times g_{i-1, j}+(i-j) \times g_{i-1, j-1}$，可以$\Theta\left(n^{2}\right)$求出。

B :

现在我们想要得到一个概率生成函数，即设$B_{i}$表示随机了恰好$i$次之后停止的概率，$B(x)=$$\sum_{i=0}^{\infty} B_{i} x^{i}$，那么有

$$B(x)=\frac{P\left(\frac{x}{m}\right)}{Q\left(\frac{x}{m}\right)}$$

再考虑如何计算答案，答案的 EGF 为$B\left(e^{x}\right)$。

$B$的分子和分母上的都是一个有限次的多项式。

换言之，现在问题规约成，有一个$N$次多项式$F$，我们想要求$F\left(e^{x}\right)$对某个$x^{M}$取模之后的结果。

$$\begin{aligned} & F\left(e^{x}\right) \bmod x^{M} \\ = & \sum_{k=0}^{N} F_{k} \cdot e^{k x} \\ = & \sum_{k=0}^{N} F_{k} \cdot \sum_{i=0}^{\infty} \frac{k^{i} x^{i}}{i!} \\ = & \sum_{i=0}^{M-1} \frac{x^{i}}{i!} \sum_{k=0}^{N} F_{k} \cdot k^{i} \end{aligned}$$

这个可以通过计算

$$\sum_{k} \frac{F_{k}}{1-k x}$$

来完成。

C ：

拓展gcd写掉部分分，我们将其拓展一下，用向量作为exgcd的基底，和实数一样带入系数计算即可。

2024.9.3：

A ：

期望部分很好求，直接枚举每一个三元环算贡献即可。求最大值，考虑每个点每有两条出边便会使三元环个数减一，每条边会使两个端点中的一个出度加一，将每个点被选次数的贡献做个差分，上费用流即可。

B ：

发现一个瓶颈在求最小的$l$，其实就是该前缀的最长后缀，而参与匹配的是$S$的所有字串，所以想到维护所有字串信息的后缀自动机，所以我们开$n$个后缀自动机，求出对应的最小$l$就可以$|T|^{2}$转移了。

C :

首先$f(n, 0)=1$，之后

$$f(n, k)=\sum_{x_{1}=0}^{n}\binom{n}{x_{1}} \sum_{x_{2}=0}^{x_{1}}\binom{x_{1}}{x_{2}} \sum_{x_{3}=0}^{x_{2}}\binom{x_{2}}{x_{3}} \ldots \sum_{x_{k}=0}^{x_{k-1}}\binom{x_{k-1}}{x_{k}}$$

运用二项式定理对每一 “层” 都运用二项式定理"剥壳"

$$f(n, k)=\sum_{x_{1}=0}^{n}\binom{n}{x_{1}} \cdots \sum_{x_{k-1}=0}^{x_{k-2}}\binom{x_{k-2}}{x_{k-1}} 2^{x_{k-1}}$$

具体地以后面$\sum_{x_{k-1}=0}^{x_{k-2}}\binom{x_{k-2}}{x_{k-1}} 2^{x_{k-1}}$为例运用二项式定理"剥壳"，可以知道:

$$\sum_{x_{k-1}=0}^{x_{k-2}}\binom{x_{k-2}}{x_{k-1}} 2^{x_{k-1}}=3^{x_{k-2}}$$

所以:$f(n, k)=(k+1)^{n}$，那么:

$$f(f(n, i), i)=(i+1)^{(i+1)^{n}}$$

快速幕计算即可。注意运用欧拉定理计算快速幕时应该模$\bmod -1$。

2024.9.4：

A :

我们考虑二元生成函数：

$$G(x, y)=\sum_{i \geq 0} \sum_{j \geq 0} \text { one }(i, j) x^{i} y^{j}$$

那么可以得到：

$$\text { ways }(i, j)=\left[x^{i} y^{j}\right] \sum_{k \geq 0} G(x, y)^{k}=\left[x^{i} y^{j}\right] \frac{1}{1-G(x, y)}$$

那么二元多项式的求逆可以通过 NTT 来解决。复杂度为$O\left(1000^{2} \log 1000\right)$。

B ：

考虑贪心求区间极大段，用区间和减去即可。

C ：

考虑 dsu on tree，那么根据dsu on tree的过程，我们要处理轻儿子间的合并以及重链的信息继承，发现前者很容易，只需要分治 FFT
或者启发式合并就可以完成。但后者没那么容易处理，原因是最后加x 的过程。重新观察转移，发现可以写成矩阵形式，即

$$\left(\begin{array}{ccc} F_{x} & 0 & 0 \\ 0 & F_{x} & 1 \\ 0 & 0 & 1 \end{array}\right)$$

然后答案矩阵是

$$\left(\begin{array}{c}F \\ G \\ 1\end{array}\right)$$

2024.9.5：

A ：

考虑把操作倒过来，就变成每次加一个点。用并查集维护连通块以及其权值和即可。

B ：

考虑在$k$次$f$操作后，原数组中位置$(i, j)$对答案的贡献，是$\binom{k}{i} \times\binom{ k}{j}$次。由于是异或操作，所以只有在贡献次数为奇数时才有实际的贡献。

那么真正需要考虑的$k$就是$\max (n, m)$在二进制下最高位以内的数位。也就是只需要预处理出$0 \leq k<2^{23}$的答案。使用高维前缀和优化即可。

C：

分成 “存在交为空的集合” 与 “不存在交为空的集合” 来讨论。

如果存在交为空的集合，显然只能有一个 (不然可以合并起来)。然后其余的集合大小一定为 1 ，否则可以只保留里面长度最长的线段。因此这种情况只要按长度排序，贪心选择最长的那些。

如果不存在交为空的集合，对于线段$i$和$j$，如果$i$完全包含了$j$，那么$i$只有两种选择：跟$j$放在同一个集合，或者自己独占一个集合。其他选择可以用调整证明不会更优。

因此对于完全包含了某个其他线段的线段，我们要么忽略它，要么让它独占一个集合。对于剩下的线段，排好序后显然左右端点都是单调的，调整可以证明每个划分的集合都是占据了一个连续段。

考虑$f(i, j)$表示用$i$个集合划分前$j$条线段的最大权值，转移形如:

$$f(i, j)=\max _{k<j}\left(f(i-1, k)+r_{k+1}-l_{j}\right)$$

可以使用前缀和优化转移。

最后与完全包含了某个其他线段的线段的贡献合并一下就可以得到答案了。

D:

考虑点分治，每次求出在当前处理的这个连通块中，包含分治中心且符合条件的方案数。求出以分治中心为根的 dfs 序，考虑$f(i, j)$表示考虑了 dfs 序中的前$i$项，目前点集内乘积为$j$的方案数。

注意到状态里记录乘积恰好为$j$很浪费，可以记录最大还能乘到多少，即$f\left(i,\left\lfloor\frac{m}{j}\right\rfloor\right)$表示考虑了 dfs 序中的前$i$项，目前点集内乘积为$j$的方案数，这样第二维就只有$O(\sqrt{m})$种取值。

转移的话，每次在递归的时候将这个点的方案传给儿子，再在回溯的时候将儿子的贡献加回父亲上即可。

2024.9.6：

A ：

打一下表发现操作次数循环节为23到46，于是用分块维护每一段操作前46次操作后的答案。

B ：

考虑将石子分为大小为/不为一的两组，然后记忆化搜索即可，注意取石子时的合并细节。

C:

能否构造出最大匹配恰为给定值$x$的充要条件是: 去掉 0 度点后$x$不大于二分图其中一边的点数，且存在一个大小为$x$的点集$S$(其中的点可以分布在两边) 满足$S$中的点的度数之和恰为边数$m$。

$\mathrm{O}\left(n^{6}\right)$的DP大概就是记$f[i][j][k][l][m]$表示做了前$i$个点，其点度之和为$j ， S$中有$k$个非 0 度点，$S$中点度和为$l, S$外有$l$个非 0 度点就可以直接DP了。

2024.9.9：

A ：

用优先队列维护节点，以当前节点到子树中最深节点的距离为关键字，每次选$m$个即可。

B ：

博弈论。

C ：

因为有效串的个数为$nlogn$级别，预处理出所有变换完后的串的哈希值，每次比较即可。

D ：

考虑枚举二进制下1的个数，将小于的放进或集合，将大于的放进与集合，当前枚举的这一项可以放进与集合里或者是或集合里，若当前项内所有数相等，也可以拆开放进两个集合里，维护区间$xor$和区间$and$即可。

2024.9.13：

A ：

将所有球按标号排序，然后按照基数排序的思想分治处理即可。

B ：

考虑状压算出每个状态对应的可以走到的点，对于其他点用1的路径首尾连接即可凑出合法的点对。

C ：

考虑建ACAM或SAM，对于每个字符串k枚举所有可能的i，考虑到合法的字符串只有$|S_k|$个，时间复杂度正确。

2024.9.14：

A：

原，8.19C

B：

多项式多点求值即可。

C：

考虑无解情况，从后往前找到第一个$cnt≠0$的值，设$sum=0$每次使$sum>>1+cnt_i → sum$，需要保证$sum$恒大于$2$，剩下的直接dp即可。

2024.9.16：

A：

三维偏序板子，离线二维数点可以做到单$log$。

B：

考虑建$PAM$，建出回文链接数，树剖之后维护即可。

C:

将每个点的值改为$a_i-\sum_{u∈ son_i}a_u×b_u$，然后可以转化为阶梯博弈，将所有奇数层的$SG$值$xor$起来判零即可，注意若$b_i=0$要将当前点归为奇数层，其子树按当前点计算。

2024.9.17：

A：

换根dp

B：

30分Floyd即可解决，100分对每个连通块找循环节，最后合并即可。

C：

树上无敌大粪讨吗，相当麻烦，不在这写了。

2024.9.18：

A：

唐题，倒着考虑即可。

B：

神秘多项式不可做题，被创飞了，谁教你放在B的。

C：

首先计算出 直飞成本，这个可以简单 bfs 求出。

剩下的部分考虑 DP，记$f_{i, x}$表示花费代价为$i$，走到编号为$x$的岛屿最多能够乘坐多少次飞机。由于 直飞成本是曼哈顿距离，所以$0 \leq i \leq n+m$，岛屿数$x \leq n^{2}$，状态数是$O\left(n^{3}\right)$的。

直接枚举每个岛屿能飞到哪些岛屿，对这些岛屿之间连边，边数是$O\left(n^{4}\right)$的。 DP 时对每个$i$进行一次转移，总时间复杂度$O\left(n^{5}\right)$，可以通过 subtask2。

考虑优化建边，一对点$(u, v)$之间有边，一定满足最小的包含$u, v$的矩形内没有别的陆地，否则选择这条边转移一定不是最优的。证明如下:

假设这个矩形内还有一个点$p$，若$p$与$u, v$均不属于同一个岛屿，那么可以花费相同的代价乘坐更多次的飞机。若$p$与$u, v$之一属于同一个岛屿（假设和$u$属于同一岛屿），那么从$u$步行到$p$然后再坐飞机代价更小。

使用单调栈 (或者其他方法) 维护，这样边数就是$O\left(n^{2}\right)$的了，因为每个点最多被一条边所在的矩形覆盖。总时间复杂度是$O\left(n^{3}\right)$的。

D：

模拟题，预处理每四百年的循环节即可，比儒略日简单。

2024.9.19：

A ：

设$f(x)=\left\lfloor\max \left(K / x^{2}, \sqrt{K / x}\right\rfloor, f(0)=+\infty\right.$，那么$a_{i} a_{i+1}$合法当且仅当$a_{i+1} \leq f\left(a_{i}\right)$。

如果从$i$开始的连续段长度为 1 ，那么方案数显然就是$\min \left(f\left(a_{i-1}\right), f\left(a_{i+1}\right)\right)+1$。

否则，设$A=f\left(a_{i-1}\right), B=f\left(a_{i+2}\right)$，那么就要计算

$$\sum_{x=0}^{A} \sum_{y=0}^{B}[x y \min (x, y) \leq K]$$

显然应该分类讨论$\min (x, y)$是啥，不妨假设$x \leq y$。那么直接校举$x$，就是求

$$\sum_{x=0}^{A} \max \left(0, \min \left(B,\left\lfloor K / x^{2}\right\rfloor\right)-x+1\right)$$

显然这是一个分三段的函数，分别对$\max (0, \cdots)$和$\min (B, \cdots)$求出分段点即可。

但是暴力怎么96pts捏。

B：

直接人脑 xor 卷积看结果。两个前缀做 xor 卷积时直接 xor 起来就可以获得一个新前缀，长度就是两个前缀长度的 min 。

容易发现做完 xor 卷积之后仍然只有$O(\log m)$个前缀，且仍然存在一个数$x$使得每个前缀除掉最后一位之后就是$x$的前缀。于是就做完了。

C:

Lemma 1. 在最优解中，如果$k_{i-1} \leq k_{i} \geq k_{i+1}$，那么必然有$k_{i}=\min \left(p_{i}-p_{i-1}, p_{i+1}-p_{i}\right.$，也就是说如果$k_{i}$是衱大值，那么它必然顶到了$p_{i-1}$或$p_{i+1}$。

证明. 显然$k_{i}+k_{i-1}=p_{i}-p_{i-1}, k_{i}+k_{i+1}=p_{i+1}-p_{i}$， 也就是两边都要相切，否则肯定不是最优解。

不妨设$0<k_{i-1} \leq k_{i+1}$，那么令$k_{i-1}^{\prime}=0, k_{i}^{\prime}=k_{i}+k_{i-1}, k_{i+1}^{\prime}=k_{i+1}-k_{i-1}$。 一波计算得

$$\begin{aligned} S^{\prime}-S & =\left(k_{i}+k_{i-1}\right)^{2}+\left(k_{i+1}-k_{i-1}\right)^{2}-k_{i-1}^{2}-k_{i}^{2}-k_{i+1}^{2} \\ & =2 k_{i} k_{i-1}+k_{i-1}^{2}-2 k_{i+1} k_{i-1} \\ & \geq k_{i-1}^{2} \\ & >0 \end{aligned}$$

也就是把$k$替换为$k^{\prime}$严格更优，与最优解矛盾。

设$l_{i}=p_{i}-p_{i-1}$。 可以看出，确定$p_{j}$是极大值时，至多只能控制$k_{i}, \cdots, k_{j-1}$，而且这恰好对应一个极长上升子段$l_{i+1}, \cdots, l_{j}$（当然，也可以对应一个极长下降子段。）

由于所有极长上升子段的长度之和是$O(n)$的，因此令每个$p_{j}$为极大值时能推出的$k$的个数之和也是$O(n)$的。因此每个位置能取的$k$的个数之和也是$O(n)$的。

于是就变成从$O(n)$个区间中选出权值和最大的不交区间集合了。

设$S_{i}$表示$i$这个位置对应的区问集合。由于还满足$S_{i-1}$和$S_{i}$的区间两两不交，所以从左往右进行一个简单 DP 即可。

场上想出来但是挂分了。

2024.9.20：

A ：

可以一眼看出是数论分块，不过怎么挂分了/kk

B ：

考虑到斐波那契有效项比较小，每次枚举，并选出符合条件的x和y，这个可以用exgcd解决，时间复杂度单log。

C ：

考虑二分最短路，每次check遍历每一条边，检验是否可以将最短路增加到此长度即可。

D ：

还是二分答案，既然想要最大速度尽量的小，那我们就一定要让每一个人的烟花都燃烧完，让点燃的时间最长。

于此同时，让最大速度尽量小的第二点，就是让人们两两之间的距离尽量小，所以需要我们让所有人都尽量靠近那个烟花正在燃烧的人。

由于他们之间的距离是确定的，且每个人的速度也由二分答案枚举而确定，所以我们可以将他们之间的距离变成时间。

为了尽量压缩所枚举人的时间，我们将每一部分人当作一个集合。

从现在拿烟花的那个人开始，左边第一个可以使他烟花然烧时间变长的人与他之间的一段人为一个集合，记录下这一集合中能使他增长的时间以及需要的时间，就是这个过程他烟火时间最少的时间。

由此，多次同样的操作。

注意的是，如果这个时间有集合可以选择，就一定要先看集合。

最后还剩一段时，原理相同，用相反的方法即可。

2024.9.23：

A ：

树形dp，需要维护子树颜色数量最大值，直接上dsu即可，差不多$n\ log\ n$。

B ：

总共两种做法，一种是对每条 spark 边界线，看其他 spark 是否覆盖掉了它在游戏区域内的所有区段，如果没有覆盖完，则说明有安定点， 这样就是一个线段覆盖问题； 另外一种就是把所有交点求出来，然后扫描线 + 点事件来 维护所有 spark 边界线的上下位置，然后维护一个前缀和之类的 来看中间是否有空隙。

C ：

首先对于每一个位置，经过若干次操作之后会变成$k_{p}^{k_{p-1}^{\prime \prime}}$的形式，从最底层开始套用拓展欧拉定理，则经过$\mathrm{O}(\log P)$层，模数就变成 1 了，所以更上面的数字就设有意义了，暴力的做法就是对于每个位置维护一个$\mathrm{O}(\log P)$的常塔。

进一步分析，对于一段区间，如果对其进行$\mathrm{O}(\log P)$次相同的修改操作，最后这段区间所有位置就会等价，我们就可以合并这段区间。

所以考虑给$n-1$个间隔设置势能，一次$[l, r]$的区间修改可以把$[l, r]$内的间隔的势能都减去 1 ，然后把$l-1$到$l$和$r$到$r+1$这两个间隔的势能加上$O(\log P)$。

可以用线段树加 set 或者 splay 来维护每个间隔的势能，以及合并等价区段。这部分的复杂度即为$O(n \log n \log P)$。

基于以上的分析，我们需要进行$\mathrm{O}(n \log P)$次常塔结果计算，也即需要计算$\mathrm{O}\left(n \log ^{2} P\right)$次快速幂，所以我们希望可以快速地计算快速幂。

这里因为$P$较小，且只会有$O(\log P)$种有用的模数，更关键的是因为欧拉函数每迭代两次就至少会把一个数变成一半。所以考虑对每个模数下的每个数字的幂次结果进行类似 BSGS 的预处理，可知复杂度为：

$$\mathrm{O}\left(P^{\frac{3}{2}}+\left(\frac{P}{2}\right)^{\frac{3}{2}}+\cdots\right)=\mathrm{O}\left(P^{\frac{3}{2}}\right)$$

这样算一次快速幂就可以做到$\mathrm{O}(1)$了。时间复杂度:$\mathrm{O}\left(n(\log n+\log P) \log P+P^{\frac{3}{2}}\right)$。

2024.9.24：

A：

Sub1

维护区间加法，查询区间$\leq k$个数。

考虑分块，每个块维护一个加法标记，每次修改对于块进行排序。

1. 容易发现修改之后，一定是一部分数增加$k$，一部分数不变，将这两部分归并即可完成线性排序。

2. 查询$\leq k$的个数，可以通过离线，排序询问，就能将二分的过程转化为维护一个指针。值域只有$10^{7}$是为了方便选手进行询问的排序。

Sub2

求$S(n, m)=\sum_{i=0}^{m}\binom{n}{i}$

由$S(n, m)=S(n, m-1)+\binom{n}{m}, S(n+1, m)=2 S(n, m)-\binom{n}{m}$，可以用简单莫队维护。

B：

结论 : 一个块大小$k$是合法的，当且仅当树上有$\frac{n}{k}$个节点的 size 是$k$的倍数。

C：

$$f^{\prime}(\theta)=b-\frac{a h \cos \theta}{\sin ^{2} \theta}$$

由于$\cos \theta$在$D$上递减，$\sin \theta$在$D$上递增，容易发现$f^{\prime}(\theta)$在$D$上单调递增。
由此得到$f(\theta)$有唯一最小值 。

设$x=\cos \theta$，则极值点$f^{\prime}(\theta)=b-\frac{a h x}{1-x^{2}}=0$

$$\begin{array}{c} b\left(1-x^{2}\right)=a h x \\ b x^{2}+a h x-b=0 \end{array}$$

解这个方程得到$\cos \theta$，然后得到$\theta$，可以$O(1)$回答询问。

D：

容易发现答案一定包含直径的某一个端点，枚举是哪一个端点，以这个端点为根，建一棵树，然后对这棵树进行长链剖分。

此时，答案一定是选择了 根到达一个叶子的路径，以及$k-1$对叶子，也就可以看成是选了$2 k-1$个叶子。

此时，我们贪心地来选择叶子，一个叶子的贡献为它与它所在链顶端的点的距离。

此时我们只需要选出贡献最大的$2 k-1$个叶子，容易证明一定存在使得这种贪心合法的方案。

接下来考虑必须经过首都的限制，将叶子按照贡献的从大到小排序，令$h_{x}$为$x$子树内叶子排名的最小值。

此时对于一个点$x$，若$h(x) \leq 2 k-1$，此时直接众心的方案合法。

否则我们要把一个叶子换成$x$子树内的叶子。

假设换掉了叶子$y$，

• 若$y$的顶端不是$x$的祖先，那么我们换掉它的代价就是$y$的贡献。

• 否则换掉它的代价就是$y$到$\mathrm{LCA}(x, y)$的距离。

对于第一种情况直接换掉贡献最小的叶子，对于第二种情况可以用倍增解决。

2024.9.25：

A：

考虑在方格表上二分。

第一轮，先间问整个方格表最中间的两行，末间问方格组成上下两部分，考察这两行的最小值$x$，如果这个最小值在两行中的上面一行，那么 1 的位置一定在上面部分，反之则在下面部分。

第二轮，不妨设 1 在上面部分，询问上面部分最中间的两个半列，目前可能出现 1 的末间问方格组成左右两部分。

还是考虑这两个半列的最小值$y$，不妨设$y$在两个半列中左边的半列。

如果$y<x$，那么 1 的位置在左面部分，反之则右， 1 的位置在与$x$相邻的那部分。

以此类准，每次可以把 1 的位置限定在全局间问过的方格的最小值的相邻部分，总询问次数为$2 \times\left(2 n+n+\frac{n}{2} \cdots\right)-2 n=6 n$，能拿55分，考虑继续优化 。

进一步发现，我们并不需要知道两行的最小值，只需要先询问一行的最小值，再在这个最小值上下找到比该最小值更小的一个值， 1 的位置也随之确定了，于是总询问次数降低到$n+\frac{n}{2}+\frac{n}{2}+\frac{n}{4} \cdots=3 n$，期望得分 100 。

B:

容易发现一个非常简单的$n=2 k+1$的构造，即任意选择$p_{1}$，并取$p_{i}+k=p_{i+1}(\bmod n)$，容易验证其正确性，并且其有重要性质$\left|p_{n}-p_{1}\right| \in\{k, k+1\}$。

将序列反转可以知道，可以任意选择满足$\left|p_{n}-p_{1}\right| \in\{k, k+1\}$并且在范围内的$p_{1}, p_{n}$，都有满足条件的构造。

如果在上述构造中取$p_{1}=0$，并且在序列最后加上$2 k+1$，我们得到了一个$n=2 k+2$的构造，但这个构造没有更好的性质。

设$2 k+1$的构造在$p_{1}=x, p_{n}=y$时为$A(x, y), 2 k+2$的构造为$B(x, y)$。

发现当$n$巨大的时侯，可以使用不超过$2 k+1$个$B$以及很多个$A$来拼接出$n$的均造，现在只需要满足其两段拼接处的条件，容易发现两个$A$之间的拼接由于$A$自由度高，比较容易，需要找出一种方案能将两个$B$连接在一起。

考虑如下构造，设当前的$B$为$B(a, a+2 k+1)$，可以构造$B(a, a+2 k+1)-A(a+3 k+1, a+4 k+1)-A(a+5 k+1, a+6 k+1)-\cdots-A\left(a+2 k^{2}-k+1, a+2 k^{2}+1\right)-B\left(a+2 k^{2}+k+1, a+2 k^{2}+3 k+2\right)$最后一个$A$对应的均造中最大数为$a+2 k^{2}+k$，可以拼接上。这里的所有构造值域均是相接的，可以计算脸证。

于是我们用$k-1$个$A$将相邻两个$B$连接了起来，多余的$A$可以简单排列在最后一个$B$之后。

通过计算知道这样的构造方法能勾造成功的$n$下界为$4 k^{3}+O\left(k^{2}\right)$，可以通过。

C：

考虑$\left(u, f a_{u}\right)$关于$[l, r]$好的条件，转化为$u$子树内有$[l, r]$之间的点且$u$并不是$l c a(l, l+1 \ldots r)$本身或其祖先，其中后面条件可以容压掉，只需要減去询问区间的所有子区间 lca 深度和即可。

现在计算单个区间权值軴化为两个问题：区间 lca 深度，有多少个子树内有该区间之间的点。

-区间 lca 深度。

即解决询问区间子区间 lca 深度和，考虑扫描右端点，维护所有左端点对应 lca 深度，并维护历史和。 修改一段左端点区间的对应 lca，实现区间加区间历史和，修改次数均摊线性。这一部分是$O(n \log n)$的。

-有多少个子树内有该区间之间的点

考察一个点$u$不计入$[l, r]$答穼的时候，将$u$子树内点按编号排序，那么这个$[l, r]$一定是介于两个编号排序后相邻的点之间的，可以抽象成知形加。

考虑树上启发式合并，对每个子树维护一个 set 或一棵平衡树之类，内部存子树内点的编号，每次把小子树的某点合并到大子树里的时候，将大子树对应平衡树中该点编号前驱后继取出，并将这个矩形加终止，换用新的两个矩形加。

问题变为$O(n \log n)$次矩形加，询问即为矩形查询，可以在$O\left(n \log ^{2} n\right)$的时间内得到解决。

2024.9.26：

A：

将所有区间按$l_{i}$从小到大排序，一个一个贪心加入，加入的时候有两种情况：

1. 之前的区间中存在未匹配的区间，且可以跟当前区间匹配。由于之后的区间的$l$都不会小于当前区间的$l$，我们陏便选择一个区间跟当前区间匹配即可。

2. 找不到可以跟当前区间匹配的末匹配的区间。我们在已经匹配的区间对$(i, j)$中找到$r_{j}$最小的一个区间对，如果$r_{j}$比当前区间的$r$小，我们可以交换这两个区间，让$i$跟当前区间匹配，把$j$变成未匹配区间。

容易发现这样贪心是最优的，用两个堆分别维护未匹配区间和已匹配区间即可，复杂度$O(n \log n)$。

B：

注意到如果区间$l, r$中有$>\log 10^{6}$个$a_{i}$满足$a_{i} \geq \frac{x}{2}$，这个区间的答案就是 0 ，因比我们只需要对$\log 10^{6}$个区间求出$\prod_{i=l}^{r} \frac{x-a_{i}}{x}$，这些区间中的$a_{i}$都满足$a_{i}<\frac{x}{2}$。

我们可以考虑如何求出$\sum_{i=l}^{r} \ln \left(\frac{x-a_{i}}{x}\right)$，最后$\exp$一下就可以得到结果，我们对前面的式子进行展开:

$$\begin{array}{c} \ln \left(\frac{x-a_{i}}{x}\right)=\ln \left(1-\frac{a_{i}}{x}\right) \\ =-\sum_{j>0}\left(\frac{a_{i}}{x}\right)^{j} \cdot \frac{1}{j} \end{array}$$

注意到$\frac{a_{i}}{x}<\frac{1}{2} ，\left(\frac{a_{i}}{x}\right)^{j}$很快就会变成 0 ，我们只要对前几个$j$计算这个式子即可，对每个$j$预处理$\frac{a_{i}}{j}$的前缀和即可，复杂度$O\left((n+q) \log 10^{6}\right)$。

C：

1. 先手选择长度为$1 / 2$的链，后手获得链上的格子，交换先后手。

2. 先手选择一条链/一个环，后手选择交换先后手/先后手不变，并获得相应的分数。

容易发现的性质是，先手选择的链/环一定是当前的链/环中长度最小的，因此我们可以设$d p_{i, j}$表示当前只剩下最大的$i$条链，$j$个环，此时先手得分減后手得分的最大值是多少，可以从$d p_{i+1, j}$和$d p_{i, j+1}$转移过来。

由于链的两端一定在边界处，最多只有$n+m$条链，复杂度$O(n m(n+m))$。

D：

我们可以把$i \oplus j \oplus x$拆成$\log$个区间，我们只需要对每个区间求出$\sum_{i=l}^{r} f(i)$即可。

$$\begin{array}{c} F_{0}(x)=1 \\ F_{k}(x)=\prod_{i=0}^{x}(2 i+1) \quad\left(\bmod 2^{k}\right) \end{array}$$

我们可以得到：

$$\begin{array}{l} F_{k+1}(x)=2 x \cdot F_{k}(x-1)+F_{k+1}(x-1) \\ F_{k+1}(x)-F_{k+1}(x-1)=2 x \cdot F_{k}(x-1) \end{array}$$

可以发现$F_{k}(x)$是一个关于$x$的$2 k-2$次多项式，那么我们要求的就是$\sum_{i=l}^{r} F_{32}(i)$，它是一个 63 次多项式，可以直接拉格朗日插值，在插值过程中需要注意将 2 的次幂提出来特殊处理，复杂度$O(63 \log n)$。

2024.9.27：

A：

考虑对于一个点权和$s(s \geq 3)$的连通块，先将其所有点权为 0 的叶子删去，则:

• 若存在点权为 2 的叶子，将其删去可得到点权和为$s-2$的连通块；

• 否则所有叶子点权为 1 ，删去两个叶子可得到点权和为$s-2$的连通块。

所以设$f_{i, 0 / 1}$表示$i$子树内包含$i$的连通块为奇数/偶数的最大点权和。

从下至上贪心，若$f_{i, k} \bmod 2 \geq k$则直接截取该连通块，之后就不考虑$i$子树了，时间复杂度$O(n)$。

B：

考虑折半搜索，枚举$k x+b$的高 15 位，那么可以得知其低 15 位模$k$的值和其下界，时间复杂度$O(T \sqrt{S})$。

C：

首先我们知道，存在四元环等价于存在两个点存在至少两个公共邻居。

枚举这个公共邻居的贡献直到找到四元环，就可以$O\left(n^{2}\right)$判四元环存在性了。

考虑修改边，把所有没有被修改的边拿出来判四元环。如果存在那么所有答案都是 Yes。否则可以预处理出任意两点的公共邻居数量。

时间复杂度$O\left(n^{2}+n q\right)$。

D：

来源：AtCoder World Tour Finals 2024 C

不会，直接贺官解。

我们不会加多余的燃料。所以如果移动的距离是$l$，那么答案就是$\max (l-2 C, 0)$。只需要考虑最小化移动距离。

那么到一个加油站之后必定会加满这种类型的燃料。设另一种燃料的剩余量为$x$。

考虑从一个加油站行驶到一个与其距离为$a$的加油站，显然有

• 如果两者燃料类型相同，$x \leftarrow x-\max (a-C, 0)$

• 如果两者燃料类型不同，$x \leftarrow \min (x+C-a, C)$

限制是始终有$x \geq 0$。

考虑一个 dp 表示到第$i$个加油站时$x=j$的最小折返总距离。可以发现只可能从$i$转移到$i+1$。

如果移动之后$x$不会增加那直接转移即可。否则我们可能会在这里刷$x$。具体来说，可以每次以$2 a$的代价增加$2(C-a)$的$x$。

考虑这个 dp 数组长什么样子，大概是，你考虑有用的位置，可以分成若干段，每一段里面的下标和值都是一个等差数列。下标的公差是某个$2(C-a)$，值的公差是某个$2 a$。而且越靠后$a$越大。

可以发现这里$a$比较小是严格比$a$比较大好的。所以进行一个$a$的转移的时候，会把后面的若干个等差数列弹掉，然后取出最后一个有用的位置（如果全部弹了就是原本的第一个）往后更新一个等差数列。

用个 deque 维护就是$O(n)$的，然而可能$x$超出了$C$得取$\min$了，那相当于从这个位置重新出发了。

从每个位置开始 dp一次即可，时间复杂度$O\left(n^{2}\right)$。

2024.9.29：

A：

容易发现，能力值最大的人一定能胜利。而其它人要胜利，就一定要打败最大值,于是想到最值分治。

考察当前序列最大值 (设位置为 mid）左边的一个数，它要胜利，一定要把最大值打败。

而我们发现，在打败最大值之前先把最大值左边的所有数全部打败，总是不劣的：要是打完前已经达到最大值了，那无论如何都可以。要是打完前达不到最大值，只能先打弱者增加能力值。

因此，对下标为$[1, m i d-1]$的人，他能赢的充要条件是: 能打完$[1 ，mid -1 ]$内的所有人，且能力值至少是$a_{m i d}-(m i d-1)$。

可以设计递归函数$\operatorname{Solve}(l, r, v)$，表示对于下标为$[l, r]$内的人，他能赢的充要条件是能打赢区间内的人，且下标至少为$v$，递归到$l=r$就得到了每个人能不能赢。

对序列建大根笛卡尔树，就可以将上述过程做到线性，最后加上区间$dp$即可。

B：

考虑容斥，钦定$k$个下㮏满足$a_{i}<a_{i+1}$，剩下的可以$\geq$也可以$<，$。

可以发现，这时相当于将序列分为了$n-k$段，每段内部都是严格递增的。

也就是说，如果确定了每段内部数的集合，就能唯一构造出一个排列。那考虑对每段内部的集合计数，考虑将每个数填入每一段里。

若$i$在序列中出现了$c n t_{i}$次，它填入$n-k$段的方案数就是$\binom{c n t_{i}}{n-k}$。

因此，我们要求的就是$\Pi\binom{c n t_{i}}{n-k} \ldots \ldots$. 吗?

上述填法有可能出现空段，为了避免空段，我们需要对算出的乘积再容斥一次。两次容斥都可以直接用卷积实现。

考虑如何计算乘积，注意到$c n t$至多只有$O(\sqrt{n})$种，对每种$c n t$可以$O(1)$算出组合数，然后用快速幕就可以算出该种$c n t$的答案。

C：

首先用线段树优化建图，对线段树上每个区间，维护区间内

• 矩阵上为 0 的位置的入树

• 矩阵上为 0 的位置的出树

• 矩阵上为 1 的位置的入树

• 矩阵上为 1 的位置的出树

用扫描线处理修改操作，打标记时就是交换 0，1 位置的对应树，上传信息时需要新建结点。

然后缩点，将所有点划分为强连通分量，并将强连通分量拓扑排序。

熟知的结论是，竞赛图的强连通分量排成一条链，而我们希望二分完全图的强连通分量最好也有类似的简单结构。

设强连通分量按正拓扑序排列，为$A_{1}, \ldots, A_{k}$。

经过分析，不难发现以下规律:

• 若$\left|A_{1}\right|=1$，设$P$为最大的$p$，使得$\left|A_{1}\right|=\left|A_{2}\right|=\cdots=\left|A_{p}\right|=1$，且$A_{1}, A_{2}, \ldots, A_{p}$全部在二分图的同一侧，则$A_{1}, A_{2}, \ldots, A_{P}$互不可达，且全部可达$A_{P+1}, \ldots, A_{k}$。

• 否则，$A_{1}$可达全部的$A_{2}, \ldots, A_{k}$。

直接分类讨论即可证明上述结论。

据此，缩点后可以$O(n+m)$求出每个点可达多少点。

2024.9.30：

A：

考场上想到区间dp了，但是没想到dp状态要加第三维。

假设 1 在$a$中的位置为$p$，在$b$中位置为$q$，由于 1 始终是堆中最后一个被取出的数，所以显然有$q \geq p$，并且取出 1 后堆一定是空的，也就是说$a$的前$q$个数和$b$的前$q$个数的集合应该是一样的。

此时我们可以递归下去，因为$[q+1, n]$和$[1, q]$（但去掉 1 ）这两个$a$中的段是独立的，再分别考虑其中的最小值即可。

据此可以区间 DP 。设$d p(l, r, v)$表示只考虑下标区间$[l, r]$中$\geq v$的数时的答案，那么$a n s=d p(1, n, 1)$，通过枚举最小值的位置来转移。