4 月 21 日

「CF1025D」Recovering BST

容易想到一个 $\mathcal{O}(n^4)$ 做法,即设 $dp_{i,j,k}$ 为 $[i,j]$ 内以 $k$ 为根是否合法,然后随便转移即可。

注意到我们实际上只需要知道 $[i+1,j]$ 能否为 $i$ 的右子树以及 $[i,j-1]$ 能否为 $j$ 的左子树。设 $L_{i,j}$ 表示 $[i,j-1]$ 能否为 $j$ 的左子树,$R_{i,j}$ 表示 $[i+1,j]$ 能否为 $i$ 的右子树,转移时枚举对应区间内的根即可。

「AGC010F」Tree Game

考虑一个菊花、一开始在中心的情况。显然先手只会往一个 $a_i$ 小的方向走才能胜利,因为双方会在这条边上反复横跳,然后后手先跳完。

考虑加上一层。假设一开始在 $u$,$v$ 子树先手必胜,则先手一定不会往 $v$ 走;假设一开始在 $u$,$v$ 子树先手必败,则先手可以往 $v$ 走,且后手一定回到 $u$,故当 $a_u<a_v$ 时先手胜利。

因此只需要枚举每个点为起点,然后做一遍树形 DP 即可:设 $dp_u$ 表示 $u$ 子树是否先手必胜,转移即判断是否存在满足 $a_v<a_u$ 且 $dp_v=0$ 的子树。

「CF938F」Erasing Substrings

注意到删除的顺序不影响答案,从而可以得到一个暴力做法:设 $dp_{i,S}$ 表示前 $i$ 位用掉的操作集合为 $S$ 的最小串。这样子是 $\mathcal{O}(n^3\log n)$ 的。

考虑一个贪心。显然我们每次选的一定是能选的最小的字符。因此我们只需要求出每个连续删除长度是否合法。

假设当前在算答案的第 $i$ 位,考虑求出 $dp_S$ 表示当前用掉 $S$ 中操作是否合法,则当前这一位的答案为 $s_{i+S}$ 中最小的,其中 $dp_S=1$。在算出当前位的答案后,那些不能到达这个答案的长度全部不合法,将它们的 $dp$ 值设为 $0$ 即可。

4 月 23 日

「AGC033D」Complexity

首先能够想到设 $dp_{i,j,k,l}$ 为左上角为 $(i,j)$、右下角为 $(k,l)$ 的矩阵的凌乱度,然而显然是过不去的。

注意到答案在 $\log nm$ 级别,因此可以考虑设 $dp_{i,j,k,l}$ 为凌乱度为 $i$ 时,上界为 $j$ 下界为 $k$ 左界为 $l$ 的矩阵右界最远能到哪。根据横切和竖切的情况不难得到转移

$$ dp_{i,j,k,l}=\max\left\{dp_{i-1,j,k,dp_{i-1,j,k,l}},\max_{t=j}^{k-1}\left\{\min\{dp_{i,j,t,l},dp_{i,t+1,k,l}\}\right\}\right\} $$

如果暴力转移总时间复杂度为 $\mathcal{O}(n^4\log n)$,仍然无法通过。

注意到当 $t$ 增大时 $dp_{i,j,t,l}$ 会减小,$dp_{i,t+1,k,l}$ 会增大,因此只要二分使得两者最接近的 $t$ 即可。总时间复杂度 $\mathcal{O}(n^3\log^2 n)$。

「CF500F」New Year Shopping

一个不要脑子的做法是线段树分治,即以时间为下标将所有物品与询问挂到线段树上,在线段树上递归时维护一个长度为 $4000$ 的 0/1 背包的 DP 数组即可。

标解给的是一个奇妙的分块做法,大概是分成 $p$ 块,从每个交界点往左右跑 0/1 背包,然后每个询问一定会包含一个交界点,直接将左右合并即可。

「CF724E」Goods transportation

容易想到一个网络流做法,即源点向每个点连容量为 $p_i$ 的边,每个点向汇点连容量为 $s_i$ 的边,每个点向编号比它大的点连容量为 $c$ 的边,然后求最大流即可。

发现最大流不好求,而图比较特殊,可以考虑 DP 求最小割。

设 $dp_{i,j}$ 表示前 $i$ 个点有 $j$ 个点和源点相连的最小割。转移这样考虑:如果 $i$ 与源点相连,则断掉连向汇点的边即可,代价为 $s_i$;如果 $i$ 与汇点相连,则断掉源点连来的边和前面与源点相连的边连来的边即可,代价为 $j\times c+p_i$。从而不难得到状态转移方程

$$ dp_{i,j}=\min\{dp_{i-1,j}+j\times c+p_i,dp_{i-1,j-1}+s_i\} $$

答案即为 $\min_{i=0}^n dp_{n,i}$。实现时需要滚动数组。

4 月 24 日

「AGC030D」Inversion Sum

设 $dp_{x,y}$ 表示 $a_x>a_y$ 的概率(假设每个操作发生的概率都为 $\frac{1}{2}$)。

对于每个操作 $(i,j)$,我们会让所有的 $dp_{i,k}$ 和 $dp_{j,k}$ 都变为 $\frac{1}{2}(dp_{i,k}+dp_{j,k})$,会让所有的 $dp_{k,i}$ 和 $dp_{k,j}$ 都变为 $\frac{1}{2}(dp_{k,i}+dp_{k,j})$。

最后统计逆序对的期望,再乘上 $2^Q$ 即为答案。

4 月 26 日

「SDOI2012」回家的路

考虑拆点,即将每个换乘站拆成横着走和竖着走,拆出来的两个点间连边权为 $1$ 的边。

然后将每一行、每一列的点拿出来排序,并依次连过去。

起点和终点可以看成换乘站(因为最短路一定不会在这两个点换乘)。

「CF995F」Cowmpany Cowmpensation

设 $dp_{i,j}$ 表示以 $i$ 为根的子树,$i$ 的权值为 $j$ 的方案数。容易得到转移

$$ dp_{i,j}=\prod_{v\in son_i}\sum_{k=1}^jdp_{v,k} $$

前缀和优化即可做到 $\mathcal{O}(D)$ 转移,总时间复杂度 $\mathcal{O}(nD)$。

考虑优化。可以发现,$dp_{1,x}$ 为关于 $x$ 的 $n$ 次多项式(可以理解为每个叶子节点都为一次式,往上合并时做乘法从而次数上升)。

那么我们只需要求出 $dp_{1,1..n}$ 然后拉格朗日插值即可。时间复杂度 $\mathcal{O}(n^2)$。

4 月 28 日

「CF940F」Machine Learning

考虑询问的最大值为多少。假设为 $k$,则序列中至少要有 $1+2+\cdots+k-1=\frac{k(k-1)}{2}$ 个数。因此答案是 $\mathcal{O}(\sqrt{n})$ 级别的。

因此可以带修莫队,只需要维护每个数的出现次数和每个出现次数的出现次数即可。移动时注意把 add 写在前面避免负下标问题。

「CF568E」Longest Increasing Subsequence

考虑普通 LIS 问题的解法,即设 $f_i$ 表示长度为 $i$ 的 LIS 的结尾的最小值,转移时二分即可。

考虑沿用到这道题中。设 $f_i$ 表示长度为 $i$ 的 LIS 的结尾的最小值,$g_i$ 表示长度为 $i$ 的 LIS 的结尾的最小值所在位置;再设 $l_i$ 表示以 $i$ 结尾的 LIS 长度,$p_i$ 表示以 $i$ 结尾的 LIS 上一项所在位置。

另外可以发现相同的数对答案没有影响,所以我们先忽略一个数不能用多次的条件。

为了方便,还可以在末尾加一个 $+\infty$。

考虑转移。分类讨论该数是不是 $-1$:

  • 如果该位置不是 $-1$,直接在 $f$ 中二分 $<a_i$ 的最大的值即可。
  • 如果该位置是 $-1$,可以枚举这个位置的值,则转化为不是 $-1$ 的情况。事实上这里并不需要二分,用一个指针即可。

考虑还原序列,可以从后往前递推。假设当前的位置为 $pos$,它的值为 $val$,对应的 LIS 长度为 $len$。

先考虑求前一个 $pos$ 仍然分类讨论该数是不是 $-1$:

  • 如果该数不是 $-1$,则前一个 $pos$ 为 $p_i$。
  • 如果该数是 $-1$,首先找是否存在 $a_j\neq -1,l_j=len-1,a_j<val$,如果存在即上一个位置为 $j$;如果不存在,则上一个位置为上一个 $-1$。

还需要考虑上一个 $pos$ 对应的数是 $-1$ 时求出上一个 $val$。显然它等于 $b$ 中最大的 $<val$ 的数。

然后对于不在 LIS 中的 $-1$,直接设为没有填过的 $b$ 中的数即可。

5 月 3 日

「十二省联考 2019」皮配

首先注意到学校选择导师和选择派系是等价的。

考虑 $k=0$ 的情况。则此时城市选择阵营与学校选择派系独立,可以分开处理。

设 $f_{i,j}$ 表示前 $i$ 个城市有 $j$ 个人在蓝阵营的方案数,$g_{i,j}$ 表示前 $i$ 所学校有 $j$ 个人在鸭派系的方案数。转移即为 0/1 背包。

统计答案时枚举第二维乘起来累加即可。

考虑 $k\neq 0$ 的情况。注意到有限制的学校数很少,可以单独拿出来处理。

设 $f_{i,j}$ 表示前 $i$ 个没有限制的城市有 $j$ 个人在蓝阵营的方案数,$g_{i,j}$ 表示前 $i$ 所没有限制的学校有 $j$ 个人在鸭派系的方案数。转移仍然为 0/1 背包。

设 $dp_{i,x,y}$ 表示前 $i$ 个有限制的学校有 $x$ 个人在蓝阵营 $y$ 个人在鸭派系的方案数。转移时可以先求出 $F_{x,y}$ 表示当前城市的人全部在蓝阵营且有 $y$ 人在鸭派系的方案数,$G_{x,y}$ 表示当前城市的人全部在红阵营且有 $y$ 人在鸭派系的方案数,然后合并即可。

最后统计答案时枚举有限制学校中选择蓝阵营的人数 $x$ 和选择鸭派系的人数 $y$,则可以计算出没有限制的学校中的人数范围,则将 $f$ 中对应的一段的和乘上 $g$ 中对应的一段的和再乘上 $dp_{?,x,y}$ 累加进答案即可。

实现时需要滚动数组。另外注意可能存在没有人的城市。

「JOISC 2020 Day1」建筑装饰 4

设 $dp_{i,0/1,0/1}$ 表示前 $i$ 位,第 $i$ 位选 A / B 时所有满足条件的方案中最多能有多少个 A / B。

转移分四种情况($a_{i-1}\leq a_i$、$a_{i-1}\leq b_i$、$b_{i-1}\leq a_i$、$b_{i-1}\leq b_i$)即可。

考虑从后往前构造方案。设 $sa$ 表示已选的 A 的数量,$sb$ 表示已选的 B 的数量,$pre$ 为前一个数,则当 $sa+dp_{i,0,0}\geq n$ 且 $sb_dp_{i,0,1}\geq n$ 且 $a_i\leq pre$ 时可以选 A。可以选 B 的情况类似。

5 月 4 日

「PA2013」Raper

设 $f(x)$ 为造恰好 $k$ 张光盘的最小花费。感性理解可以发现 $f(x)$ 是一个下凸壳。

考虑 WQS 二分。二分斜率 $m$,求切点相当于最小化 $y$ 轴上的截距,即求出最小的 $f(x)-mx$。

这个最小值的意义就是可以随意造光盘,且每造一张光盘可以赚 $m$ 元时的最小花费(显然它一定非负)。

考虑用堆解决这个问题。

维护一个小根堆,每次将 $a_i$ 插入到堆中,然后将当前的 $b_i$ 与堆顶匹配。然而当前的 $b_i$ 可能不优,所以要再往堆中插入 $-b_i$,这样子以后某个更优的 $b_j$ 如果选到了这个就代表将之前与 $b_i$ 匹配的 $a_k$ 与 $b_j$ 匹配,并舍弃 $b_i$。

$m$ 的话可以一开始将所有的 $b_i$ 都减去 $m$,显然求出来仍是正确的。

另外我们还需要求出最多能造的光盘数以便 check,所以这个过程中堆中的每个元素还要维护一下是 $a_i$ 还是后悔操作。

「ARC096D」Sweet Alchemy

考虑差分,则问题变为每次选择一棵子树,消耗 $\sum m_i$ 的材料,造出 $sz$ 个物品,且每棵不是原树的子树都只能选至多 $D$ 次。

令每棵子树的 $m_i$ 之和为其代价,$sz$ 为其收益,则相当于一个多重背包。

然而 $D$ 在 $10^9$ 级别,直接多重背包显然无法通过。

考虑一个错误的贪心:设 $w_i$ 为收益,$v_i$ 为代价,按 $\frac{w_i}{v_i}$ 排序并从大到小贪心选。

考虑什么时候这个贪心是对的。假设有两个物品 $i,j$ 满足 $\frac{w_i}{v_i}>\frac{w_j}{v_j}$,那么在收益相等(选了 $w_j$ 个 $i$,选了 $w_i$ 个 $j$)的情况下,选 $w_j$ 个 $i$ 显然会更优。从而在 $\frac{w_i}{v_i}$ 大的物品还能加的时候,$\frac{w_i}{v_i}$ 小的至多会选 $w_i-1$ 个。

所以我们只需要每种物品拿出 $\min\{n,D\}$ 个出来多重背包,剩下的部分贪心即可。

实现时求出 $dp_i$ 表示达到 $i$ 的代价最小需要的体积,然后枚举背包贡献的代价、剩下的贪心装满即可。多重背包部分可以二进制分组,也可以单调队列。

「CTS2019」 氪金手游

首先考虑原树为外向树的情况。此时 $u$ 子树中所有点选择时间都应比 $u$ 晚。

考虑这个概率。设 $u$ 子树 $w_i$ 的和为 $s$,整棵树 $w_i$ 的和为 $S$,则 $u$ 子树中所有点选择时间都比 $u$ 晚的概率为

$$ \frac{w_i}{S}\sum_{i=0}^{+\infty}\left(\frac{S-s}{S}\right)^i=\frac{w_i}{s} $$

这个概率只和子树有关,因此可以设 $dp_{i,j}$ 表示以 $i$ 为根的子树 $w_i$ 和为 $j$ 的概率,转移即为树形背包。

现在有内向边,可以考虑容斥,即对于每条内向边包含它的方案数等于忽略它的方案数减去它为正向边时的方案数。前者不难计算,后者套用上面的 DP 即可。

5 月 5 日

「CF985G」 Team Players

考虑容斥,则答案为含 $0$ 条边的贡献 $-$ 含 $1$ 条边的贡献 $+$ 含 $2$ 条边的贡献 $-$ 含三条边的贡献。

  • 含 $0$ 条边的贡献:枚举每个数和它的排名,然后求出对应的其它两个数的方案数即可。
  • 含 $1$ 条边的贡献:枚举一条边和第三个数的排名,然后求出第三个数的方案数即可。
  • 含 $2$ 条边的贡献:仍然枚举一条边和第三个数的排名,然后求出第三个数的方案数。这里第三个数的方案数可以通过将出边排序后二分得到。
  • 含 $3$ 条边的贡献:直接三元环计数即可。

需要注意计数方法避免算重。

5 月 6 日

「POI2012」衣帽间 Cloakroom

考虑将所有询问离线并按左端点从小到大排序。则 $a_i\leq m$ 的限制我们可以通过将物品按左端点排序并依次加入来解决。

考虑 DP。设 $dp_i$ 表示物品权值之和为 $i$ 时右端点最远能到哪。这样子对于每个询问我们只需要查询 $dp_k$ 是否大于 $m+s$ 即可。

转移类似于 0/1 背包。

5 月 7 日

「SNOI2017」遗失的答案

首先特判掉 $G\nmid L$ 的情况。

为了方便,将 $L$、$n$、$X$ 都除以 $G$。这样子问题转化为在 $[1,n]$ 中选若干个数,必须选 $X$,选出来的数 $\gcd$ 为 $1$、$\operatorname{lcm}$ 为 $L$ 的方案数。

我们先不管那个必须选 $X$ 的条件,想一想怎么做。

注意到值域只有 $10^8$,即最多只有 $8$ 个质因子,可以考虑状压 DP。

先考虑如何设状态。先将 $L$ 分解质因数,每个数对应的状态的前 $8$ 位表示该数中每个质因子的指数是否为 $0$,后 $8$ 位表示该数中每个质因子的指数是否和 $L$ 相同。

注意到可能会有一些数对应的状态相同。我们预处理出所有 $L$ 的 $[1,n]$ 内的约数,然后把状态相同的分在一组中。可以发现组数不会太大(大概在 $600$ 左右)。

这样子就可以 DP 了。设 $dp_{i,j}$ 表示前 $i$ 组状态为 $j$ 的方案数。转移考虑当前组选还是不选:如果选的话当前组有 $2^{cnt}-1$ 种方案,状态会或上该组的状态;不选则状态不会有变化。

现在考虑必须选 $X$ 的限制。可以先求出不包含 $X$ 所在的组的方案数,然后再将所有或上 $X$ 的状态为全集的那些位置加起来,再乘上 $X$ 所在组的方案数(因为 $X$ 必须选所以为 $2^{cnt-1}$)。

现在的问题是如何求出不包含 $X$ 所在的组的方案数。设 $f_{i,j}$ 表示前 $i$ 组状态为 $j$ 的方案数, $g_{i,j}$ 表示 $i$ 组之后所有组状态为 $j$ 的方案数,求法和上面的 DP 相同。设 $X$ 所在组为 $x$,则我们只需要合并 $f_{x-1}$ 和 $g_{x+1}$ 即可。可以发现合并的过程其实就是或卷积,于是 FWT 即可。

预处理出所有强制包含某个组的答案,最后询问时直接找到 $X$ 对应的组即可。

5 月 9 日

「清华集训 2017」小 Y 和恐怖的奴隶主

看到数据范围容易想到矩阵快速幂,因此可以考虑 DP。

设 $dp_{i,a,b,c}$ 表示前 $i$ 次攻击,场上有 $a$ 个一血、$b$ 个二血、$c$ 个三血的概率。转移稍微讨论一下即可。

为了求答案,再设一个 $f_i$ 表示前 $i$ 次攻击对 Boss 的期望伤害,从所有 $dp_{i,a,b,c}$ 由 $\frac{1}{a+b+c+1}$ 的概率转移过来。

因为 $k\leq 8$,所以实际可用的状态很小,算上 $f_i$ 只有 $166$ 个。于是就可以矩阵快速幂了。

但我们每个询问都矩阵快速幂时间复杂度为 $\mathcal{O}(T166^3\log n)$,显然会 T。设转移矩阵为 $M$,考虑预处理出 $M^{2^k}$,则每个询问只需要拿一个行向量乘上 $\log n$ 个矩阵即可,询问时间复杂度降为 $\mathcal{O}(T166^2\log n)$。

另外这题有一些卡常,可以在矩乘时用 __int128 作为中间变量,最后再取模来减少取模次数。

「CF708E」Student's Camp

显然营地不连通只能是上下分开,即存在相邻两行剩下的砖块区间没有交。

考虑 DP。设 $f_{i,j,k}$ 表示前 $i$ 行,第 $i$ 行剩下 $[j,k]$,且前 $i$ 行连通的概率。容易得到转移

$$ f_{i,j,k}=p_{j,k}\sum_{[j,k]\cap[l,r]\neq\varnothing}f_{i-1,l,r} $$

这里的 $p_{l,r}$ 表示某一行剩下 $[l,r]$ 的概率,显然等于左边少了 $l-1$ 块、右边少了 $m-r$ 块的概率。

设某一边少了 $i$ 块的概率为 $d_i$,则有

$$ \begin{aligned} d_i&={k\choose i}P^i(1-P)^{k-i}\\ p_{l,r}&=d_{l-1}d_{m-r} \end{aligned} $$

直接转移显然过不去。设

$$ \begin{aligned} fr_{i,r}&=\sum_{l\leq r}f_{i,l,r}\\ sr_{i,j}&=\sum_{l\leq r\leq j}f_{i,l,r}=\sum_{r\leq j}fr_{i,r}\\ fl_{i,l}&=\sum_{l\leq r}f_{i,l,r}\\ sl_{i,j}&=\sum_{j\leq l\leq r}f_{i,l,r}=\sum_{l\geq j}fl_{i,l} \end{aligned} $$

可以发现 $fr_{i,r}=fl_{i,m-r+1},sr_{i,r}=sl_{i,m-r+1}$,且最后答案就为 $sr_{n,m}$。

那么我们就可以通过容斥,用 $sr$ 来表示 $f$。

$$ \begin{aligned} f_{i,j,k}&=p_{j,k}\sum_{[j,k]\cap[l,r]\neq\varnothing}f_{i-1,l,r}\\ &=p_{j,k}(sr_{i-1,m}-sr_{i-1,j-1}-sl_{i-1,k+1})\\ &=p_{j,k}(sr_{i-1,m}-sr_{i-1,j-1}-sr_{i-1,m-k}) \end{aligned} $$

而 $sr$ 又可以通过 $fr$ 求出,所以只要考虑如何求 $fr$。

$$ \begin{aligned} fr_{i,r}&=\sum_{l\leq r}f_{i,l,r}\\ &=\sum_{l\leq r}p_{l,r}(sr_{i-1,m}-sr_{i-1,l-1}-sr_{i-1,m-r})\\ &=(sr_{i-1,m}-sr_{i-1,m-r})\sum_{l\leq r}p_{l,r}-\sum_{l\leq r}p_{l,r}sr_{i-1,l-1}\\ &=d_{m-r}\left[(sr_{i-1,m}-sr_{i-1,m-r})\sum_{l\leq r}d_{l-1}-\sum_{l\leq r}d_{l-1}sr_{i-1,l-1}\right] \end{aligned} $$

于是只要求出 $d_{l-1}$ 和 $d_{l-1}sr_{i-1,l-1}$ 的前缀和即可。第一个可以提前预处理出,第二个可以在 DP 时维护。

边界为 $f_{0,1,m}=1$ 即 $fr_{0,m}=sr_{0,m}=1$。

总时间复杂度为 $\mathcal{O}(nm)$。

「CF1286D」LCC

容易发现最早碰撞的一定是相邻的两个球。

我们钦定某一对球是最先撞上的以及它们的运动方向,然后考虑 DP。设 $dp_{i,0/1}$ 表示前 $i$ 个球,当前的球往左/往右,且保证最早撞上的是钦定的那一对的概率。转移讨论一下几种情况即可。

这个转移显然可以写成若干个 $2\times 2$ 的矩阵相乘。如果我们把所有方案按时间从小到大排序再枚举,则每次相当于修改了一个转移矩阵来使得时间比它小的碰撞不能发生。于是用线段树维护矩阵连乘即可。

5 月 11 日

「CF1284E」New Year and Castle Construction

考虑任意五个点对答案的贡献。显然有

  • 如果五个点的凸包为五边形,则贡献为 $0$;
  • 如果五个点的凸包为四边形,则贡献为 $1$;
  • 如果五个点的凸包为三角形,则贡献为 $2$。

我们只需要求出五个点凸包为为 $x$ 边形的方案数 $s_x$,然后答案即为 $s_4+2s_3$。

不知道怎么想到可以把答案拆成 $5(s_5+s_4+s_3)-(5s_5+4s_4+3_s3)$ 的形式,而又有 $s_5+s_4+s_3={n\choose 5}$,因此我们只需要计算 $5s_5+4s_4+3s_3$ 即可。这个东西的实际含义就是任意五个点的凸包所含的边数之和。

考虑枚举一条边并枚举它在多少个五个点的凸包中。我们先枚举一个点,然后把剩下的点极角排序并扫描(此时相当于枚举了一条边),则剩下 $3$ 个点都应在这条边左侧,每次找到范围后组合数算一下即可。

需要注意的是本题卡精度所以极角排序不能用 atan2,可以用叉积判断。

5 月 12 日

「CF1285F」Classical?

下文中的 $A$ 为 $\max_{i=1}^n\{a_i\}$。

考虑枚举答案的 $\gcd$,问题变为求满足 $\gcd(x,y)=g$ 的 $x,y$ 中 $x\times y$ 的最大值。

可以考虑贪心。我们先把所有满足为 $g$ 的倍数的数拿出来并从大到小排序,然后依次扫描,同时开一个栈来维护。对于每个数,我们需要判断栈中有没有与它互质的数,假设有 $s$ 个,则我们一直弹栈,直到弹出 $s$ 个与它互质的数,并在弹栈过程中更新答案即可。

一个关于正确性的感性理解:因为之后加进来的都比当前的小,弹出去的都比当前更新答案的小,所以弹出去的所有数不会影响答案。

现在的问题就是如何求栈中和某个数互质的数的个数。设栈中有 $c_i$ 个 $i$,则栈中与 $x$ 互质的数的个数为

$$ \sum_{i=1}^{A}c_i[\gcd(i,x)=1] $$

莫比乌斯反演得到

$$ \sum_{d|x}\mu(d)\sum_{d|i,i\leq A}c_i $$

于是我们只需要入栈、出栈时维护每个数有多少个倍数在栈中即可。

总时间复杂度大概是 $\mathcal{O}(A\log^2 A)$。

5 月 13 日

「JLOI2016」成绩比较

考虑容斥,求出至少 $i$ 个人被 D 神碾压的方案数 $f_i$。

首先钦定 $i$ 个人被 D 神碾压,然后对于每一科选出没有被 D 神碾压但是这一科分数比他低的 $n-r_i-i$ 个人,然后再枚举 D 神的分数并计算出其它人分数的方案数,即可求出 $f_i$,即

$$ f_i={n\choose i}\prod_{i=1}^m{n-i-1\choose n-r_i-i}\sum_{j=1}^{u_i}j^{n-r_i}(u_i-j)^{r_i-1} $$

直接计算显然复杂度爆炸。考虑先对于每个 $i$ 求出 $\sum$ 后式子的值 $s_i$

$$ \begin{aligned} s_i&=\sum_{j=1}^{u_i}j^{n-r_i}(u_i-j)^{r_i-1}\\ &=\sum_{j=1}^{u_i}j^{n-r_i}\sum_{l=0}^{r_i-1}{r_i-1\choose l}{u_i}^{r_i-1-l}(-j)^{l}\\ &=\sum_{l=0}^{r_i-1}(-1)^l{r_i-1\choose l}{u_i}^{r_i-1-l}\sum_{j=1}^{u_i}j^{n-r_i+l} \end{aligned} $$

最后的 $\sum$ 为自然数幂和的形式,因此可以拉格朗日插值。

最后根据容斥定理不难得到答案

$$ \sum_{i=k}^{n-1}(-1)^{i-k}{i\choose k}f_i $$

总时间复杂度为 $\mathcal{O}(n^2m)$。

5 月 14 日

「JOISC 2016 Day 1」俄罗斯套娃

我们把每个套娃看做一个点 $(R_i,H_i)$,把套在一起的若干个套娃看做一条链,把每条链 $H$ 最大的那个套娃称作这条链的头。

这样子问题就变为,每个点可以向右上方某一个点连边,求最小链数。

先考虑只有一组询问的情况。

我们把所有物品按 $H$ 从小到大排序,然后依次加入。对于每个物品,显然选择能选择的最右的链头连上最优。于是我们只需要找到左边第一个链头即可。

考虑处理询问。可以将链头的权值设为 $1$,其它点权值设为 $0$,容易发现此时答案即为满足条件的点的权值和。将询问离线按 $H$ 的限制排序,用一个支持单点修改、区间求和、查询左边第一个权值不为 $0$ 的点的数据结构维护即可。

实现时可以把 $R$ 作为第二关键字从大到小排序来避免 $H$ 相同的点间的影响。

5 月 16 日

「雅礼集训 2018 Day1」树

设 $dp_{i,j}$ 表示 $1\sim i$ 构成的树高度为 $j$ 的方案数。

显然树上一定存在 $(1,2)$ 这条边,因此我们转移时讨论以 $2$ 为根的子树(记做 $A$)和整棵树其它部分(记做 $B$,显然它也是一棵树)的高度关系。

转移讨论一下整棵树最深的节点在哪里即可

$$ dp_{i,j}=\left(\sum_{k=1}^{i-2}\sum_{l=1}^{\min\{j-2,k\}}{i-2\choose k-1}dp_{k,l}dp_{i-k,j}\right)+\left(\sum_{k=1}^{i-1}\sum_{l=1}^{\min\{i-k,j\}}dp_{k,j-1}dp_{i-k,l}\right) $$

边界为 $dp_{1,1}=dp_{1,2}=1$。

「CTS2019」随机立方体

为了方便,设 $n<m<l$,$V=nml$。

考虑容斥,求出至少有 $i$ 个极大数的方案数 $c_i$。

那么 $c_i$ 等于选出 $i$ 个极大数的方案数、$i$ 个极大数所在的平面的并填数的方案数、其它位置填数的方案数之积。

首先考虑求选出 $i$ 个数的方案数 $f_i$,不难得到

$$ f_i=\prod_{j=0}^{i-1}(n-j)(m-j)(l-j) $$

在求接下来两个方案数之前,先考虑算 $i$ 个极大数所在平面的并的方块数 $g_i$,显然有

$$ g_i=V-(n-i)(m-i)(l-i) $$

现在考虑求 $i$ 个极大数所在平面的并的填数的方案数 $h_i$。显然每个数需要满足小于控制它的极大数中最小的那个,我们称这个极大数实际控制这个数。将所有极大数从大到小考虑,则最大的那个极大数实际控制 $g_i-g_{i-1}-1$ 个数(不包括自己),且有 $g_i-1$ 个数可以填,则方案数为 $A_{g_i-1}^{g_i-g_{i-1}-1}=\frac{(g_i-1)!}{g_{i-1}!}$,且填完后变为子问题 $h_{i-1}$。所以

$$ h_i=\prod_{j=1}^{i}\frac{(g_j-1)!}{g_{j-1}!} $$

其他位置填数的方案数就很好算了,为 $(V-g_i)!$。

注意上面漏算了需要乘上选出 $g_i$ 个数的方案数。所以有

$$ \begin{aligned} c_i&={V\choose g_i}f_ih_i(V-g_i)!\\ &=\frac{V!}{g_i!(V-g_i)!}f_i\prod_{j=1}^i\frac{(g_j-1)!}{g_{j-1}!}(V-g_i)!\\ &=V!f_i\prod_{j=1}^i(g_j-1)!\prod_{j=0}^{i}\frac{1}{g_j!}\\ &=V!f_i\prod_{j=1}^i\frac{1}{g_j} \end{aligned} $$

我们实际上要算的是至少有 $i$ 个极大的数的概率 $d_i$,直接除以 $V!$ 即可

$$ p_i=f_i\prod_{j=1}^i\frac{1}{g_j} $$

线性求逆元即可 $\mathcal{O}(n)$ 求出所有 $p_i$。

最后再考虑求答案。因为有

$$ p_i=\sum_{j=i}^n{j\choose i}ans_j $$

二项式反演得到

$$ ans_k=\sum_{i=k}^n(-1)^{i-k}{i\choose k}p_i $$

总时间复杂度 $\mathcal{O}(n)$。

5 月 19 日

「LibreOJ NOI Round #2」不等关系

假设 > 是没有限制的,那么整个序列被 < 划分为若干段。设这些段的长度为 $a_1,a_2,\cdots$,则方案数为

$$ \frac{n!}{a_1!a_2!\cdots} $$

> 的限制时可以考虑容斥。设 $dp_i$ 表示前 $i$ 个数的合法序列数,容易得到

$$ dp_i=\sum_{j=0}^{i-1}(-1)^{cnt_{i-1}-cnt_j}{i\choose j}dp_j $$

进而有

$$ \frac{dp_i}{i!}=\sum_{j=0}^{i-1}(-1)^{cnt_{i-1}-cnt_j}\frac{dp_j}{j!}\frac{1}{(i-j)!} $$

边界为 $dp_0=0$。将 $(-1)^{cnt_{i-1}}$ 提出后分治 NTT 即可。

5 月 26 日

「CF671C」Ultimate Weirdness of an Array

考虑求出一个 $H_i$ 表示有多少个 $[l,r]$ 满足 $f(l,r)\leq i$,则答案为

$$ \sum_{i=1}^{\max\{a\}}i\times(H_i-H_{i-1}) $$

考虑如何求 $H_i$。设 $nxt_l$ 表示最小的满足 $l\leq r,f(l,r)\leq i$ 的 $r$(若不存在则为 $n+1$)。则将 $l$ 作为左端点时右端点不能在 $nxt_l$ 左边,故有

$$ H_i=\sum_{i=1}^nn-nxt_i+1 $$

考虑快速求 $nxt_i$。考虑从大到小枚举 $i$,在 $i$ 减小时考虑 $nxt$ 的变化。

假设满足 $i|a_j$ 的 $j$ 为 $x_1,x_2,\cdots,x_m$,则 $[l,r]$ 外至多有这些数中的一个。因此 $nxt_{x_2+1..n}$ 会变成 $n+1$,$nxt_{x_1+1..x_2}$ 会与 $x_m$ 取 $\max$,$nxt_{1..x_1}$ 会与 $x_{m-1}$ 取 $\max$。

于是我们只需要写一个支持区间取 $\max$、区间求和的数据结构即可。可以用线段树实现,维护区间最大值、最小值、和,当最小值大于等于修改值时直接返回,当最大值小于修改值时直接区间赋值,否则向下递归。由于 $nxt$ 是不降的所以复杂度大概是对的。

5 月 27 日

「JOISC 2020 Day2」有趣的 Joitter 交友

如果 $x$ 关注了 $y$,则从 $x$ 向 $y$ 连一条边。这样子会得到若干个强连通分量。

考虑某一个强连通分量。假设它的大小为 $s$,且有 $k$ 条入边,则它对答案的贡献为 $s(s-1)+sk$。

考虑维护强连通分量。用并查集维护连通关系,用 std::set 维护入边。

假设现在要加入一条边 $x\to y$,讨论一下

  • 如果 $x,y$ 在一个强连通分量中,什么都不做。
  • 如果已经存在 $y$ 所在强联通分量中一点连向 $x$ 所在强连通分量中一点的边,将 $x,y$ 所在的强连通分量合并。
  • 否则,更新 $y$ 所在强连通分量的入边。

我们需要判断是否存在 $y$ 所在强连通分量中一点连向 $x$ 所在强连通分量中一点的边。再开两个 std::set 维护所有强连通分量连入、连出的强连通分量即可。

合并强连通分量时可以启发式合并。需要注意的是合并后可能产生新的能合并的强连通分量,用一个队列存一下即可。

具体维护有亿点点复杂。

「CF1270H」Number of Components

可以发现一个性质,即连通块一定是连续的一段。证明可以设 $i<k<j$,然后讨论各种情况,并证明无论如何 $k$ 与 $i,j$ 都连通。证起来有些复杂所以此处略去(

那么我们可以枚举连通块的最右边的点 $p$,如果 $[1,p]$ 与 $[p+1,n]$ 间没有连边即 $\min_{1\leq i\leq p}a_i>\max_{p+1\leq i\leq n}a_i$ 则 $p$ 满足条件。

考虑枚举 $\max_{p+1\leq i\leq n}$,设为 $w$。将序列中 $>w$ 的数设为 $1$,$\leq w$ 的数设为 $0$,则 $p$ 满足条件当且仅当这个 $0/1$ 序列形式如同

$$ \underbrace{11\cdots 11}_{p\text{个}1}00\cdots 00 $$

因而没有必要枚举 $p$,只需要枚举 $w$ 即可,因为确定一个满足条件的 $w$ 时 $p$ 的值可以唯一确定。

所以我们只需要统计有多少个 $w$ 对应的 $0/1$ 序列是这个形式即可。

为了方便,设 $a_{0}=+\infty,a_{n+1}=0$,此时一个 $0/1$ 序列是这个形式当且仅当只有一对相邻的 $0$、$1$。于是我们对于每个 $w$ 计算相邻的 $0$、$1$ 对数即可。

考虑用线段树解决这个问题。对于相邻的两个数 $a_i,a_{i+1}$,当 $w\in[\min\{a_i,a_{i+1}\},\max\{a_i,a_{i+1}\})$ 时这两个数会构成一对 $0$、$1$,在线段树上将这个区间加 $1$ 即可。统计答案时我们需要算有多少个位置的值是 $1$,难以维护;注意到一定有一对 $0$、$1$(因为 $a_0=+\infty,a_{n+1}=0$),所以我们只要维护最小值个数即可。另外注意统计答案时不能将不在序列中的数算进去。

「JOISC 2020 Day4」治疗计划

考虑两个方案 $[L_i,R_i]$ 和 $[L_j,R_j]$ 先后执行后能否合并为一个健康人区间。显然应该满足

$$ R_i-L_j+1\geq |T_i-T_j| $$

因此我们可以以任意顺序加入方案,最后合并成 $[1,n]$ 即可。

所以可以从左往右考虑。考虑最短路,将所有 $L_i=1$ 的点作为源点,如果 $i,j$ 能合并则从 $i$ 向 $j$ 连边 $c_j$。

然而需要优化。把绝对值拆开:

  • 如果 $T_i\geq T_j$,则 $R_i-L_j+1\geq T_i-T_j$ 即 $R_i-T_i+1\geq L_j-T_j$。
  • 如果 $T_i\leq T_j$,则 $R_i-L_j+1\geq T_j-T_i$ 即 $R_i+T_i+1\geq L_j+T_j$。

把所有方案按 $T_i$ 从小到大排序,并开两棵线段树分别维护 $L_i-T_i$ 和 $L_i+T_i$,每次在第一棵线段树上找左边满足条件的点、在第二棵线段树上找右边满足条件的点转移即可。

因为每个点的入边的权值都相同,所以每个点只会被 $dis$ 最小的那个点更新,即线段树上每个叶节点只会被访问一次,所以复杂度是对的。

5 月 28 日

「CF603E」Pastoral Oddities

首先有一个结论:一个大小为偶数的连通块一定存在一个合法的边集,一个大小为奇数的连通块一定不存在一个合法的边集。

证明:

  • 如果连通块大小为奇数,又因为每个点度数都为奇数,所以总度数为奇数,这是不可能的。
  • 如果连通块大小为偶数,此时我们可以先找到一棵生成树,从下往上构造即可。可以发现一定能构造出解。

于是我们只需要保证图中没有大小为奇数的连通块即可。

考虑一个类似 Kruskal 的思路,即按边权从小到大加入所有边,直到满足条件。

于是我们可以用 LCT 维护生成森林,用堆维护所有生成森林中的边。加入一条边时,首先替换掉路径上最大边,然后每次从堆中弹出一条边权最大的边并删除,直到删除这条边后不满足条件,这条边就是答案。

具体还要求每个连通块大小,用维护子树信息那套维护一下虚子树大小即可。

「NOI2019」序列

至少有 $L$ 个下标相同 $\Longleftrightarrow$ 至多有 $K-L$ 个下标不同。

考虑一个费用流模型,即从源点向 $a$ 中所有点连容量为 $1$、费用为 $a_i$ 的边,从 $b$ 中所有点向汇点连容量为 $1$、费用为 $b_i$ 的边,从 $a_i$ 向 $b_i$ 连容量为 $1$、费用为 $0$ 的边,再新建两个点 $C,D$,从 $C$ 向 $D$ 连容量为 $K-L$、费用为 $0$ 的边,从 $a$ 中所有点向 $C$ 连边,从 $D$ 向 $b$ 中所有点连边。这样子求流量为 $K$ 时的最大费用即为答案。

考虑模拟费用流。显然我们会优先流 $C\to D$,因为此时可能的收益最大。当 $C\to D$ 这条边满流时我们有如下选择:

  • 选一个 $a_i+b_i$。
  • 选一个 $b_i$ 已经匹配了的 $a_i$ 和 $b_j$ 匹配。
  • 选一个 $a_i$ 已经匹配了的 $b_i$ 和 $a_j$ 匹配。

于是我们开五个堆,分别维护未匹配的 $a_i$ 的最大值、未匹配的 $b_i$ 的最大值、未匹配的 $a_i+b_i$ 的最大值、$b_i$ 已经匹配了的 $a_i$ 的最大值、$a_i$ 已经匹配了的 $b_i$ 的最大值,每次三种情况比较一下即可。

实现时需要维护 $C\to D$ 弧的残量已经每个 $a_i$、$b_i$ 是否已经匹配,写起来需要注意各种不会减少(甚至可能增加) $C\to D$ 弧残量的情况。

「JOISC 2020 Day4」首都城市

考虑建一个图,即如果某两个颜色为 $i$ 的点的路径上存在一个颜色为 $j$ 点,则从 $i$ 向 $j$ 连一条边。

那么一条边 $(u,v)$ 的实际意义是要想把颜色为 $u$ 的点连通,则必须把 $u,v$ 合并。

考虑一个强连通分量,显然其中任意一种颜色想要连通都只能将其它 $sz-1$ 个颜色合并,因此一个强连通分量需要合并 $sz-1$ 次。

于是我们缩点并将 $sz-1$ 作为点权,问题变为求从某个点出发到一个出度为 $0$ 的点的最短路(实际意义就是一路合并直到连通),于是我们只需要枚举出度为 $0$ 的那些强连通分量更新答案即可。

接下来考虑建图的问题。枚举颜色 $i$,并求出所有颜色为 $i$ 的点的 LCA,直接从 $i$ 向每个颜色为 $i$ 的点到 LCA 路径上的颜色连边即可。

这样子还是不好做。可以将每个点向对应的颜色连边,然后就只需要从 $i$ 向路径上所有点连边了。容易发现这样子不会影响答案。于是直接树剖+线段树优化连边即可。

5 月 29 日

「CF639E」Bear and Paradox

首先考虑怎么放最优。考虑邻项交换法

$$ a_i\left(1-\frac{c(t+t_i)}{T}\right)+a_j\left(1-\frac{c(t+t_i+t_j)}{T}\right)>a_j\left(1-\frac{c(t+t_j)}{T}\right)+a_i\left(1-\frac{c(t+t_i+t_j)}{T}\right) $$

化简得到

$$ a_it_j>a_jt_i $$

于是按照 $\frac{a_i}{t_i}$ 从大到小排序即可。

一个想法是二分答案,check 时按 $a_i$ 排序然后看 $a_i\left(1-\frac{cx}{T}\right)$ 是否满足条件。但很容易发现这个是假的,因为 $\frac{a_i}{t_i}$ 相同的题目无法确定顺序,从而无法确定完成时间。于是我们记一下可能的完成时间的最大值和最小值,并在 check 时拿 $a_i\left(1-\frac{cx}{T}\right)$ 的最小值去和前面的最大值比较即可。

「十二省联考 2019」字符串问题

容易想到一个图论模型,即从每个 A 类串向它所支配的 B 类串连边,从每个 B 类串向以它为前缀的 A 类串连边,并将所有 A 类串的权值设为长度。这样问题变为求最长路,如果有环输出 -1

第一类边可以直接连,但第二类边暴力连复杂度爆炸,考虑一些优化。

对反串建 SAM,此时 Parent 树上每个点的祖先都是它的前缀,于是我们只需要将树上每个 B 类串对应的节点向子树中所有 A 类串对应的节点连边。找某个子串在 SAM 上的点可以记一下每个后缀对应的点然后在 Parent 树上倍增。

进一步,我们可以在 Parent 树上从上往下连边,由 Parent 树上的节点连向 B 类串,再从 B 类串连向 Parent 树上的子节点和子节点包含的 A 类串。

然而这样子有一个问题,就是 SAM 上每个节点可能包含了多个 A 类串、B 类串。于是我们把每个节点对应的串按长度排序,如果长度相同则把 B 类串放在前面,然后依次扫过去,并记一个 $t$ 为之前扫到过的长度最大的 B 类串(没有扫到 B 类串时则为 SAM 上的节点),从 $t$ 向当前扫到的节点连边即可。连出来大概是一个这样的东西

X → A1,A2
↓
B1
↓
B2 → A3

然后最后的 $t$ 向 Parent 树上的子节点连边即可。

5 月 30 日

「CF1063F」String Journey

为了方便,把串翻转,条件改为「使 $t_{i-1}$ 是 $t_i$ 的真子串」。

可以发现一个性质,即在一定存在一组最优解使得 $|t_i|=i$,因为某个不满足的串删去多的部分一定不会差。

于是可以考虑一个 DP。设 $dp_i$ 表示最后一个串以 $i$ 结尾时最多能选出多少个串。

然而这个似乎没法转移。冷静分析一下可以发现一定有 $dp_{i-1}\geq dp_i-1$(考虑一个最后一个串以 $i$ 结尾且包含 $dp_i$ 个串的方案,将方案中所有串删去最后一个字符后显然仍然合法,且此时构成一组最后一个串以 $i-1$ 结尾且包含 $dp_i-1$ 个串的方案)。于是我们可以从 $dp_{i-1}+1$ 往下枚举 $dp_i$ 并判断是否合法。可以发现总 check 次数是 $\mathcal{O}(n)$ 的。

考虑如何 check $dp_i=x$ 是否合法。我们相当于要判断 $s_{1..i-x}$ 的所有子串中是否有一个长度为 $x-1$ 的、满足是 $s_{i-x+1,i}$ 的子串且其结尾的 $dp$ 值 $\geq x-1$。

前面那个条件不好处理,可以转化为存在一个 $p\leq i-x$,满足前缀 $p$ 与前缀 $i$ 或前缀 $i-1$ 的最长公共后缀长度 $\geq x-1$。

注意到在整个过程中 $i-x$ 是不降的,因此我们可以用一个指针维护可能的范围;最长公共后缀的条件可以建出 SAM,在 Parent 树上找到前缀 $i$ 和前缀 $i-1$ 对应的点向上倍增找到最小的 $len_u\geq x-1$,则子树 $u$ 中所有点都满足该条件;$dp$ 值的条件可以直接查询子树中范围内的最大的 $dp$ 值并判断,DFS 序+线段树即可。

5 月 31 日

「JOISC 2020 Day3」星座 3

考虑一个贪心。从下往上扫,同时每个位置维护一下它下方保留了的不能与它共存的权值和,对于每颗星星留一个权值大的即可。

考虑每颗星星上方不能与它共存的星星的范围,显然是往左、往右走到第一栋比它高的大楼的范围。

用并查集维护每个点往左、往右最远能走到哪里,然后区间加一下就好了。

「APIO2014」回文串

PAM 板子题。建出回文树后每个节点的子树大小即为出现次数,然后取个 $\max$ 即可。

「SHOI2011」双倍回文

考虑建 PAM,对每个节点额外求出一个 $trans_u$ 表示长度 $\leq$ 当前节点长度一半的最长回文后缀。

这个直接从 $trans_{fa}$ 往上跳 $fail$ 直到跳到一个能扩展新加的字符且扩展后长度小于新节点一半的节点即可。

那么我们只需要判断 $len_{trans_u}$ 是否为偶数且 $len_u$ 是否等于 $len_{trans_u}$ 即可判断 $u$ 是不是一个双倍回文串。

「AGC006F」Blackout

考虑对于每个黑格子 $(x,y)$,从 $x$ 向 $y$ 连一条边,则问题变成如果存在 $x\to y\to z$ 则连边 $z\to x$,求最终边数。

显然可以对于每个连通块分开考虑。考虑对于每个连通块三染色,那么会有三种情况

  • 失败,则此时一定有一个长度 $\geq 4$ 的环,从而整个连通块变成完全图,此时答案为 $sz^2$。
  • 成功但没有用上 $3$ 种颜色,则此时不会产生任何新边,答案即为连通块内边数。
  • 成功且用上了 $3$ 种颜色,则三种颜色会循环有连边,答案为 $cnt_0cnt_1+cnt_1cnt_2+cnt_2cnt_0$,其中 $cnt_i$ 为颜色为 $i$ 的点数。

下篇

最后修改:2020 年 06 月 03 日 02 : 50 PM