2024.09 做题记录seo优化

2024.09 做题记录

news/2024/10/1 17:17:40

20240901 上午模拟赛

能想出来 T2，但是怎么没想出来呢。

T2：及时去想 $2^{k/2}$ 的做法，猜到是 DP 套 DP，但是没有进一步思考内层状态是 $O(2^{k/2}k)$ 的。

T3：没调完/fn/fn

T4：赛时会了 $f_{i,j}$ 表示 $B(i,j)$ 是否可行，但是么有去想进一步的单调性优化，$f_{i}$ 可以表示最大的 $j$，这其实是值域定义域互换的套路。给转移强制钦定顺序会好很多。

20240901 下午模拟赛

前三题都是普及题。

T4：60 分的暴力很好想，但是要坚信没有别的做法，直接维护。没想出来是因为没有抓好连通块深度最浅的放在一起统计以及如果只维护父子关系确实只影响 $12$ 个点，场上在想 $k-$邻域直接似了。

树上问题不到迫不得已不要考虑祖先往儿子走或者神秘邻域，换根是好东西。

还有这个就是必须平衡修改与查询的复杂度。

背包是可以删的。在此基础上可以实现换根。

20240903

一棵树的完美匹配唯一

ARC183D

考虑完美匹配事实上是很强的限制，并且两个叶子节点对应的都是完美匹配边，那么从这条路径的叶子节点开始递推，只能是这个路径的【这条边是否在完美匹配路径之上的状态】全部异或 $1$。并且，这条路径一定是 $01$ 交替的，使用 dfs 序构造是正确的。

20240904

正睿有俩题在中午一眼秒了来着。

ARC179D

显然按照某种 dfs 序。考虑在定根时有 $f_u$ 表示：$u$ 子树内遍历完的最小步数，且必须在 $u$ 结束。但是注意掉结束可以不在 $u$ 本身，可以在某个子树内的叶子上，还要设一个 $g_u$ 表示不强制在 $u$。$f_u=\sum \min(f_v+2,2\text{siz}_u-\text{maxdep}_v-1)$，而 $g_u$ 可以选择一个儿子不出来，细节变为 $g_v+1$。换根 dp 大概需要维护最大和次大。

复习到换根 dp 了：

从 $u$ 推到 $v$ 时，假设新的根是 $v$
去除 $v$ 在 $u$ 作为儿子
把 $u$ 当成 $v$ 的儿子对 $v$ 进行转移，可以在 dfs 进去再做，但是需要求好参数
恢复 $v$ 在 $u$ 中成为儿子

ARC179E

首先可以对于固定的 $l$ 二分最大的 $r$ 使得 $[l,r]$ 合法。考虑判定合法，固定左端点类似水镜可以设计 DP 为：$f_{i,0/1}$，第 $i$ 个矩形为横着放 / 竖着放是否合法。

转移有 $4$ 种情况，发现 $0\to 1,1\to 0$ 的情况是不平凡的，可以用面积之和来判定，那么对于某个点我们发现有且仅有一个 $l$ 使得这个转移合法。对于所有点可以二分求出 $l$，然后将这个问题视为图论可达性问题：有 $2\times n$ 的点，分别代表 $f_{i,0},f_{i,1}$，每次枚举固定的那个 $l$ 时临时加入所有合法的 $1\to 0,0\to 1$ 转移，DDP 维护查询 $l$ 是否可以到达 $r$ 即可。

ARC180E

我测，真不会啊。

注意到答案具有单调性，考虑反过来求，求代价为 $k$ 时最长的 LIS 长度。

先求代价为 $0$ 的问题，$f_{i,j}$ 为前 $i$ 个数 LIS 结尾者相对排名为 $j$ 的最长 LIS 长度。

$j\in[1,i-a_i]$ 时可以考虑让 $i$ 加入 LIS。事实上发现，LIS 最优一定都是值域上一段前缀。
$f_{i-1,j-1}\to f_{i,j}$ 代表让排名高于 $i$ 排名的都 $+1$。

可以简化为 $f_{i,j}=f_{i-1,j-1}+[j\leq i-a_i]$。

容易发现 $f_{n,x}=\sum_{i=1}^x[x\leq n-a_{n-i+1}]$。

考虑代价 $>0$ 时，有一个代价可以免费让一个位置 $+1$，最终影响就是对于 $j\in[n-a_i+1,n]$ 的 $f_{n,j}$ 都加上 $1$。

贪心即可。

更优美的做法是观察到：LIS 必然为值域上的连续段 $[l,r]$，并且序列形如：$[n,n-1,n-2,\cdots,r+1],[l,l+1,\cdots,r-1,r],[l-1,l-2,l-3,\cdots,2,1]$。

发现产生代价的也只有 LIS 的部分。看成一次函数即可。

20240905

P3248

考虑缩点，将一个版本的树视为一个大点，因此需要先求出两个点在缩点树后的 LCA。跳到同一个大点即可。问题在于一个大点中不好查询原编号，直接维护是通过 dfs 序的，所以需要主席树维护。

https://qoj.ac/contest/1244 口胡记录

QOJ6501

考虑每一个边都形如 $x$ 为 $y$ 在 $T_1$ 的父亲或 $y$ 为 $x$ 的在 $T_2$ 父亲，每个点被一条边选择，每个连通块必须是基环树森林即 $|V|=|E|$，有解时答案为 $2^{cnt}$。

QOJ6502

不会。

QOJ6503

注意到 DFS 序的最终节点必然为叶子节点。因此我们可以确定新树 dfs 序的最后节点必然为叶子节点。并且 DFS 序列中第二个节点必然与 $x$ 直接相邻，所以可以求出叶子节点的所有相邻点，可以不停删叶子节点暴力模拟即可。

QOJ6504

笑点解析，随机矩阵没见过。随机三个可逆矩阵 $M_0,M_1,M_2$，注意到两个消掉的位置一定奇偶性不同，若 $i\bmod 2>0$ 则令 $A_i=M_{s_i}$，否则 $A_i=M_{s_i}^{-1}$，区间打 tag 维护 $+0,+1,+2$ 的矩阵即可。每次区间询问矩阵积就行。

QOJ6505

$p$ 的位置是确定的，枚举 $p$，求一下两边最长可以拓展的即可。

QOJ6506

注意到有 B 现在操作且 A 在 B 的周围时就死了。A 选一个 $\text{dis}(i,i+1)>2$ 的就赢了。

QOJ6509

这个操作是整体性极强的。考虑整体操作与询问串的关系，令操作为：若 $i=1$ 或 $s_{i}\ne s_{i-1}$，那么我们就会把 $i$ 删去，此时考虑称呼操作为【$i-1$ 把 $i$ 删去了】。第一次操作的前驱一定是 $i-1$，但是到后面的前驱会到更前面。我们希望在操作过程中保持原始标号不变。

区间询问可能会有 $l$ 被提前删去从而造成很大的影响。

扫描线 $k$，考虑整体对询问区间操作，维护 $fir_i$ 表示第 $i$ 个询问在 $k$ 次操作后的首个下标的位置。先考虑 $fir_i$ 怎么维护：如果这个位置在整个序列已经被删去，则后移一位，否则可能保持不变。

考虑维护存活位置中的相对位置。后面忘了。完全不会。

P8251

注意到如果一个位置成为好的了，那么以后的事情都与前面无关了。所以可以处理 $nxt_i$ 表示以 $i$ 开始的第一个好点。那么 $f_i=f_{nxt_i}+1$，跳出 $r$ 就是 $1$。倍增 $f_{i,j}$ 为 $nxt_i$ 的 $2^j$ 级优化即可。

P8252

考虑枚举某个元素为交集，按照 $|S_i|$ 排序后只关心上一个覆盖元素 $x$ 的集合 $lst_x$，取 $|S_i|$ 最大的一定是好的，此时我们假设还没有找到答案。判定是否是子集只需要看 $lst_x$ 是否全部存在且取等。

P8256

判 $0$ 是显然的，加入时确定是被左边删，保留到最后，还是被右边删。注意到被保留的必须是连续的一段。 考虑数据范围是 $O(n^3)$ 的，所以用一个 $O(n^3)$ 的 DP 来做，这种子串匹配考虑前后缀各删一些得到 $T$。如果保留到最后会有一个位移量。我们考虑每个字符确定类型：被左边弹出去，被右边弹出去，最终被留下。$f_{i,j,k}$ 表示前 $i$ 个有 $j$ 个是前面被弹出去，有 $k$ 个后面被弹出去。

20240906

QOJ1839

不妨设 $p_i=i$，第一个序列必须递增，考虑大小关系建图：$u\to v$ 为 $u$ 大于 $v$，连出来的二分有向图应该保证无环。可以考虑四元环的情况，因为递增所以都形如一个区间对一个点或者一个点对一个区间连边。有环当且仅当出现 $i<j,q_i>q_j,s_i=0,s_j=1$。考虑所有 $s_j=1$ 的位置，必然是 $q$ 的递增子序列。设计 DP 为 $f_{i,j,k}$ 为前 $i$ 个数长度为 $j$ 的结尾 $k$ 的 $q$ 的递增子序列数量，容易做到 $O(n^4)$。

P10684

考虑一行就是冒泡排序次数，可以用 $x$ 坐标减去前缀 $c_1$ 和来描述，考虑两行的次数。暴力维护 $ans_x$ 为使得第一行有 $x$ 个 $1$ 的最小代价，上下移动的代价确定，减去的定值确定。

考虑将两行的所有棋子的 $x$ 坐标之和放在一起考虑。

考虑在第二行移动，对于下面的每个边计算被跨过的次数。事实上只需要对上下两行最小化执行向右的操作使得某次操作时下面确定点向上可以匹配，向左可以随便执行，因为 $x$ 坐标减小同时，操作次数的代价 $+1$，这没有影响。

线段树维护所有的 $ans_x$ 可以做到 $O(n+q)\log n)$。

QOJ8225

看上去就很区间 dp，因此放在区间中做问题分析。假如我们确定了最小值的位置 $a_x$ 为区间 $[l,r]$ 的最小值，值为 $v$，那么给 $a$ 所有数都减去 $v$，对于 $b$ 的影响就是都减去了 $(r-l)v$。中间为 $0$ 的不管，可以分治成两个独立的子问题。设计 DP 为 $f_{l,r,k}$ 表示 $a$ 中的最小值为 $k$ 是否可行，转移需要枚举位置以及左右是否可行：$f_{l,pos,x+(r-l)k}\text{ and }f_{pos+1,r,x+(r-l)k}$。

然后发现只与 $r-l$ 有关，并且 $x<y$ 且 $x\equiv y(\bmod (r-l))$ 时 $f_{l,r,y}$ 合法一定有 $f_{l,r,x}$ 合法。考虑定义域值域互换，$f_{l,r,k}$ 表示在对 $r-l$ 取模为 $k$ 最大的合法最小值。转移是考虑枚举两侧长度的 $\text{LCM}=t$，对于所有 $0\to t-1$ 枚举可以得出两侧的所有状态，直接上暴力转移即可。时间复杂度 $O(n^4)$。

QOJ4894

我的评价是不如分块。显然记录当前位置为 $L$，每次要找 $l>L$ 且 $r$ 最小的区间。分块希望一次跳多个区间，维护 $dis_i$ 表示第 $i$ 个点跳到块外的步数，$nxt_{i,0}$ 与 $nxt_{i,1}$ 表示 $i$ 的直接后继以及 $i$ 的块外后继。对于加入区间 $l,r$，考虑整块的 $tag_i$ 表示当前未考虑的后继 $r$ 的最小值，这个后继要保证在当前块的后面。修改对于 $l$ 之前块打标记，对 $l$ 的块下传并修改。时间复杂度 $O((n+q)\sqrt n)$。

QOJ4890

没啥规律，强制钦定按照 $1$ 的个数排序没坏处。令 $f(x)$ 表示 $x$ 行的 $1$ 数量。用 SEERC2020 AND=OR 的分析套路，考虑枚举 $b$ 中为 $1$ 的个数 $t$。对于 $f(x)<t$ 必然选择 $a_x=0$，$f(x)>t$ 必然选择 $a_x=1$。现在需要考虑的只有 $f(x)=t$ 的行集合 $S$。对于 $f(i)<t$ 且 $c_{i,j}=1$ 的 $b_j$ 一定为 $1$，对于 $f(i)>t$ 且 $c_{i,j}=0$ 的 $b_j$ 一定为 $0$。由于已经排序，可以直接对这些求并，分别记录为列集合 $pre,suf$。显然要求两个集合不交才对于 $t$ 有解。而 $=t$ 的形态都应该相同，如果相同一定是 $2^{|S|}-1$，否则答案就是一个组合数随便选捏。

QOJ4895

定义 $g(x)=\prod(-1)^{k_i}$，容易发现 $f(x)\ne 0$ 时 $f(x)=g(x)$。显然 $f(x)$ 是一个完全积性函数。考虑 $f(xy)=f(xy)^2g(x)g(y)$。令 $h(x)$ 表示最大的 $t$ 使得 $t^{d+1}$ 为 $x$ 的因数。

$f(xy)^2=[h(x)=1]=\sum_{t|h(x)}\mu(t)= \sum_{t^{d+1}|x}\mu(t)$。

考虑往一个集合 $S$ 中插入数 $v$ 产生的影响。有 $\triangle ans=g(v)\sum_{t\mid v}\mu(t)\sum_{i\in S}g(i)[\dfrac{t^{d+1}}{ \gcd(t^{d+1},v)}\mid i]$。

枚举 $t$ 只用考虑 $v$ 的约数，由于 $t$ 是互不相同且值域很小，可以预处理所有贡献。直接 DSU on tree 就可以 $O(n\log^2n)$。

20240907

T373883

考虑钦定 $1$ 号的位置固定，那么 $2\to n$ 一定是一段前缀在 $1$ 的东边，剩下的后缀在 $1$ 的西边。枚举这段前缀是什么，考虑判断两侧的点的关系可以放在东边的上部分半圆中考虑，也就是对 $1$ 西边的点中心对称到上面，对于中心对称后考虑半圆上的前后关系即可判定原点的东西。由于是有标号单调性的，直接 DP 为 $f_{i,j}$，西边的第 $i$ 个在上面排名 $j$，处理出合法区间直接前缀和优化即可 $O(n^3)$。

T380965

容斥考虑同色点对为：可以通过红，蓝边连通的数量和减去两种颜色都连通的。考虑只保留两种颜色的 MST 的边，容易维护出前两种互不干扰的数量。对于两种颜色都联通的，如果两个点在两个图中的连通块都一样就是一个等价类，这种就是每个等价类的贡献和。排序后双指针判定，需要支持加边，删边。如果用启发式合并来撤销 / 加入，复杂度 $O(n\log n)$ 的。

T322009

选 $S$ 的权值 $2^q$ 很神秘啊，上组合意义。考虑对每个点等概率黑白染色，对于所有点构成的虚树算，中间的随便染，染出 $S$ 就是黑点虚树的概率。这个虚树是与树根无关的。令树根为 $p$ 计算出每个点的 $top_u$，其中 $top_u$ 为 $u$ 的某个儿子。分开考虑每个 $i\ne p$ 在拓扑序中 $i$ 在 $p$ 前面的概率。首先先考虑虚树点集 $S$ 共同包含 $i,p$ 的概率，容易计算总共包含 $p$ 的方案数，用总数减去仅在某个儿子中选的方案数。再考虑 $i,p$ 共同包含，提出来 $i,p$ 两端的子树，用 $top_u$ 可以算出 $p$ 那侧的大小，也就是个子树补，也容易计算。事实上 $p,i$ 在 $S$ 中拓扑序形成顺序的概率，显然仅与 $p,i$ 的路径本身有关。记录 $\text{LCA}_1(p,i)=t$，那么概率就是 $\dfrac{dis(p,t)}{dis(i,t)+dis(p,t)}$。$dis$ 表示路径边数。这样做是因为两侧几乎等价，我们只关心最大值。

T320948

数位 dp 加 KMP 自动机上 dp。

T410844

重点在于刻画答案的结构。考虑一个 $01$ 序列 $s_i=[i\in S]$。显然我们希望进行 $m$ 次向右移位，每个位置都不重合，最终覆盖 $[1,nm]$。

有解时，$01$ 段交替的长度 $c_1,d_1,c_2,d_2,\cdots$，一定有 $c_i$ 全部相等，并且 $c_i\mid d_i$。
显然可以将每个长度都除以 $c_i$。
考虑一种 $100100000000$ 的串，记录 $d_i$ 的最小值 $p$，那么每一个 $d_i$ 都可以减去 $p$。

执行后面两种操作可以不断递归到 $1$ 串。

考虑二元组 $(x,y)$ 表示 $1$ 的个数与总串长。那么 $(1,1)=1$，每次可以交替执行操作：

$(x,y)\to (x,ky)$。
$(x,y)\to (kx,ky)$。

求到达 $(n,nm)$ 的数量。显然可以 $n,m$ 也就是操作一二分开捏。

问题转化为：

$n$ 种不同的小球，每种有 $a_i$ 个内部互不区分的。对于每个 $k=1\sim \sum a_i$，求出放入 $k$ 个不同盒子每个盒子非空的方案数。

二项式反演钦定 $i$ 个盒子是空的，记为 $f_{n,i}$。剩下的可以 EGF 合并，具体二项式反演过程可以 NTT 做到 $O(N\log N+N\sqrt N)$。

T359629

显然 $A_i$ 对 $B_i$ 互相连边，有且当且仅当每个连通块形态为树或基环树，已知并查集连边时的计数是容易的。所以我只会 $O(n^2)$。

T359628

只关心所有链底，处理出 $w(l,r)$ 表示 $[l,r]$ 的最小代价，某个链底被选多次一定不优，直接 dp 不影响答案。

T376039

自动机上 dp，对于所有串建立 dfa，两个状态等价当且仅当后面接上任意长 $10$ 的 $01$ 串的合法性都相同，bfs 搜出自动机即可。自动机大小 $35$ 直接 dp 就行了。

T381603

这个数据范围这个合并方式考虑区间 dp。对于一个区间中，能力的最大值是一定有可能胜出的，这提示我们去想最值分治。考察当前序列最大值（设位置为 $mid$）左边的一个数，它要胜出，一定要把最大值打败。那么这个位置要胜出先把 $[l,mid)$ 的都杀完一定不劣。所以这个位置的权值应当至少是 $a_{mid}-(mid-l)$，并且可以是 $[l,mid)$ 的胜者。注意到我们可以枚举 $mid$ 以及值，往两侧形成独立的子问题。其实我们并不关心是谁胜出了，最后往上面传的只有具体的值。因此可以设计 dp 为 $f(l,r,x,y)$ 表示在所有 $\max(a_i)=y$ 的序列中，有多少个 $a$ 使得这个区间的胜者的权值至少为 $x$。可以 $O(n^3m^2)$ 在 $y$ 维度前缀和优化，枚举最大值位置与值来做。

T364846

考虑对于一个给定的 $p$ 如何刻画序列 $F$，先设置所有 $F_i=-1$，对于所有 $p$ 从大到小加入所有位置，当前的值为 $val$，考虑加入后形成的连续段长度为 $T$，对于所有 $1\leq i\leq T$，若 $F_i=-1$ 则令 $F_i=val$。每次赋值的显然是对于 $T$ 的一段后缀。那么给定 $F$ 的意义就是告诉你 $\ge k$ 所有点连续段长度的最大值就是 $F_k$。正向操作较难处理新连续段的生长与合并，并且无法使用连续段 dp 的套路。但是我们可以逆向操作，将加入变为删除某个点，选择某条连续段裂开，这样几乎是等价的，不用太考虑实际位置，实际状态数是 $\text{Bell}(50)=2\times 10^5$，可以接受。

T359324

差分约束模型直接建立有向图 $i\to a_i$，这题是建立内向基环树，题意等价于删除一些边使得图上最长路 $\leq m$。对于环上挂的若干棵树，我们可以从底到上贪心删边，考虑 $dis_i$ 为 $i$ 到下面的最长路，合并 $(u,v)$ 时如果 $dis_v+w_{u,v}\leq m$ 就保留边，否则删去 $(u,v)$ 并无论如何都让代价 $+1$。

难点事实上在环的部分，通过上一步剪掉所有挂着的树可以得到 $dis_i$ 表示树部分的距离，那么在环上走到下一条断的边的距离一定满足加上 $dis_i$ 都仍 $\leq m$。首先断环成链，把环变成长度 $2$ 倍的链更方便求出下一个位置。首先环上显然需要断边，考虑枚举第一个断的边是 $i$，我们希望求出 $nxt_i$ 表示最大的 $[i,nxt_i]$ 的环边可以被保留。而 $nxt_i$ 的意义就是下一个需要被断的边。如果有了 $nxt_i$，下一个就是完全独立的一个问题，我们可以一直跳 $nxt$ 知道转了一圈回来，这一部分是经典的倍增。考虑怎么求 $nxt_i$，这个东西在链意义是单调不增的，记录环上的前缀和为 $pre$，那么代价可以表示为单点 $dis$ 加上前缀和减一个定值 $pre_i$，这个东西随便推一下就是经典的单调队列了。

时间复杂度 $O(n\log n)$。

T292908

sb 出题人，懂不懂什么叫正难则反啊？？？$3.26\text{KB}$ std 被我 1k 做法爆了。具体就是答案为 $\sum_{T}[u\in\text{get}(T)]g(T)$，那么先假定都在，然后容斥掉 $u$ 子树里没有点的情况的贡献即可。

T417198

容易让 $(x,y)$ 的边权为 $(x,y)$ 回文组合的选定对数。朴素的状压求二分图匹配数量最多做到斐波那契数的复杂度，考虑对 $(2i,2i-1)$ 连边权为 $1$ 的边，那么权值就是直接选若干环的乘积即可，$2i,2i-1$ 同时在某个环，所以可以做到 $3^{n/2}$ 的状压（需要枚举子集合并）。

U415120

连续段的刻画方法是 $\max-\min=r-l+1$。后面那个扫描线的时候当常数赋初值即可。注意到两个连续段的交集仍然为连续段。那么枚举交集的连续段即可，$\max,\min$ 可以通过单调栈来化为区间加。询问一个连续段的左右端点可以通过维护区间最小值大小，个数，以及连续段的端点 $l,r$ 来做。枚举完交集后向两端分别拓展求乘积最后求和即可，时间复杂度 $O(n\log n)$。

T322892

考虑将权值分散到每条边上，就是两边连通块大小的乘积和，每条边的权值固定，但是每次操作可以让路径上的边贡献变成 $0$，可以在（树剖-标号）平面上拆为 $O(n\log n)$ 个矩形操作。

T360101

连通两个的操作上建立重构树，一个虚点就代表一个连通块，任何对于两两之间 $+1$ 的都可以在这个虚点上做。树剖容易做到 $O(n\log^2 n)$。

T409793

最大难点在读题。每次操作是对于一个连通块进行赋值。形式化地考虑操作 $1$ 在干什么：对于一条路径 $S$ 的权值为 $\max_{i\in S} a_i$。定义 $p_{u,v}=\min_{S(u\to v)} w(S)$，即最大点权最小值，那么 $h_u>p_{u,v}$ 时就应该满足 $h_u=h_v$。这样的点 $v$ 对于每个 $u$ 显然是一个连通块。

最大点权最小值，考虑将所有网格图的边按照边权排序，边权定义为 $\max(a_x,a_y)$，那么每次在 $x,y$ 时合并两个连通块，建立一个新的虚点代表值，查询 $p_{u,v}$ 可以通过查询 $u,v$ 在重构树上的 $\text{LCA}$ 点权来做到单次 $O(1)$，预处理 $O(n\log n)$。

注意到修改的上升和下降并不等价，所以需要考虑原来的水位为 $h_1$，修改为 $h_2$，然后对所有被影响的 $h_u$ 做重新赋值。

而在重构树上，$p_{u,v}<x$ 的 $v$ 是重构树上 $u$ 的一个特定祖先 $q$ 的子树中的所有叶子节点，$q$ 可以树上倍增找。

$h_2>h_1$ 时，对于 $p_{u,v}<h_2$ 的 $h_v$ 都修改为 $h_2$。
$h_2<h_1$ 时，对于 $p_{u,v}<h_1$ 的 $h_v$ 都修改为 $\max(p_{u,v},h_2)$。

对于操作 $2$ 的标记额外处理下即可。两个同属一个标记，复杂度大概 $O(n\log n)$。

P10271

容易发现是选取两个相同的奇回文子串，二分哈希即可，建议评黄。

P7976

变为模 $3$ 意义下的数字串，$n$ 相当于给定上限，数位 dp 即可。每一对 $x$ 的位与 $n$ 的位都会对 lucas 定理做贡献，dp 状态加进去就行。

P10998

一眼想到枚举 $(a,b)$，考虑 $(a,b)$ 向外连了 $\leq B,>B$ 条边两种情况。前面的直接暴力枚举所有出边，后面的暴力枚举 $a$ 的出边 $(a,c,d)$ 即可。可以通过哈希表快速检查 $(a,b,c,d)$ 是否合法。

P10997

两条单调分界线独立选取，独立 dp 即可。

P10769

$f_{i,j}$ 表示 $i$ 为右端点开了 $j$ 条线的最小代价。感受那股劲，有决策单调性。上分治即可。

P10896

CF1919E

题意就是重新排列 $p$，要求 $p_1\in\lbrace-1,1\rbrace,|p_i-p_{i-1}|=1$。考虑用连续段 dp 的套路从小到大加入点。

20240908 上午模拟赛

T1：列出式子后发现是最小化字典序，贪心选即可。

T2：从大到小排序加点维护直径，$u$ 到 $S$ 点集中的距离最大值的 $v$ 一定在 $S$ 的直径端点中。

T3：填数游戏超级弱化版。

T4：没想到分治，输麻了。直接枚举 $k$ 硬拆 $\min$ 式子就行。

$100+100+100+55=355$。

20240908 下午模拟赛

T1：这个故事告诉我们对拍是没用的。

T2：莫队修改次数巨大多，考虑根号平衡就是 $O(n\sqrt n)$。

T3：发现 $x,y$ 属于相离区间的统计只与极长区间长度有关，本质不同长度 $O(\sqrt n)$ 种，写的太难看把线性变成 $O(n\sqrt n)$ 了。/hanx

T4：折半考虑，由于一个跨越两端的集合 $R'$ 的权值固定在右侧，所以可以只在左边枚举子集，时间复杂度 $O(6^{n/2})$。

$90+100+70+100=360$。

这俩$\textbf{\color{red}普及}$模拟赛脑子好用点都能 AK。

20240909

QOJ895： 图的总边数是 $(m+1)m/2$，那么对于每种颜色分开考虑，在最终的图上都必然是一个大小为 $(m+1)/2$ 的匹配，所以 $m$ 必然是奇数，且每条边连接的端点不重不漏，假设在输入的图中第 $i$ 种颜色已经有 $t$ 个匹配以及 $n-2t$ 个单点，这些点最后都需要形成匹配，必须满足 $n-2t\leq m-n+1$。如果这个限制已经不满足了，那么必然无解。否则考虑增量构造，每次从 $n\to n+1$，并维持此条件成立。建立这样的二分图：$L_i$ 表示第 $i$ 种颜色，$R_i$ 表示图上的第 $i$ 个点。$u\to v$ 代表图中 $v$ 还没有 $u$ 颜色的匹配。对于每种颜色，设已经匹配了 $p_i$ 对，那么连 $m+1+2p_i-2n$ 条 $i\to n+1$ 的边。这里 $n+1$ 号点我们认为其可以被匹配 $m-n$ 次，意思是至少有 $n$ 种颜色被加上。由于是正则二分图，左部图一定可以匹配上。时间复杂度 $O(m^{3.5})$。

QOJ4780： 模拟赛的输出内容变为所有操作结束后输出每个队列颜色种类数，这个换维下就是搞笑题，将每个颜色放在最后统计即可。在本题中，考虑计算每个操作 push 进去的数在哪个时刻被全部弹出去，这个时刻记为 $nxt_i$，那么对于同一种颜色的所有操作，求 $[i,nxt_i]$ 的区间并进行区间 $ans$ 加一即可，这样可以抛弃掉颜色限制。不是很好 $\text{polylog}$，考虑序列分块。对于某一个位置而言，无论何时，后侧传来 $a_i$ 个数，当前位置就会被弹出。先逐个块考虑，维护当前块中所有队列的大小。如果碰到询问完全包含这个块就让 tag 加一，否则重构整个块。双指针扫描线时间维，记录当前时间 $i$，求出最大的 $p$ 使得 $[i,p]$ 非空，这时如果当前询问完全包含此块，就让 $nxt_i$ 对 $p-1$ 进行 $\text{chkmax}$ 操作。对于操作的散块，可以拆分成所有单点，我们只需要换维，BIT 维护时刻是否有操作的区间和，这个 $p$ 可以在散块的询问上二分 BIT 进行。时间复杂度 $O(n\sqrt n+n\log^2n)$。

QOJ6670： 枚举 $1$ 的位置，所有的合法区间一定不会包含两个 $1$，按照这些 $1$ 分段，相当于需要向左拓展选 $l$，向右拓展选 $r$，使得 $[l,r]$ 为 $1\sim r-l+1$ 的排列。考虑这个怎么做，其中的一个必要条件是 $[l,r]$ 之中的最大值必然为 $r-l+1$，所以考虑钦定最大值在左侧 / 右侧，每次只需要判断一个区间是否合法。判定一个区间构成的数集是否为 $[r-l+1]$ 可以使用 xor-hashing。

QOJ6670： 模拟赛出题人原神真玩多了，但是场切了。考虑钦定 $k$ 个点是好点，这些钦定的鞍点必然不同行不同列，行列的具体位置无关所以可以看成都在右上角，实际位置乘个下降幂就行。考虑对值域扫描线，维护 $f_{t,k}$ 为所有数 $\leq k$ 时，钦定有 $t$ 个好点的方案数，转移枚举新加入 $j$ 个值为 $t$ 的好点即可。时间复杂度 $O(n^3)$。

QOJ2273： 模拟赛出题人觉得原神是真好玩，但是场切了。考虑对 $S$ 串建立 KMP 自动机，并且从前往后确定 $T$ 中字符的过程。令 $f_{i,j}$ 为填好了 $T$ 中的前 $i$ 个字符，$T$ 的最后 $j$ 个字符与 $S$ 的前 $j$ 个字符相同时，也就是当前处于自动机上的节点位置为 $j$ 时最大的权值。转移枚举出边 $k$ 走到 $nxt_{j,k}$，此时 $T$ 串中长为 $j,fail_j,fail_{fail_j},\cdots$ 的后缀和 $S$ 串相对应长度的前缀相同，而其他后缀与 $S$ 串相对应长度的前缀必然不同，LCP 长度是确定的。考虑求出 $fail$ 树上的深度，向外转移加上它作为新贡献的权值即可。时间复杂度 $O(m^2|\sum|)$。

QOJ2563： 模拟赛出题人发现原神更新了，但是场切了。考虑到除了高级水管之外的东西没什么用，事实上你只需要填高级水管，只要没有什么硬伤比如向外连或者相邻连不了。你的朋友都能干活。考虑到高级水管可以横纵拆开，两个维度并没有联系，只是对于一个点必须两个方向各自有且仅有一个。给每条边赋一个状态，表示有没有水管通过这条边相连。考虑一个高级水管即为要求一个格子中相对的两条边状态不同。注意到行和列几乎独立，对于一行竖着的边，如果相邻两个有要求的边奇偶性不对，即不能满足中间的格子均为好格子，则说明中间的格子中至少一个不是高级水管。对于列类似。抽象成图论模型就是某些行连续段中间至少一个坏点，某些列连续段中间至少一个坏点。考虑对行连续段和列连续段分别建立为左部图和右部图，连一个二分图。如果两种连续段在某个点产生相交就将两个点连到一起，那么问题就是最小边覆盖，跑一遍匈牙利即可。

QOJ1262： LGV 引理 noip 用不上，先不写了。大概就是行列式的每个元素都是多项式，直接操作多项式复杂度会炸。但是可以带点值，对于所有点值跑，最后插值跑出答案多项式。

QOJ8730： 二选一模型直接上二分图。令 $b_i$ 代表原来的 $b_i+n$，那么将 $a_i$ 与 $b_i$ 连边构成二分图，此时我们要选出独立集，不难发现，$k=0$ 的答案就是所有连通块中，左部图大小与右部图大小的 $\min$ 求和，即全选出左边或者全选出右边。考虑更改视为：删去边 $(u,v)$，添加边 $(x,y)$，要求 $|\lbrace u,v\rbrace\cap \lbrace x,y\rbrace|=1$。$k=1$ 时可以不考虑添加，因为 $n>1$ 时可以直接在连通块内部连。只需要计算断掉一条边后的答案，边双缩点后是容易的，枚举所有割边更新答案。$k=2$ 时枚举断掉的边，新增的边一定是：与剩下的连通块中左右部点的个数差距最大的连通块，连接。可以 $O(n)$ 或者 $O(n\log n)$ 维护。

CF1930G： 难点在于刻画答案序列前缀 $\max$ 的结构。记录 $mx_{u}=\max_{v\in\text{subtree}(u)} v$，那么进入一个子树 $u$ 再结束后的结尾要么不变要么被更新成 $mx_u$。考虑一个节点 $u$ 成为 $\text{premax}$ 的判定条件：所有祖先的标号一定更小，因为祖先一定在 $u$ 之前，且所有 $mx_v\ge u$ 的 $v$，如果不是 $u$ 的祖先，那么一定还没有被访问过，因为不会回溯。

可以考虑对于一个点的所有子结点，按照 $mx_v$ 进行排序，并且得到一个 $\text{dfs}$ 序。考虑 $f_i$ 表示 $i$ 作为 $\text{premax}$ 结尾的所有序列，要求恰好以 $i$ 为结尾的方案数。由判定 2，按照 $\text{dfs}$ 序跑 dp 一定是可以无后效的。那么考虑 $v\to u$ 转移成功的情况：

一定有 $v<u$。并且 $v$ 的遍历顺序一定在 $u$ 之前。换而言之，$\text{dfn}_v<\text{dfn}_u$。
若 $\text{lca}(u,v)=v$，即 $v$ 是 $u$ 的祖先，那么要求 $v\to u$ 的路径上，恰好满足 $v$ 是次大，$u$ 是最大值。
若 $\text{lca}(u,v)=d\ne v$，那么一定有 $d$ 关于 $v$ 方向的子树 $d'$ 已经遍历完毕，$v$ 结尾一定是要求 $mx_{d'}=v$。考虑放在 $d$ 上统计，对于每个除了下去的链的子树，能转移的一定是 $\text{maxsubtree}$。合适的转移顺序就是要求按照 $mx_v$ 进行排序，顺势推下来就很自然。

能转移的点要么是祖先要么是子树 $\max$，令 $p$ 为 $1\to u$ 的路径的 $\max$，不含 $u$。$p>u$ 时 $f_u=0$。否则有 $q$ 能转移当且仅当：$q\in[p,u)$；$q$ 为 $u$ 的祖先；$q$ 为 $u$ 祖先中某个儿子的 $\text{maxsubtree}$。容易在 $\text{dfs}$ 结束时撤销贡献，用树状数组维护。时间复杂度 $O(n\log n)$。

P10093： 考虑枚举第 $k$ 大值是第 $x$ 个位置，记一个辅助序列 $b_i\in\lbrace0,1\rbrace$，那么 $b_i=1$ 当且仅当 $a_i>a_x$ 或 $a_i=a_x,i>x$。这个区间 $[l,r]$ 是可以被选出的当且仅当有 $k$ 个 $1$ 存在，只需要寻找前面的 $k$ 个 $1$ 和后面的 $k$ 个 $1$，暴力枚举在这之中恰好有 $k$ 个 $1$ 的子区间，此时这个区间两端的 $1$ 的位置确定，但是实际的 $l,r$ 可以变动，写个 ST 表查询前缀和最大值最小值即可。对 $a_i$ 从小到大值域扫描线，可以链表维护上一个 $1$ 的位置以及下一个 $1$。时间复杂度 $O(nk+n\log n)$.

20240910

UOJ786： 考虑将 $(i,j)$ 与 $(j,i)$ 交换，那么每一列的牌就对应每一个人，问题转换为将每行的顺序任意排列，使得每一列都有 $n$ 种牌。做 $n$ 次二分图匹配（左部图种类匹配右部图行号），根据 Hall 定理，这样匹配一定是有解的。

QOJ2577： 考虑将方案数转为概率，每次操作等价于有 $1/2$ 的概率执行，那么只需要求出期望有多少个节点有标记，输出时乘上 $2^t$ 即可。暴力维护 $f_o$ 为 $o$ 当前有标记的概率，$g_o$ 为祖先中存在标记的概率，作为标记下传时进行更新。需要对节点与询问区间的关系进行分类讨论。

P11038： 注意到对于给定的 $k$ 剖分，儿子个数 $\leq k$ 的都可以全选，对于 $>k$ 的可以拉出来建立虚树，相当于要选 $k$ 个儿子。树上 dp 就是 $f_u$ 表示子树 $u$ 的答案，那么我们要选 $f_v+w(u,v)$ 的前 $k$ 大的 $w$ 置为 $0$，剩余保持再取 $\max$。在朴素的 dp 之外，考虑一些关键点的儿子有可能并不在虚树之中，但是依然要维护。对每个点开一颗平衡树，最开始维护每个点连出去的边权形成的集合，$k$ 来更新的时候删去原来的，并且暴力加入所有儿子的 $f_v+w(u,v)$，对这个求一下第 $k+1$ 大即可。时间复杂度 $O(n\log^2 n)$。

QOJ5175： 考虑首都到各个关键点的最优路径一定是一棵树，否则如果出现环可以走更短的一边。我们想让翻修一定有用，那么钦定一棵树后一定只修改这棵树上的边。令 $f_{u,i,S}$ 表示 $u$ 为最短路树的根时，到达集合 $S$ 中的关键点，修改了 $i$ 条道路，的最小的距离最大值。答案即为 $f_{1,i,\text{All}}$。考虑按照集合 $S$ 从小到大进行 dp，转移分为两个根相同的子树，对于不交的集合合并成同一个，以及换根 $(u,v)$ 但是集合 $S$ 不变。分别对应 $\max(f_{u,T,i},f_{u,S-T,j})\to f_{u,S,i+j}$ 以及 $\min(f_{u,S,i}+a,f_{u,S,i-1}+b)\to f_{u,S,i}$。注意到合并两个状态是对两个数取 $\max$，而答案由于任意边 $b\leq a$ 所以具有单调性，对于第三维进行双指针即可。后面那种转移个类似最短路的三角不等式，通过一次分层图最短路更新 dp 值。时间复杂度 $O(2^kn^3+3^kn^2)$。

QOJ5013： 考虑将问题转化为选出一个尽量长的子序列，这个子序列的连续段数量 $\leq m+1$，长度作为 $ans_m$。记录每个连续段长度为 $a_i$，一个极长连续段内一定不会被断开。并且令划分出的 $m$ 个子段中允许空序列，这不影响答案。连续段数量 $\leq 2$ 是平凡的，假设形成了 $m$ 个连续段，那么 $ans_{\ge m-1}$ 一定都是 $n$。所以我们只会保留若干个连续段，容易发现删掉相邻两个连续段一定劣于删掉其中一个。所以删掉的连续段不相邻。两端的连续段代价都是 $1$，需要特殊考虑是否保留，中间的删除代价都是 $2$，枚举两端的 $4$ 种情况，问题转化为中间选择一些两两不相邻的连续段删去，使得总和最小。这是经典的反悔贪心问题，考虑当前最小的，要么选它，要么调整成选两端的。使用小根堆维护之。时间复杂度 $O(n\log n)$。

QOJ8702： 令集合 $S$ 为当前状态可能为狼人的人，必然有 $m\in S$，考虑使用 $\min-\max$ 容斥，对于一个元素定义 $a_i$ 为确定 $i$ 是否在狼人集合中的时间，我们要求的就是 $E(\max a_i)$，对这个使用 $\min-\max$ 容斥，答案所求就是 $E(\max(U))=\sum_{S\subseteq U}(-1)^{|S|+1}E(\min(S))$。而 $U=\lbrace1,2,\cdots,n\rbrace\setminus\lbrace p\rbrace$，其中 $p$ 为预言家。考虑 $E(\min(S))$ 的具体就代表从 $S$ 开始执行的期望步数，使得可以锁定的狼人集合变为 $S$ 的真子集。令 $g(n)=\binom{n+1}{2}$，即 $1\sim n$ 的子区间个数，那么对于一个集合 $S$ 的有效执行概率 $p(S)$ 为：考虑 $S$ 将所有 $n$ 个数断裂为长度分别为 $c_1,c_2,\cdots,c_k$ 的连续段，无效的个数 $v(S)$ 就是 $\sum g(c_i)+(c_1+1)(c_k+1)$。$p(S)$ 为 $g(n)-\dfrac{v(S)}{g(n)}$，回到前面的，$E(\min(S))=\dfrac{1}{p(S)}$。考虑对这个东西进行 DP 优化，注意到 $g(x+y+1)=(x+1)(y+1)+g(x)+g(y)$，可以将 $c_1+1+c_k$ 视为相连的。对于 $v(S)$ 相同的放在一起。设计 $f_{i,j,p}$ 表示前 $i$ 个人，$v(S)=j$，预言家是否确定的总贡献和。转移枚举到 $q$ 为一个连续段的结尾即可。时间复杂度 $O(n^4)$。

CF773E： 感性理解按 $a$ 从小到大排序一定最优，逆序对的 exchange argument 可以证明。然后考虑 $F$ 一定是先减后增的，那么考虑先找到这个转折点，对两部分分开做。先考虑后面那段 $+0/1$ 的段，假设有两个数，那么变化为 $x\to\min(\min(x+1,a)+1,b)$。可以拆开到每一项的 $x\to \min(x+2,a+1,b)$，对于更长的序列同理，即 $\min_{i\ge pos}len-i+a_i$。由于不关心原序列具体位置，用权值线段树维护之，令 $c_i$ 表示 $\leq i$ 的值的个数，就是在求 $len+\min_{i\ge pos}i-c_i$ 哦。最后一个 $-1$ 是有单调性的，分界点 $pos$ 不难发现就是最大的 $p$ 使得 $-c_p\leq p$，可以权值线段树上二分求。时间复杂度 $O(n\log n)$。

20240911

P7648： 注意到状态转移并不依赖于当前具体时间，只关心上一次进球到这一次进球的时间间隔，与是谁进的。dp 状态必然需要记录时间以及两队的比分，我们只关心进球为 dp 划分状态的边界，这样状态是可接受的。$f(t,x,y,id)$ 表示当前为第 $t$ 秒，两队比分为 $x:y$，刚刚进球，现在球在第 $id$ 队的 $1$ 号的概率。预处理两次相邻进球的进球方与间隔时间，这些在转移过程中保持不变，时间复杂度可以接受。

QOJ9243： 令 $S$ 各个元素的出现次数为 $c_1,c_2,\cdots,c_k$，$\sum c_i=n$。考虑 $p(S)=\large\prod_{i=1}^k\binom{n-\sum_{j<i}c_j}{c_i}$，我们要求每一项均为奇数，逐项考虑容易发现，$c_i$ 在二进制表示下两两不交，即为 $n$ 的一组划分。现在考虑将 $n$ 的每一位为 $1$ 的 $i$ 划分给值 $a_i\subseteq y$，那么合法的 $a_i$ 与 $S$ 形成双射，我们要求 $\cup a_i=y$ 且 $\sum a_i2^i=x$，这比较困难。考虑对 $y$ 进一步拆位，相当于一个 $\log n\times \log y$ 的矩阵，$a_i$ 的每一位为 $1$ 的位 $j$ 会对总和造成 $2^{i+j}$ 的贡献，这样位置互不干扰。我们只需要对这个矩阵计数，$(i,j)=1$ 代表 $a_i$ 的第 $j$ 位为 $1$。相当于 $n,y$ 为 $0$ 的位不允许对应的行列填 $1$，剩下的可以填，但是要求所有的 $1$ 的贡献 $2^{i+j}$ 和为 $x$。考虑从小到大对于 $x$ 数位 dp，考虑到第 $d$ 位就找出所有 $i+j=d$ 的位置，由于需要最终并起来恰好为 $y$，还需要状态压缩哪些行有 $1$ 了，状态就是 $f_{d,S,p}$ 表示前 $d$ 位中，前 $d-1$ 位已经和 $x$ 对应位完全匹配，$S$ 集合的行中有 $1$，低位向前面进位的值是 $p$ 的方案数即可。所以这个是 CF1864H。由于每次转移是取并，大概需要一次 FMT 求形如 $f(x,z)=\sum_{x\subseteq y\subseteq z}g_y$ 的东西。复杂度懒得算了。事实上也可以对每个 $s$ 子集分开做最后子集反演。

20240912

QOJ8627： 不是哥们，$f(t,u,0/1)$ 表示当前时间 $t$，雨是否已经变大，在 $u$ 的最优决策以及最优期望淋雨量不是做完了？？双指针所有 $0\to 1$ 边上的转移系数，随便后缀和即可。

QOJ8240： 其实可以从前往后考虑这个栈。记录 $nxt_l$ 表示下一个与 $l$ 值相同的位置，如果 $nxt_l\leq r$ 就清空并且让 $l$ 跳到 $nxt_l+1$，否则 $l\to l+1$ 并让 $ans\to ans+1$。分块加速做即可做到 $O(n\sqrt n)$，具体就是维护直接后继与跳出块的后继以及贡献。不知道为什么过不去/fn。

QOJ9242： 注意到 $k,b$ 都是定值，和 $i$ 关系不大，考虑构造 $c_i=2a_i-ik-b$，等价于要求 $c_{i+r}=c_{i-r}$，那么一次询问 $\text{rad}(i)$ 就是在询问 $i$ 为回文中心的最长奇回文半径。修改操作就是对于一个区间加上 $2v$，考虑线段树维护正反串哈希以及反串哈希，对于一个哈希值区间加是容易的，询问就考虑二分答案，时间复杂度 $O(n\log^2 n)$。

QOJ9245： 猫树分治，前后缀 dp 表示 $f_{i,j,0/1}$ 为考虑到位置 $i$，当前边界为左还是右括号，选出了 $j$ 个括号的方案数。合并的复杂度是 $O(k)$ 的。对于子区间询问那个对左右乘上贡献即可。

QOJ9250： 一眼支配对，不难发现 $(i,j,k)$ 与 $(l,r)$ 没有太大关联。令值域 $D=10^6$，考虑倒序枚举答案为 $d\leq D$，标记所有 $D\mid a_i$ 的位置，对于特定的 $j$，前驱 $i$ 是确定的，而后继 $k$ 就是最小的 $k-j\ge j-i$ 且 $D\mid a_k$。考虑找出这样的三元组并且将 $(i,k)$ 记为合法对。若有 $[i,k]\subseteq [l,r]$ 就将 $[l,r]$ 的询问答案记为 $D$。这样扫描的复杂度是 $O(nd(D)_{\max}+D\ln D)$ 的，因为对于一个数最多被统计 $d(D)_{\max}=240$ 次。这个时间限制不允许我们带多余的东西，考虑怎么找三元组，找前驱是简单的，扫后继的时候记录一个 $suf_i$ 表示 $\ge i$ 的最小的合法的 $k$，也容易找出来。这样对于 $(i,j,k)$ 可以找出来 $O(n)$ 组。有了所有点对，点对的属性就是 $[l,r,v]$，表示 $[l,r]$ 区间中有一个权值为 $v$ 的点。放在二维平面上，所有修改区间与询问挂在 $r$ 上离线扫描线，令 $x$ 轴为 $r$，$y$ 轴为 $l$，那么就是 $O(q)$ 次询问一个后缀值域上的最大值。由于修改次数高达 $O(nd(D)_{\max})$，询问只有 $O(q)$，需要使用 $O(1)-O(\sqrt D)$ 的分块来根号平衡。

QOJ9252： 首先考虑将原来的序列翻转，单向地考虑，记录 $a_i$ 为第 $i$ 个位置上企鹅的值，$b_i$ 为这个位置的企鹅的标号。考虑 $p$ 为 $a_i$ 最大值的位置。如果 $a_i+a_p\leq W$，可以在序列中任意交换，否则 $i,p$ 的相对位置关系不会改变。最值分治，删去这些任意换的 $i$，剩下的 $i$ 形成了子问题。那么建立大根笛卡尔树，找到祖先中最浅的 $p$ 使得 $a_i+a_p\leq W$，方案数考虑加到支配 $i$ 的 $p$ 上，对于所有位置乘个排列就行了。令 $p$ 在笛卡尔树上支配了 $[l_p,r_p]$，那么对于 $i$ 有一个随便换到的区间。经典问题，扫描线序列，动态维护当前位置上有什么值是可以填进去的。需要删除 $x$ 时，将 set 中比 $x$ 编号更小的依次弹出，再弹出 $x$。

QOJ9254： 考虑所有数出现次数 $\leq k$ 的概率为 $p_k$，答案就是 $m^n \sum_{k=1}^n(p_k-p_{k-1})k$。考虑怎么求 $p_k$，钦定有 $t$ 种数出现次数 $>k$，进行容斥即可。由于调和级数，时间复杂度 $O(n^2\log n)$，因为 dp 的第三维是 $n/k$ 级别的。

QOJ6408： 审题哦，问的是无序集合，懒得喷了。我们考虑判定一个集合是否可行而不是对操作序列计数。考虑最后选中的集合是 $S$，那么 $S$ 可以成为前 $|S|$ 大当且仅当 $\min(S)\ge\max(U\setminus S)$。$v$ 的限制很神秘，考虑分类讨论 $|S|$ 与 $v$ 的关系，不难发现 $|S|< v$ 与 $|S|\ge v$ 本质相同。$|S|\ge v$ 时一定不会给 $S$ 之外的投票，此时 $\max(U\setminus S)$ 是确定的。考虑令 $\max(U\setminus S)=k$，那么对于所有 $i\in S$，令 $b_i=\max(0,k-a_i)$，那么每次操作就是对 $v$ 个 $b_i$ 执行 $b_i\to b_i-1$，问能否让 $b_i\leq 0$。这个操作成功当且仅当 $\max(b_i)\leq m$ 且 $\sum b_i\leq mv$。按照 $a_i$ 排序进行 dp，枚举 $\max(U\setminus S)$ 所在的元素为 $k$，那么 $>k$ 的 $b_i$ 均为 $0$，但是前面的 $S$ 中的元素必须有 $\sum b_i\leq mv,\max(b_i)\ge m$。在排序时后面那个就是限制一个区间 $[l,r]$ 的数可以被选入 $S$，对这段区间执行背包 dp 即可。注意到背包是可撤销的，可以从小到大扫描 $k$，$l$ 双指针跑。视 $n,m,V$ 同阶，时间复杂度 $O(n^4)$。

QOJ6410： 其实就是一个位置占领一个十字，问最少放多少个，从每一条直线上去考虑，其实是竖着 $a_n$ 条线以及横着 $n$ 条线，需要最大化交点数，对于一个线最多有一个交点。求最小个数那么贪心从左下往右上显然是优的。reverse 一遍 $a$ 就是找最大的 $a_i\ge i$ 且 $a_{i+1}<i+1$，那么让 $i$ 就作为答案，记录这个第一问的答案为 $k$。注意到 $k\times k$ 的位置是关键的，如果存在某个位置不被控制就寄了。那么考虑计数：必须满足前 $k$ 行中每行都有 $\texttt{R}$，或者前 $k$ 列中每列都有 $\texttt{R}$。考虑将答案计算设为：满足条件 $1$ 的方案数，加上满足条件 $2$ 的方案数，减去 $k!$。减去的 $1,2$ 都满足的显然就是内部 $k\times k$ 的正方形中恰好每行每列都恰有 $1$ 个 $\texttt{R}$ 的方案数。条件 $1,2$ 的计算差不多，只需要转化下维度就行了。现在考虑计算前 $k$ 行每行都有 $\texttt{R}$ 的方案数。显然前 $k$ 行每行的限制都不用管，且令这些 $\texttt{R}$ 的列号构成的集合为 $S$，那么必须有 $\lbrace1,2,\cdots,a_{k+1}\rbrace\subseteq S$，特判掉 $k=n$ 即 $a_n=n$ 的情况后，可以 dp 设 $f_{i,j}$ 表示前 $i$ 行放 $\texttt{R}$ 的方案数，使得 $|\lbrace1,2,\cdots,a_{k+1}\rbrace\cap S|=j$。转移是 $O(1)$ 的。可以 $O(n^2)$ 完成这个问题。

QOJ6417： $k$ 为奇数时 $E(a_{(k+1)/2})=\dfrac{n+1}{2}$，所以 $k$ 为奇数答案为 $\dfrac{(n+1)n^k}{2}$。我们声称 $k$ 为偶数时与平均值的关系也很大，并且两侧是对称的，我们可以计算 $E(a_{k/2+1}-a_{k/2})=d$，考虑将 $d$ 拆到每一段上最后求和。那么 $E(a_{k/2})=(n+1-E(d))/2$。考虑在 $\leq i,\ge i+1$ 两边分别选的概率为 $p_i$，也就是 $(i,i+1)$ 对 $d$ 造成贡献的概率是 $p_i$，那么 $E(d)=\sum p_i$。

20240913

QOJ6409： 考虑建立二分图，左部图的 $a_i$ 与右部图的 $b_i$ 连边。连通块是独立的，最大化的话大概都就是连通块有 $m$ 条边，可以组出来 $m/2$ 条合法组。构造考虑建立 dfs 树，对于非树边优先匹配即可。

QOJ6416： 显然可以二分答案 $mid$，不妨设 $b_i$ 单调不减。那么就是要找到最大的 $q$ 使得 $b_q\leq k$，计入答案的数量就是 $\sum_{i\leq q}[i\in S]$。那么考虑从小到大枚举 $q$ 使得 $b_q=k$ 是否可以作为答案。考虑 $mid$ 的限制就必须有在 $[1,q-1]$ 中的前 $mid-1$ 小以及在 $[q+1,n]$ 中的前 $k-mid-1$ 小。拿个堆扫描线维护堆内数的和即可。时间复杂度 $O(n\log^2n)$。

UOJ806： 将询问离线，放到每个 $g$ 上求。考虑 $i\to p_i$ 构成的内向基环森林，研究函数 $f_u(x)$ 表示 $a_u$ 在 $x$ 时刻的值。对于边 $(u,v)$ 考虑 $a_u$ 与 $a_v$ 的关系。先考虑图是一棵内向树的情况：从根向下考虑，有 $root$ 的儿子 $u$ 的 $a_u$ 在 $\max(a_{root}-a_u,0)$ 的时间内都是 $a_u\to a_u+1$，后面保持不变。此时 $p_u$ 是一个分段函数时，$u$ 的分段函数考虑怎么处理：$p_u$ 的分段函数形如一段时间 $+1$，接下来一段时间不变，再加一，循环往复。考虑初始的 $a_{p_u}-a_u=k$ 的影响。考虑把这个看成一个变量的变化：不妨设 $f_{p_u}(0)=0$，如果 $k<f_{p_u}(t)$，则 $k\to k+1$，否则 $k$ 不变。一次的变化形如 $k\to \min(k+1,f_{p_u}(t))$，将这个东西展开，也就是将 $\min(\min(a,b+1)+1,c)$ 看成 $\min(a+2,b+1,c)$，那么有 $f_u(t)=\min_{i\leq t}\lbrace f_{p_u}(i)+t-i\rbrace$。在操作结束后整体平移 $k$ 就可以得到 $f_u(t)$。事实上对于一个环而言，环上最小值的点永远是最小值，因此其一直是 $+1$ 的，可以断环为链，变成树的情况。注意到当 $f_u(t)=f_{p_u}(t)+0/1$ 时之后会一直保持。具体值不好维护，考虑就是平移 $dep_u$ 会有更好的性质。也就是令 $g_u(t)=f_u(t+dep)-dep$。可以直接动态开点可持久化线段树维护。那么线段树二分找到一个时间使得 $k$ 第一次两个值相等。zak 做法可以倍增维护，不会啊。

PKUSC2022 D1T1：注意到操作的阶段划分一定是交替进行的。先考虑一个变量怎么做，求一个 $f(x,y)$ 表示当前是 $x$，后续操作使得在第一次 $>x$ 时值为 $x+y$ 的概率，$1\leq y\leq m$，在此过程中带一个属性作为期望步数，重新定义加法与乘法即可。对于 $f$ 的转移，考虑枚举第一步的值是 $k\in[-m,m]$。若 $k=0$ 列一个方程即可。$k>0$ 直接加上。$k<0$ 可以用先前的 $f(\max(0,x+k),*)$ 来转移，这一部分单次需要 $O(m^2)$。考虑有了 $f$ 怎么做原问题：事实上只关心 $|x-y|$ 以及 $\max(x,y)$，由于初始时 $x=y=0$，定义 $g(x,y)$ 表示当前 $\max$ 在 $x$，$\min$ 在 $x-y$，这种情况的概率以及期望步数。$g$ 的转移分讨这一步对于 $f$ 的前进发生在 $\min$ 上还是 $\max$ 上即可。时间复杂度 $O(nm^2)$。

PKUSC2022 D2T2： 考虑对每种颜色随机赋权值使得每种颜色的边权异或和为 $0$，那么异或和为 $0$ 的一条路径极大概率是合法的。树上前缀和之后 $path(u,v)$ 合法当且仅当 $pre_u=pre_v$。维护一个数据结构来维护点集，支持 $O(1)$ 加入，$O(1)$ 查询同色点对距离最大值，可以使用 $O(n\log n)-O(1)$ 的 $\text{LCA}$ 来维护每种颜色的直径端点来做。考虑先把不删点的答案和端点找出来，不在这条路径上的点显然都已经确定，对于这条路径上的点，考虑分为三部分取 $\max$，分别为这条链左边的部分，右边的部分，自己子树。分别可以分开维护 $pre,suf$ 以及 dsu on tree 来做。时间复杂度 $O(n\log n)$。

CF1348E： 你们 hba 模拟赛认为这玩意比 T1 难？可以让某种不同颜色但是由同一种类的球构成的盒子中只有一个，否则可以调整法。此时答案显然只有两种，只需要考虑答案是否可以取到上界。考虑剩下的红球数量 $\bmod k=i$ 是否可行，用一个 dp 那么转移可以用前缀和优化或者 bitset 搞到 $O(n^2)$ 或者 $O(n^3/w)$。

QOJ8628： 不会啊。

20240915

noi.ac-3503

显然 $E=\dfrac{\sum c_i\prod_{j<i}p_j}{\prod p_i}$。考虑 $d_i=0$ 的部分分，可以用 exchange argument 交换相邻两个数的影响。贡献分别为 $c_x+p_xc_y$ 以及 $c_y+p_yc_x$，若 $(x,y)$ 比 $(y,x)$ 更优必然满足 $\dfrac{c_x}{1-p_x}<\dfrac{c_y}{1-p_y}$。按照这个进行排序即可得到最优顺序。考虑 $d_i$ 的限制，每次可以贪心选择当前能选择的关卡中的 $\dfrac{c_x}{1-p_x}$ 的最小值的 $x$ 立刻挑战。用一个小根堆维护能选择的，并查集维护合并即可。时间复杂度 $O(n\log n)$。

noi.ac-3513

加边次数固定，因此可以将 $x<y,x=y,x>y$ 三种情况中的一种的开销视为 $0$。不妨设 $x<y$ 的开销为 $0$。将问题稍作转变，考虑先确定加入 $m$ 条边后的图，然后给边标号，即确定加边顺序。对于图是一个边双的情况，考虑删去最后一次加入的边，然后有两种情况：

图仍然是一个边双。此时即为题目中 $x=y$ 的情况。
图是一条由若干个边双组成的链。此时即为题目中 $x>y$ 的情况。对两种情况分别转移即可。这一部分时间复杂度为 $O(n^2m^2)$。

对于图是一个连通图的情况，我们可以将图看成若干个边双连成的一棵树。考虑最终的图由点数分别为 $a_1,a_2,\cdots,a_k$ 的边双连接而成，则连边的方案数为 $n^{k-2}\prod_{i=1}^k a_i$。点的标号方案为，第 $i$ 个边双的最小点应小于第 $i+1 $ 个边双的最小点，避免算重。边的标号方案为，每个边双内部按原来的顺序，两两之间的顺序任意，树边的顺序任意，显然不影响题目中开销的计算。总时间复杂度 $O(n^2m^2)$。

P7831

先考虑 $-1$，就是无法走到一个环上。走到一个环上很难处理，考虑建立反图，改成能被一个环到达的点。在最开始没有入度的点的答案一定是 $-1$。可以用类似拓扑排序的思想删去这个点，并且访问遍这个点相邻的边，会牵扯到后面的点的入度情况。先考虑上一下 dp：令 $f_{u}$ 表示 $u$ 的答案，如果不考虑环每次转移就形如 $\max(r_{u,v},f_u-p_{u,v})\to f_v$。注意到 $f_v$ 一定是大的向小的转移。由于 $r$ 是取 $\max$ 的过程，一些点和边的初始值一定是某个 $r$。如果这条边的转移对象还没有值，就给赋值上当前的 $r$，剩下的边就随便走了。可以让所有边都按照 $r$ 排序。走不到环上的节点一定会被忽略，考虑当前的边确定值后可以拆掉一个环上的边，跑拓扑排序去找到这个环可以到达的所有点时，可以执行那个 dp，并且删掉这条边，表示这条边在后续的转移中没有用了。如果没有入度，就可以入队了。拓扑排序过程中，如果 $r$ 的赋值确实发生了，如果一条边会被删掉必须满足它无法走到环上，这条边还没有被删除所以它一定在一个环中。时间复杂度 $O(m\log m)$。

P7916

$k=2$ 考虑转对偶图最短路，这条路径代表割开的两部分分别为黑以及白。同样考虑对偶图，拓展到一般情况上，就是黑白分界线割成了若干部分，需要匹配一下若干部分，要求路径无交，也就是无相交仅包含的情况。把最外面一圈点拉出来跑一下最短路，匹配只会发生在下标奇偶不同的点对上。预处理所有的代价，用春测 t3 的套路跑一下区间 dp 就行了。时间复杂度 $O((nm)\log(nm)\sum k+\sum k^3)$。

UOJ821

注意到前缀 $\max$ 之间的东西会和前面的 $\max$ 值本身绑定在一起。所以对于 $a$ 可以只保留前缀 $\max$ 的值，现在就是要从小到大加入，要么新建石堆要么插入一个已有的。直接 dp 需要记录非空，无法接受。考虑有 $n$ 个石堆但是允许空堆的答案是 $f_n$，显然 $f_n=\prod\binom{cnt_i+n-1}{cnt_i}$，做一遍二项式反演就可以求出来答案。注意到 $\sum cnt_i=m$，本质不同的 $cnt_i$ 有 $O(\sqrt m)$ 个。所以可以对于本质不同的 $cnt_i$ 求 $f_n$，每个分开求复杂度都是 $O(\sqrt m)$，总时间复杂度 $O(n\sqrt m)$。如果要对于所有 $m$ 都求解，可以保留 EGF 以及容斥系数的多项式进行卷积。

ZR2997

暴力的判定要求满足形成单调栈。手玩发现合法序列没有 $231$。不难发现没有字典序限制的答案是 $\text{Catalan}(n)$。考虑确定一个前缀后的做法，有解当且仅当确定部分不存在 $231$ 且前缀存在 $i<j,p_i<p_j$ 并且 $[1,p_i)$ 并未全部在前缀中确定，因为这样必然有 $231$ 状物。从大往小加入数，考虑当前极长的前缀下降段 $len$，前缀相当于确定了一些数的决策。确定前缀后，答案是若干卡特兰数的乘积。而每一段就是被前缀划分出来的若干连续段，考虑确定出来 $a_i$ 能填入的连续段位置 $[l,r]$，对这玩意做一遍卡特兰数自卷积即可。注意到 $a_i$ 只能放到第一个连续段，操作过后会形成分裂。对于原来 $a_i$ 可以填的数，下界是 $a_1\sim a_{i-1}$ 的 $\text{mex}$，上界是第 $\min(i-1,\text{mex}-1)$ 大，容易树状数组上二分维护。对于卡特兰数自卷积，可以使用启发式分裂。时间复杂度 $O(n\log n)$。

20240916

hba 模拟赛 t2

小 T 有一个仅由 a, b, c 构成的字符串 S，他要将其改为 T 以送给小 Z。他能进行以下操作：花 $A$ 的时间将某个 a 改为 b ; 花 $B$ 的时间将某个 b 改为 c ;花 C 的时间将某个 c 改为 a 。小 T 只有 $maxT$ 个单位的时间。小 Z 是一个看重过程的人，你能告诉小 T ，有多少种操作序列能在规定的时间内将 S 修改为 T 吗？$|S|\leq 11$

注意到最小步数是好求的，最大步数容易求出，就是每个位置转一些次后疯狂跑 $A+B+C$，可以求最大步数。$f_{T,x,y}$ 表示用了 $T$ 步达到距离为 $1$ 的有 $x$ 个，距离为 $2$ 的有 $y$ 个，相同的为 $n-x-y$ 个的方案数。可以矩阵快速幂优化 dp。

20240917

hba 模拟赛 t3

小 T 有一个由 $n$ 个点构成的环，相邻两个点之间的长度都是正整数。有 $m_1$ 个如下限制：从顺时针第 $s_{1,i}$ 个点到第 $t_{1,i}$ 个点的距离至少为 $l_{1,i}$ 。有 $m_2$ 个如下限制：
从顺时针第 $s_{2,i}$ 个点到第 $t_{2,i}$ 个点的距离至多为 $l_{2,i}$。环上的距离定义为：沿着环上的边顺时针从起点走到终点所经过的长度。小 T 想问你，满足以上条件的环有多少种不同的长度？$n,m_1,m_2\leq 50$。

令 $0\to i$ 的距离为 $a_i$，且令 $a_n$ 为环的长度。计数的对象是 $a_n$。基础的限制条件为：$a_0=0,a_i+1\leq a_{i+1}$。先考虑 $s\to t$ 至少为 $l$，那么限制为：$s<t$ 时 $a_s\leq a_t-l$，否则在 $s>t$ 时 $a_s\leq a_t+a_n-l$。类似的，至多为 $l$ 就为：$s<t$ 时 $a_t\leq a_s+l$，否则在 $s>t$ 时 $a_t\leq a_s-a_n+l$。如果 $a_n$ 是定值，可以将所有 $a$ 看成差分约束的简单限制 $a_x\leq a_y+v$，容易 SPFA 判断是否有解。容易发现 $a_n$ 的有效值是一段区间，二分找上下界即可。

hba 模拟赛 t4

小 Z 喜欢折纸。她有一张 $n × m$ 的纸，每个格子都是黑色或白色的。每次小 Z 可以选择一条沿着格子边缘且平行于纸张边缘的直线作为对称轴折叠这张纸。小 Z 会将面积更小的那一部分向面积更大的那一部分折叠，且大的那部分坐标不变。重叠的两个格子必须颜色相等。则最后的结束状态一定是原纸张的一个子矩阵。问有多少种不同的结束状态。两个结束状态不同当且仅当他们不一样大，或者左上角的坐标不同。$n,m\leq 250$。

显然是可以将行与列分开做，两边的答案乘起来就是答案。预处理 $mx_i$ 表示 $(i,i+1)$ 的回文半径，$f_{l,r}$ 表示折成 $[l,r]$ 是否可行，枚举上一次的折点即可做到 $O(n^3)$。

QOJ7301

考虑直接 dp，前 $i$ 个三元组的最大值位置在第 $j$ 个，如果有多个最大值定义其在最左边，这个值为 $k$，且我们只确定了前 $i+j$ 个数的取值。这时的总贡献和，转移分为：

普通的继承最大值位置，容易 $O(n^2)$。
$f_{i,0,x}\to f_{i+1,*,\leq x}$，可以后缀和优化。
$f_{i,*,x}\to f_{i+1,2,>x}$，可以前缀和优化。

总时间复杂度 $O(n^2)$。

QOJ4815

树上背包有一个 trick 就是考虑按照 dfs 序进行 dp，如果不选一个子树就相当于从 $i+\text{subtreesize}(u)$ 进行转移，否则是 $i+1$ 也就是选了一个儿子。DFS 序优化树上背包主要是将合并变为插入来优化复杂度。考虑树上连通块问题也可以用点分治来做。每次统计经过根节点以及当前节点 $u$ 的连通块个数。在这个题中可以结合 dfs 序。对于 $rt\to u$ 的已选择后，前面的是一段 dfs 出栈序，后面的是一段 dfs 入栈序。区分完之后，在出栈序和入栈序上跑两遍背包即可。总时间复杂度 $O(nk\log (n/k))$。

T489103

懒得写了，但是好题。

先考虑给定 $S$ 以后怎么算 $f(S)$，需要找到一个好的刻画方式。我们考虑以 $1$ 为根 DFS 一遍整棵树，然后考虑贪心。每次贪心地找到所有路径中 LCA 最深的路径，如果这条路径上所有节点都没被访问过我们就将该路径上所有节点都设为被访问过并令答案加一，否则我们直接不管这条路径。

考虑方案数转期望，我们求出每个点有多大概率作为某个被选择路径的 LCA 出现过，然后把它们加起来再乘上 $2^{\frac{n(n+1)}{2}}$ 就是答案。那么怎么求呢？注意到对于一个点如果它的某个祖先被访问了，那么这个点也没有用了。因此我们可以将选择一条路径视作直接将这个子树吃掉，这样就可以 DP 了，我们设 $f_{u,j}$ 表示钦定了 LCA 在 $u$ 子树内的路径，还有 $j$ 个点没有被吃掉的概率，转移就将两个子树合并起来即可，设 $u$ 为 $v$ 的父亲，那么显然 $f_{u,0}$ 只能转移到新的 $f_{u,0}$，而对于 $i\ne 0$，$j\in[0,siz_y]$，$f_{u,i}$ 和 $f_{v,j}$ 有 $\dfrac{1}{2^{ij}}$ 的概率转移到 $f_{u,i+j}$，有 $1-\dfrac{1}{2^{ij}}$ 的概率转移到 $f_{u,0}$。树上背包求一下即可。最终 $f_{i,0}$ 即为 $i$ 作为某条路径 LCA 出现的概率。时间复杂度 $O(n^2)$。

T272090

这不是我们 CSP-S2019 D2T3 吗。将 $a_i$ 号点到 $i$ 号点的路径 $L$ 提出来专门考虑。

对于编号为 $a_i$ 的点：其所连的所有边中，$L$ 上与 $a_i$ 相邻的边必须是 $a_i$ 第一个操作的边；
对于编号为 $i$ 的点：其所连的所有边中，$L$ 上与 $i$ 相邻的边必须是 $i$ 最后一个操作的边；
对于 $L$ 路径中间的点：在 $L$ 上靠近 $a_i$ 端的边操作之后，下一个操作的一定是 $L$ 上靠近 $i$ 端的边。

可以对于每个点连接的所有边开一个并查集来判定当前局面的解是否存在。可以用以下三条来判定：

若存在 $i\ne j,a_i=a_j$，必然不合法。
上述第二条限制成环，或者第一、第三条限制与第二条限制冲突时，必然不合法。前者利用并查集可以非常方便的解决。后者简单判断即可。
如果存在一个点 $x$，通过上述的若干限制，从第一步操作一直限制到最后一步操作，且还存在与 $x$ 相连的边并未被操作，则一定不合法。

而此时只要满足限制条件，最终局面一定会满足要求。接下来考虑如何计算方案数：注意到当我们对每个点都确定好其所有相连的边之间的操作顺序之后，我们就可以确定出最终局面，并且这两者是互相一一对应的关系。这就意味着我们只需要计算每个点所连的边，能有多少种相对操作顺序，将所有点的方案数相乘即可得到最终的结果。而每个点所连的边的相对操作顺序，其实就是第一部分计算限制条件时，有多少条可以自由安排顺序的链，方案数就是这个数的阶乘。

T406734

倒着做启发式合并。离线询问，时间倒流，先求出每次断边操作哪边的连通块更小。接着再时间正流，每次断边时，暴力分裂出较小的连通块。分裂连通块时，需要对每个连通块都维护线段树来查询每个颜色的情况，并且需要在小联通块中查询操作后的颜色。维护每个点变成了什么，可以在线段树叶子上挂一个并查集。对线段树进行“区间改为 $v$” 时，将区间内的叶子上挂的并查集全部合并到 $v$ 上。查询某个点颜色时进行 findfa，看现在挂在哪个叶子上即可。时间复杂度 $O(n\log^2n+q\log n)$。

QOJ7302

有病题。官方题解。

T404285

注意到只有最后一次赋值操作是有用的，相当于从若干个赋值中选一个作为 $x$ 的初值，然后对于乘法跑一个背包。注意到找到 $p$ 的原根 $g$ 后可以转化为加法操作。每次就是找到所有 $a_i=1$ 的，对 $a_{(i+x)\bmod p}$ 赋值为 $1$。每次事实上只需要找到有意义的转移进行暴力，二分哈希即可，哈希需要树状数组维护，每次找到一个不同位置花费 $O(\log^2p)$ 的时间，所以总时间复杂度 $O(p\log^2p)$。

20240918

不知道哪里看来的题

给定一棵 $1$ 为根，$n$ 个点的树，对于一个在点权上的 $n$ 的排列 $a_i$，定义 $k$ 为有多少个 $u$ 使得对于所有祖先 $v$ 都有 $a_u\leq a_v$，定义这个分配方案的权值是 $m^k$，求所有 $n!$ 种分配方案的权值和，$n\leq 3000$。

事实上很难直接计算，考虑用容斥。钦定 $k$ 个点成为了前缀 $\min$，我们赋予它的权值为 $(m-1)^k$。这样对于一个实际上有 $k'$ 个点的方案，它的贡献为 $\sum_{k=0}^{k'}\binom{k'}{k}(m-1)^k=m^k$，这样就巧妙的化为对于所有集合 $S$ 求出 $S$ 集合为关键点时，$f(S)=(m-1)^{|S|}\times \text{count}(p)$ 的和。考虑在此基础上树上 dp，注意到转移的时候并不关心具体 $|S|$ 的大小，所以合并进新的点 $u$ 时可以直接乘上 $(m-1)$。直接设计 $f_{u,i}$ 表示讨论范围为 $u$ 的子树，$p$ 序列也只考虑 $1\sim \text{subtreesize}(u)$，此时满足 $\min(S)=i$ 的 $f(S)$ 的和。这样做是因为这棵树有 $fa(u)<u$。具体 $\text{count}(p)$ 就是考虑从小往大填。转移就是树上背包，合并一下两个排列的贡献，注意要从值的角度来进行合并。时间复杂度 $O(n^2)$。

QOJ4220

考虑一个 $3n$ 个点的环，共有 $n$ 种颜色，每种颜色恰有 $3$ 个点。对于每种颜色，需要选择两个点，画一段不经过未选择点的圆弧。求圆弧两两不交的方案数。$n\leq 10^6$。

执行完第一种颜色的选择之后就可以断环成链，$f_i$ 表示前 $i$ 个点最多匹配多少种颜色以及其方案数，转移是 $O(1)$ 的。注意，执行完第一步必须的操作之后或许就有很优美的性质，比如 CSP-S2021 回文。

T378411

启发式分裂。注意到合法的区间具有一定的单调性。具体而言，考虑任一不合法的区间，一定存在某种元素出现次数过少，此时包含该元素的所有子区间均不合法。先判断 $[1,n]$ 是否合法，合法则更新答案，否则找到一种出现次数不足的元素，递归到每个子区间计算答案。对于每次子区间，可以启发式分裂做到 $O(n\log n)$。

QOJ4812

考虑 $f_{i,j}$ 表示当前总和为 $i$，结尾为 $j$ 的贡献和，显然 $f_{i,j}=cf_{i-j,j-1}+f_{i-j,j+1}$。这样是 $O(n^2)$ 的。直接上根号分治。注意到总和一定且很小，并且 $|a_i-a_{i+1}|=1$，考虑对 $a_1$ 大小进行分治，令 $a_1\leq B$ 时跑上面那个 dp，这样结尾就不会很大，不会超过 $O(\sqrt n)$，这部分是 $O(n\sqrt n)$ 的。$a_1>B$ 时就不会碰到 $0$，可以抛去绝对值的限制，可以将 $a_1$ 视为 $0$，最后整体加上一个常数。并且长度是 $O(n/B)$ 的。如果 $g_{i,j,k}$ 表示长度 $i$，$\sum (a_t-a_1)=j,a_i-a_1=k$，这是 $O(n^{8/5})$ 的。但事实上可以倒着 dp，每次在开头加上一个数而不是在结尾，考虑对后面的影响——整体向上或者向下平移 $1$，同时长度不会很大，状态记录一下当前和即可。每次转移就加一个 $a_1-1$ 或者 $a_1+1$，但是要考虑 $\sum (a_t-a_1)$ 的变化量就是 $-i$ 或者 $i$。$g_{i,j}$ 记录长度 $i$，和是 $j$，就可以做到 $O(n\sqrt n)$。

QOJ4814

题意就是多次询问将给定点集的虚树至少要拆成多少条链来覆盖所有的关键点。事实上可以变成最大化问题，分配一堆链 $p_i\to p_{i+1}$，需要给每个点确定一条链，一条链有贡献当且仅当路径上的所有点都被选入了这条链。相邻链的共顶点可以覆盖两次。先对所有关键点建立虚树，在 $t_i=\text{lca}(p_i,p_{i+1})$ 处考虑这条路径。令 $f_u$ 表示 $u$ 子树内的答案，那么相当于考虑 $t$ 是否被选入 $p_i\to p_{i+1}$。那么考虑令 $x=p_i,y=p_{i+1}$，就是对所有 $x\to y$ 的路径上的点邻接的所有点求 $f_v$ 的和再 $+1$ 对 $f_u$ 取 $\max$。令 $g_u=\sum_{v\in\text{son}(u)}f_v-f_u$。转移重新整理成路径上的 $g_v$ 和，再加上两个方向的 $f_{v_1},f_{v_2}$，需要特判 $t,p$ 共点的情况。对 $g$ 做前缀和后可以树状数组维护。时间复杂度 $O(n\log n)$。

QOJ4816

一个方案合法当且仅当点权 $\geq i$ 的只形成一个连通块。这种情况考虑 $f_{u,i,0/1}$ 表示仅考虑 $u$ 的子树，$a_u=i$ 且是否存在 $v\in\text{subtree}(u)$ 使 $a_v>a_u$。显然 $f_{v,j,0}$ 只能往比 $j$ 大的转移，$f_{v,j,1}$ 只能往比 $j$ 小的转移。都可以用前缀和优化来做。注意询问之间是相互独立的，可以使用换根 dp 的思想维护一个子树补 $g_u$，可以用 $f,g$ 合并求出 $a_u=y$ 的答案。时间复杂度 $O(nm+q)$。可以子树补加子树内维护一个点做根的状态。

20240919

不知道哪里看来的题

最小直径生成树，但是边权是 $1$。朴素的 $O(n^3)$ 就是枚举直径的中点或者中点的边。bitset 优化可以 $O(n^3/w)$。

贴个 full solution

求绝对中心需要先求出全源最短路，由于边权全为 $1$，有复杂度为 $O(\frac{n^3}{\omega})$ 的算法，后面再介绍。记 $dist_{u,v}$ 表示 $u,v$ 之间的最短路，$far_u=\max_vdist_{u,v}$，首先 $far_u$ 最小的哪些点是绝对中心的候选点，绝对中心还可能是一条边的中点，枚举边 $(u,v)$，中点离所有点的最远距离为：

\[\max_{k=1}^n\min(dist_{u,k},dist_{v,k})+0.5 \]
由于 $u,v$ 是相邻的，所以 $\forall k\in[1,n],|dist_{u,k}-dist_{v,k}|\le 1$，推出这个最短距离大于等于：

\[\max_{k=1}^n\max(dist_{u,k},dist_{v,k})-0.5=\max(far_u,far_v)-0.5 \]
所以只有当 $u,v$ 同时为绝对中心候选点时 $(u,v)$ 的中点才可能成为绝对中心，在此前提下这条边的中点是绝对中心当且仅当不存在 $k$ 使得 $dist_{u,k}=far_u$ 和 $dist_{v,k}=far_v$ 同时成立。对每个点 $u$ 预处理一个 bitset 表示哪些 $v$ 满足 $dist_{u,v}=far_u$，判定 $(u,v)$ 中点就把两个 bitset 按位与，再用 bitset::none() 检验是否全 $0$。

关于全源最短路，先对每个点 $u$ 预处理一个 bitset 表示 $u$ 和哪些点相邻，然后枚举起点进行 BFS，在扩展点 $u$ 的时候，需要快速找到哪些点和 $u$ 相邻且还没有入队，这可以用 bitset 实现。

以 $O(\frac n{\omega}+popcount)$ 的复杂度遍历一个 bitset $bits$ 中所有的 $1$ 方法如下：
for(int i = bits._Find_first(); i != bits.size(); i = bits._Find_next(i))
复杂度 $O(\frac{n^3}{\omega})$。

不知道哪里看来的题

$m=0$ 或者 $m=n$ 的情况是平凡的。注意到宇宙射线的代码就是在 Floyd 中不考虑 $>n-m$ 的点作为中转点。考虑让 $1\sim n-m$ 的点作为白点，$n-m+1\sim n$ 作为黑点，那么实际上考虑连通性时所有黑点之间的边是没有用的。那么考虑每一个极大连通块作为计数对象，令 $h_{x,y}$ 表示有多少 $x$ 个白点，$y$ 个黑点的极大连通块的连边方案数，有了 $h$ 可以考虑 $ans_{x,y}$ 为 $x$ 个白点 $y$ 个黑点的答案，每次枚举 $0\leq x'\leq x,0\leq y'\leq y,x'+y'>0$ 作为新一个极大连通块，容易做到 $O(n^4)$。$h$ 考虑经典的连通块容斥技巧也可以 $O(n^4)$。

QOJ6119

注意到添加括号的操作数量是确定的。因为一定只会补足某一种括号，直到两种括号数量相同。如果加多了一定会形成额外的匹配，这样是不优的。如果左括号比右括号的数量少，就需要在最后添加左括号。考虑贪心确定一个左右括号数量相等序列的答案。事实上可以直接看成类似冒泡排序，消逆序对的过程。对于每一个前缀贪心做，考虑每个前缀，如果右括号数量多于左括号，则将最后一个右括号通过与非前缀中的数交换变为左括号。多次交换的影响是整体右移，这样做一定是合法且步数最小的。执行这个算法后，考虑第 $i$ 个右括号往后移动了多少位，令前面有 $c_i$ 个左括号，那么它移动的次数就是 $\max(0,i-c_i)$，求和即可。问题就是，右括号视为 $1$，左括号视为 $-1$，求所有的前缀和与 $0$ 的 $\max$ 的和即可。使用分块维护可以做到 $O(n\sqrt n)$。

QOJ5367

计数问题事实上可以去找容易刻画成 dp 的判定条件。考虑。令 $l_i=\text{lca}(p_i,p_{i+1})$，判定的充要条件有任意 $l_i$ 是 $l_{i+1}$ 的祖先。那么 $l_i=1$ 的是一段前缀，我们要求 $p_i,p_{i+1}$ 不同时在 $1$ 的某个同一子树内。我们扫这个 $p$，如果最早相邻的 $p$ 出现在同一个子树内，直接进入 $l_i$ 的子问题。当然进入这个子问题的合法条件就必须有这个子树之外的点都已经在 $p$ 中都填写过了。这些 $l_i$ 就几乎构成了从底到根的路径。底下是什么是不确定的，可以考虑从顶上往下 dp。状态的转移就分为将 $l_i$ 保持不变或者向下移动。

直接 dp 考虑 $f_{u,i}$ 表示 $u$ 子树中，已经有 $i$ 个在以前出现过，也就是 $\sum [l_j\text{ is the ancestor of }u]=i$。注意到计数的对象是形如：【$u$ 子树外的一个具体点标号，或者一个 $u$ 子树内的点】。且 $u$ 子树之外的部分已经合法的方案数。向上考虑合并出 $\text{lca}$ 时，这些点都是等价的。事实上这是意味着有一些出现过的点在 $u$ 的子树之中。考虑转移时只能向一个儿子转移这些 $l_i$，那么我们先构造剩余节点的排列，再考虑 $v$ 子树中有多少个点被选。对于一个点分为两类：之前染色过的，以及在 $u$ 处合并的。我们的计数对象是不关心向下转移的那个 $v$ 中具体转移到哪个点上。对于在 $u$ 处合并的不能相邻。可以容斥计数：$g_{i,j}$ 为 $i$ 个之前出现过的，$j$ 个 $u$ 处出现过的排列方案数，这 $i+j$ 个数是互相区分的。容斥的转移细节是值得考虑的，可以让 $g$ 的下标存连续段个数，但是如果一个事实上存在相邻的方案，它的贡献和都会是 $0$。

统计答案在 $l_i$ 的链底统计。时间复杂度 $O(n^5)$。

CF2005E2

~~倒序进行 dp，$f_{i,j,k}$ 表示 $(i,j)$ 为左上角，$k$ 为当前操作编号，是否可以赢。可以 bitset 优化，复杂度 $O(n^3/w)$ 直接过了。~~

$a$ 出现多次时一定会输，注意到有单调性，可以维护最小的奇数 $k$ 以及偶数 $k$，也就是定义域值域互换的套路做到 $O(n^2)$。

QOJ8578

韩语谁看得懂哦。

给定序列 $a_i$，每次选择一个 $1\leq i< |a|$ 满足 $a_i=a_{i+1}$，然后删除 $a_i,a_{i+1}$，并在同样的位置插入 $a_i+1$。你可以对序列进行任意次操作，你希望最大化最终序列中所有数的最大值。定义上述问题的答案为 $f(a)$。给定长为 $n$ 的序列，有 $q$ 次操作，每次操作是以下二者之一：

$\texttt{1 l r}$ ：输出 $f(a_{l\sim r})$的值。

$\texttt{2 p v}$ ：令 $a_p\to v$。

$n,q\leq 10^5,a_i,v\leq 10$。

考虑用连续段的方法来描述这个序列。需要讨论每一段长度 $c_i$ 是否为偶数。每次找到最小值，如果 $2\mid c_i$ 直接将它变为 $c_i/2$ 个 $x_i+1$。否则划分一个奇数的中点在中间是一定消不掉的。也就是变成两个独立的 $(c_i-1)/2$ 个 $x_i+1$。这样的操作轮数一定是 $O(\max(v))$ 的。线段树维护的话，如果出现 $212$ 状物，一定就要把中间的缩了。线段树维护缩段进行一些操作之后的样子，只会剩下 $O(v)$ 个段。

QOJ8793

zr 出题人玩原神了。直接模拟，一共有三种：一个电脑重新可用，一个人找到电脑，一个人活了。考虑用事件来描述，并且用小根堆来维护每个事件。直接维护所有事件是 $O(n^2)$ 的。对于人，我们只关心最近的电脑；对于电脑，我们只关心正反两个方向最近的两个人。考虑具体的影响：

人出现，会改变该运动方向上最近的电脑的人。
电脑出现，改变两边的人的最近电脑。
人到达电脑即电脑消失，会改变两边的人的最近电脑。

这样总事件数量就是 $O(n)$ 的。
考虑如何维护事件，只需要找到某个位置的左边右边的第一个电脑/人是谁即可，可以加偏移用 set 维护。总时间复杂度 $O(n\log n)$。

不知道哪里看来的题

考虑一个 $n\times m$ 的网格图，需要用 $1\times 2$ 的多米诺骨牌来覆盖，要求不存在一个点被骨牌顶点覆盖 $4$ 次。求合法的覆盖方案数。$n,m\leq 10^7$。

坏题，不写。

不知道哪里看来的题

给定一棵 $n$ 个点的树，每一条边都有 $1/2$ 的概率长 $1$ 或 $2$，求出直径期望。$n\leq 60$。

直接 dp 套 dp 啊，$f_u$ 表示 $u$ 的最长链，$g_u$ 表示 $u$ 子树内的直径。那么设计一个 $f_{u,x,y}$ 表示 $f_u=x,g_u=y$ 的概率。转移时维护 $g_{u,y,y',k}$ 表示 $u$ 子树中 $u$ 向下延的最长，次长链分别为 $y,y'$ 的概率，要求子树直径 $\leq k$。容易树上背包做到 $O(n^5)$。

20240920

noi.ac-3523

事实上可以递推后手必胜的 $n$。从 $n=0$ 出发，不断去找最小的后继 $n'$ 使得 $n'-n>\text{digitsum}(n')$。这样做可以找到所有的后手必胜的 $n$。可以写出如下的暴力：

for(;m<n;){ll d=0;for(;;){d+=10;if(d>digitsum(m+d))break;}m+=d;
}

用数位 dp 加速这个过程。发现进位是烦人的，对于一个 $n$，我们从后往前找到第一个极长的 $9$ 的连续段，长度为 $k$，令 $n=t\times 10^i+l$，其中 $t$ 的数位和为 $j$ 且结尾的极长 $9$ 连续段长度为 $k$。令这个为 dp 状态，$f_{i,j,k,l}$ 表示下一个 $n'\ge(t+1)\times 10^i$。存的是 $n'-(t+1)\times 10^i$。转移考虑 $l$ 的第一位拼上什么即可转移，对于 $i\leq 3$ 可以暴力处理。

LOJ3406

用点双分析，考虑对图建立圆方树。让猫的起点是 $a$，就让整个图的根是 $a$。作为猫，我们希望让 $b$ 一直往下走，直到没有出路。首先 $a$ 不是割点且不是 $1$ 度点时，且不存在一个必胜点时一定是必败的。进一步考虑猫的轨迹希望都走在割点上，不然 $b$ 就可以直接飞走。所以第一步一定是走到 $b$ 方向的一个更近的割点。性质是圆方树上度数大于 $1$ 的圆点是割点。事实上在确定根后，只关心 $b$ 所在的子树。每次猫的移动轨迹是跳过一个方点，到达一个与当前点在原图相邻的圆点。考虑树上 dp 表示 $f_u$ 为猫猫在 $u$ 时是否可以让 $b$ 被抓住。转移对于圆点考虑子方点的所有子圆点都在原图必须与 $u$ 相邻，不然就飞了。换根维护一个 $g$ 表示范围为子树补的可行性。如果存在一个点满足到另外任意一个点都是好的，那么猫可以先到这个点，所有询问都是 Yes，否则树上倍增一下 $b$ 在猫方向的哪个子树即可。求 $g$ 的意义在于判断是否存在一个必胜点，以及在最后询问时找到合理的范围。

P11073

Genshin OI 唯一的正经题。缩点成 DAG 是显然的，考虑缩点后的图为图 $G$，如果用 bitset 维护可达性就没有用好询问的性质。注意到拓扑序的性质是只有可能拓扑序小的通向拓扑序大的。考虑用如下判定：建立反图 $H$，那么判定的充要条件就是在 $G,H$ 中可以 $u$ 都可以到达比自身拓扑序大的所有点。考虑在拓扑排序的过程中按照拓扑序倒序添加点。不合法的必要条件是在加点的某个时刻，当前存在至少两个点没有入度。然后发现这个是充分的，因为可以只留下一条入边，剩下的树是符合条件的。时间复杂度 $O(n+m)$。

T402404

注意到所谓的对合排列就是逆排列等于原序列，而逆排列与原排列的逆序对数量相同，所以逆序对数为 $k$ 的对合排列数量奇偶性等于逆序对数为 $k$ 的排列数量奇偶性。考虑怎么求逆序对为 $k$ 的排列数量奇偶性，朴素 dp 加上前缀和优化是 $O(n^3)$ 的。考虑放置到第 $t$ 个数，求出此时的 $f_t(x)$ 的生成函数。首先将 $f_t(x)$ 前缀和，然后对 $\ge t$ 的 $f(x)$，将其减去 $f(x-t)$ 的系数。直接乘的式子就是依次乘上 $\dfrac{1}{1-x}$ 以及 $(1-x^t)$，可以使用乘法交换律把所有的 $\dfrac{1}{1-x}$ 换到前面。由于只关心这些除的操作之后 $[x^n]f(x)$ 模 $2$，显然是 $\binom{n+x-1}{x}$，可以使用 lucas 定理 $O(1)$ 得出奇偶，对于后面的模拟乘 $(1-x^t)$ 可以用 bitset 模拟移位。复杂度 $O(n^3/w)$。

CF1415F

加强版 qoj4906，以后再做。

对于所有事件按照时间排序，考虑一个 $O(n2^n)$ 做法：在一开始就确定一个球是分身接的还是一个人接的，对于分身接的点必须提前到。一个个点模拟人接的点，判定是否可以在规定时间之前放下一个分身点。事实上只考虑放分身点的位置，由于人接的点是时空确定的，可以在转移中间作为判定能否转移的条件。这个过程可以用 dp 加速。设 $f_{i,t}$ 表示 $t$ 时间在 $i$ 号球位置放分身是否合法，这个没法做，但是可以定义域值域互换，改成 $f_i$ 表示最小时间在第 $i$ 个球放分身点，且 $i-1$ 是分身接下的，同理设 $g_i$ 表示最小时间到第 $i$ 个球放分身点，且 $i-1$ 是本人去接。转移枚举上一个放分身点的位置 $j$，可以通过简单的预处理得出可能的 $j$ 的最小值，要求 $j+1\to i-1$ 都是本人去接，大概需要暴力判 $i-1$ 的转移。时间复杂度 $O(n^2)$。

T413297

先做没有限制的情况：考虑对于算第 $w$ 位的贡献，令 $g_w(a)$ 表示序列 $a$ 的第 $w$ 位权值是否为 $1$，若为 $0$ 权值为 $1$，否则为 $-1$。此时只关注最低 $w$ 位。考虑找到 $a$ 下标偶数中第一个 $p$ 使得 $a_p\neq 0$，让这个序列与 $a_{p-1}\oplus 2^{w-1-p}$ 进行配对，这些 $g(a)$ 的和是 $0$，没得配对的序列有 $p=2^{\lceil\frac{n}{2}\rceil}w$ 个，这些的第 $w$ 位都是 $0$，总共序列数是 $q=2^nw$ 个，所以低位符合条件的有 $\dfrac{p+q}{2}$，乘上高位的 $2^{(m-w)n}$ 种就对了。

考虑有限制的情况。直接分讨 $\sum g(a)$ 就是了。光速幂启动，$O(\sqrt{\text{mod}}+m)$。

AT_arc083_d

二选一模型 直接上建图啊。

考虑确定一个球是被 $A$ 还是 $B$ 收的之后可以计数，感性理解下有解的 $A,B$ 的分配方案很少。同行不能有多个 $A$，同列不能有多个 $B$。对于该方向遮挡它的障碍连有向边，会得到内向树森林，它的拓扑序方案数就是 $\dfrac{(2n)!}{\prod siz_i}$。每个点对于一个方向的障碍都是确定的。假如确定了一个点的方向即连边，其实可以确定接下来一些点的连边。一个分配方案的充分必要条件是每行每列都有且仅有一个点选择对应方向。事实上对于每个球建边是没前途的。考虑每个位置是 $(x_i,y_i)$，那么就让 $(x_i,y_i+n)$ 连无向边。这样就形成了 $|V|=|E|=2n$ 的二分图。每个连通块是独立的，并且如果连通块不是基环树森林就一定无解。那么给定这张图后，一个点需要选择有且仅有一条边，考虑给选择这个点的边定向向这个点，我们要求每个点的入度都恰好为 $1$。此时回到最开始选择 $A/B$ 的问题就好了。首先环上的选点方案只有两种，其次挂的一堆树都是唯一的，也就是外向。确定 $A,B$ 分配方案后再建立最开始提到的那个图，直接计算拓扑序即可。

代码懒得写了。时间复杂度 $O(n)$。

AT_agc061_c

构造双射，考虑对于一个登记顺序，反向确定每个人选了 $a$ 还是 $b$。显然可以线性扫一遍时间轴，维护一个 $p$ 表示当前选到了前 $p$ 个人，看当前位置是否匹配上 $p+1$。注意到出现 $b$ 选了和选 $a$ 没影响时就没必要选 $b$ 了。反正就是能早匹配就早匹配。每次选择就形如：选择 $a$ 或者在 $(a,b)$ 已经有选的时候选 $b$。可以使用容斥，钦定人的集合 $S$ 选了 $b_i$ 但是 $(a_i,b_i)$ 中都没有点，记这个方案数是 $f(S)$。显然存在 $S_i,S_j$ 有交集时 $f(S)=0$，考虑令 $l_i$ 表示最小的 $b_j\ge a_i$，$r_i$ 表示最大的 $j$ 使 $a_j\leq b_i$。则 $S$ 控制不到的人就是未被 $[l_i,r_i],i\in S$ 覆盖的所有人，此时 $f(S)=2^{n-\sum (r_i-l_i+1)}$。考虑让 $S$ 的元素都是区间，对于 $S$ 的右端点为 $i$ 的放在一起 dp 即可，可以前缀和优化。时间复杂度 $O(n)$。代码是 agc 那样的短哦。

P10283

将所有 $01$ 串插入 trie 树，那么我们 dfs，必须将所有棋子扔到叶子节点上。维护 $f_u$ 表示把 $u$ 上的多余棋子往下移动的最小代价，$u$ 的平凡情况是对于一个叶子节点建立两个子节点并均摊，或者对于缺恰好一个叶子的加入一个空节点。否则转移就是两边的 $\min$ 再加 $1$，每次沿着最优路径更新一下即可。由于答案的量级是 $O(n\log n)$ 的，这样的总复杂度也是 $O(n\log n)$。

P7152

又是双射题？没救了。考虑对合法划分计数，这显然是双射。一个合法的划分 $\lbrace(l_1,r_1),(l_2,r_2),\cdots,(l_k,r_k)\rbrace$ 要求任意 $s_{l_i}=s_{r_{i+1}}$，并且每个连续段中间没有相邻相同的。啥都扔进状态里就行，$f_{i,x,y,z}$ 表示划分到 $i$，$s_{l_{k-1}}=x,s_{l_k}=y,s_{r_k}=z$ 的方案数，转移时我们不给最后一段锁死，枚举当前位，看是否封死上一段。时间复杂度 $O(nm^4)$，$m=4$ 表示字符集大小。

P10285

省流：选定合适的参考系，并且要逐个考虑研究对象。

显然有一个 dp 是 $f_{S,i}$ 表示已经放置了集合 $S$ 的波特，放的最后一个是 $i$ 的最小时间。波特在动是不好的，考虑到波特是相对静止的，让人是变速的。让波特成为参考系，那么人的速度有 $(k+1)/k$ 正向移动和 $(k-1)/k$ 反向移动两种，激活点的速度只有 $(k-1)/k$ 反向移动。这个题三个研究对象就很烦，但是可以分开处理。转移的细节是访问到 $f_{S,i}$ 的具体值后，二分一个最近的激活点表示最小等待的时间。在转移的过程中，只考虑人的变化。可以预处理走 $i$ 个单位 $L/R$ 的正方向的距离的最小时间，需要考虑人反向走的时间。这个值是 $dis_j$ 的话，每次转移就形如 $f_{S,x}+dis_{x\to y}\to f_{S\cup y,y}$。时间复杂度 $O(R2^R\log n+R^22^R)$。

AT_arc176_c

从小到大填，考虑某种边权连的所有边，分讨下就行。

P6916

喜欢我们大模拟吗。move 操作考虑暴力维护每一组碰撞，维护当前剩余动能以及在一次碰撞内可以释放的动能。在运动的一定是一个连通块，$q$ 很小可以暴力维护。转化为机械能的移动可以暴力维护，可以向右找，拓扑排序维护出拓展的连通块。

CF2009G3

没意思。给 $a_i$ 减去 $i$，显然可以求出每个长为 $k$ 的子串价值，这个就是 $k$ 减去区间众数数量，可以用带 $\log$ 的东西维护，这个长度为 $n-k+1$ 的序列记为 $b$。那么 $f(l,r)=\min_{i=l}^{r-k+1} b_i$，对于所有子区间求和就拿单调栈维护区间加，线段树维护历史和即可。

20240921

P9129

秒了。显然可以容斥成 $\leq B$ 减去 $\leq A-1$ 的方案数。一眼区间 dp，考虑讨论的是序列的下标 $[l,r]$ 范围。只讨论 $\leq B$ 的情况：记录 $B$ 的长度为 $k$，那么 $|x|<B$ 可以直接组合数算，需要重点关注 $|x|=B$ 的情况。我们考虑一个 deque 加进去是什么样子的：L1,L2,R1,L3,R2,R3,R4,L4 导出到 $x$ 的样子就是 L4,L3,L2,L1,R1,R2,R3,R4。由于 $|x|=k$ 是定长的，可以考虑 $x$ 两端往中间填，维护两个指针 $p,q$ 表示 $x$ 的 $[1,p],[q,k]$ 已填。在数列中的填数顺序理应是倒序的。在此基础上考虑与 $B$ 去匹配，直接分别维护两个状态，前缀 $[1,p]$ 是 $<B[1:p]$ 还是 $=B[1:p]$，后缀 $[q,k]$ 是 $>B[q:k]$ 还是 $\leq B[q:k]$。记录这个方案数是 $f_{l,r,p,q,0/1,0/1}$，因为是区间 dp，所以转移可以做到 $O(1)$。统计答案就是考虑所有的 $p=q-1$ 进行合并有效状态即可。时间复杂度 $O(n^2\lg B^2)$。

UOJ747

注意到找到一个点让所有人聚合一定是最优的。因为网友和人见面之后可以一直跟着直到所有人在一起，可以到最后面基。在点上聚合是容易的，对于 $k+1$ 个点都跑一遍单源最短路。在边的中点聚合需要考虑从哪个端点进入，令两侧分别为 $x_i,y_i$，答案是有关于 $w,\max(x),\max(y)$ 的。浅浅推下式子，答案是 $\dfrac{w+\max(x)+\max(y)}{2}$，因此只需要最小化两侧的 $\max$ 之和，所有人的 $x$ 拉出来排序，枚举一个前缀选 $x$，后缀选 $y$ 即可。时间复杂度 $O(kn\log n+mk\log k)$。

UOJ748

称原串为 $S$。考虑判断一个长度 $n+2t$ 的串 $T$ 是否合法，对于这个 $01$ 串，采用以下的匹配形式：从左往右扫字符串 $T$，维护一个指针 $p$ 表示 $S$ 与 $T$ 当前匹配到的位置。如果这一位能匹配上，$p\leftarrow p+1$。若不能匹配，如果是 $0$ 就扔到栈里面，如果是 $1$ 就弹栈顶，这代表一个匹配。注意，如果栈为空也有可能合法。此时让 $p$ 回退到最大的 $g$，使得在 $g$ 之后的存在一个没有匹配的 $0$，也就是把 $g$ 往后的都视为，尚未匹配。dp 加速这个过程：$f_{i,p,siz}$ 表示 $T$ 的指针扫到 $i$，$S$ 匹配位置为 $p$，栈的大小为 $siz$ 的方案数。答案就是 $f_{n+2t,n,0}$。

P8100

每次事实上是交换两个相邻差为 $1$ 的数。注意到差 $\ge 2$ 无论如何都无法改变相对位置的偏序关系。这种存在偏序的方案事实上可以考虑建图，$u\to v$ 表示 $u,v$ 不可以交换，那么一个合法的拓扑序就唯一对应一个原序列。考虑怎么做这个拓扑序计数。注意到奇偶性相同的位置一定在图上可达，可以连上边，那么可以看成是两条链互相连边，$f_{i,j}$ 表示拓扑序已经有奇链前 $i$ 个偶链前 $j$ 个的方案数即可。看是否可以转移到 $f_{i+1,j},f_{i,j+1}$ 即可。时间复杂度 $O(n^2)$。

CF1889C2

直接 dp，考虑 $f_{i,j}$ 表示前 $i$ 个点删了 $j$ 条线段且 $i$ 不被覆盖时，前 $i$ 个点最多有多少个点不被覆盖。枚举上一个不被覆盖的点 $t$，记录 $w(t,i)$ 时有多少线段使得 $t<l\leq i\leq r$，那么显然有转移 $f_{t,j-w(t,i)}\to f_{i,j}$，注意到 $0\leq w\leq k$ 才是有意义的。直接对于所有 $t$ 按照 $w$ 分成 $k+1$ 段，维护 $k+1$ 个线段树表示 $f_{i,j}$ 的区间 $\min$ 即可做到 $O(nk^2+n\log n)$。

CF1889D

这是一道图论题。考虑用有向图模拟过程，对于每个栈连 $i\to top_i$，当前棋子在 $u$，在这个内向基环树上走一步到 $v$，然后将 $u$ 的出边更改为下一个 $top_u$，直到走到某个没有出边的点。用好内向基环树的性质，如果当前 $u$ 在这个基环树的环上，那么一定会走一圈回到 $u$，但是这些环上的点的边都会更改一轮了。可以直接把环消了然后对所有环上的点进行一轮迭代，不断消环直到图变成森林，每个点的答案显然就是对应内向树上的根。时间复杂度 $O(n+\sum k_i)$。

CF1870E

显然有 $f_{i,j}$ 表示 $i$ 为最后一个子段结尾时异或和为 $j$ 是否可以。转移可以做一遍前缀 $\max$，但是由于区间权值是 $\text{mex}$，所以可以考虑缩减有用的区间数量，对于若干个 $\text{mex}$ 相同的区间，保留被包含的显然不劣。这样的区间个数是 $2n$ 的。结论的正确性来自于每个点作为端点时的有效区间个数只有左右最多各一个。对于这些区间做 dp 的复杂度就是 $O(n^2)$。还有一种做法是 $to_{i,j}$ 表示最小的 $r$ 使得存在 $t\ge i$ 使得 $\text{mex}(a_{t\sim r})=j$，考虑扫描线序列，$f_i$ 表示最小的 $j$ 使得这些区间的右端点为 $j$，异或和为 $i$，bfs 一遍就够了。

20240922

CF1764H

环上操作显然是诈骗，可以倍长一下。对于没有被影响的元素可以扫描线维护。注意到每个元素的存活不与别的有关，只与所有的操作区间有关。对于一次操作我们考虑贡献放到左端点上。拆下贡献，考虑颜色 $v$ 产生贡献当且仅当 $v$ 第一次作为左端点前没被覆盖过，并且最终至少存在一个 $v$。维护一个 $f_i$ 表示对于 $l_i$ 上一个影响到它的操作，$t_i$ 表示颜色 $i$ 彻底消失的时间。$t$ 可以倒序维护，第 $c$ 次操作就是 $t_i\to c,i\in(l,r]$，$t_l\to\max(t_i),i\in(l,r]$。ODT 维护 $t$ 的连续段即可。最后二维数点，时间复杂度 $O(n\log n)$。

ZR3000

注意到返回 $1$ 一定就是按照 dfs 序走一遍，但是可以不返回，于是可以停在一个离 $1$ 最远的叶子节点上，到根的路径不被访问。算概率的话提出来这条路径，逐渐往下走，要求沿途挂着的子树都恰好访问干净不重复，设一个 $f_u$ 表示概率，$h_u$ 表示儿子的 $f_v$ 的乘积。找到到这个叶子的概率就是路径上 $h$ 乘积除以 $f$ 的乘积。

T514236

前缀和是一条折线，显然如果我们正序对操作序列 dp 是通过较少的信息量无法得知当前位置的，这个的经典套路是倒序进行 dp，这样在第一位插入一个数会导致全局的前缀和都进行变化。考虑 dp 为，倒序考虑了最后的 $i$ 个操作，不妨设当前在倒数第 $i$ 次操作前的位置是 $0$，那么有多少的概率使得这个前缀和折线经过了 $j$ 的概率。转移是 $O(1)$ 的，时间复杂度 $O(n^2)$。

T514239

正难则反，考虑统计一些相对容易计数的来容斥出来两两不交的三元组。令只有一个交点的三元组是 $x$ 个，有两个交点的三元组是 $y$ 个，有三个交点的三元组是 $z$ 个。首先处理出 $d_i$ 表示第 $i$ 个矩形与多少个矩形有交点，显然有两种方向：$(n-2)\sum d_i=2x+4y+6z,\sum \binom{d_i}{2}=y+3z$，那么可以统计出 $x+y$ 的值。$z$ 本身不难求。先考虑怎么求 $d_i$：在横轴上扫描线，相交的矩形分为左线在这个矩形前出现和在这个在这个矩形的左线后面。可以跑两遍扫描线，用树状数组维护纵轴，区别在于扫描到右线是否撤销以及统计的细节。再考虑怎么求 $z$，可以考虑对三个矩形的交集统计，覆盖了 $x$ 次可以表示为 $\binom{x}{2}$，可以用线段树维护区间和与区间每个数的二次方的和，支持区间加。开两棵线段树容斥掉右端点 $\leq r-1$ 的情况即可。时间复杂度 $O(n\log n)$。

20240923

P4769

注意到一个合法的前缀最大值序列 $a_i$ 与一个合法的最长下降子序列长度 $\leq 2$ 的序列形成双射。对前缀最大值序列计数即可，对于某条线上的一堆起点到最后的一堆中点且不跨越 $y=x+b$ 的方案数，这是经典的反射容斥。

P6790

广义串并联图模板题（删一度点，叠合重边，缩二度点），在缩边过程中维护这条边代表的边集中，$f_x,g_x$ 分别为选或不选这条当前边的生成树的方案数。容易在三种操作过程中维护转移，实现细节可以用 map 维护所有边，拓扑的话用队列维护当前的 $\leq 2$ 度点，复杂度 $O(n\log n)$。

P9061

对于一次操作，就是把一个左下角的东西移到边界上。我们可以对尚未操作与已经操作的分开维护。被操作的点显然是一条轮廓线，剩下的点在其右上部分。可以先跑一次扫描线维护出每个点什么时候被操作。对于一次询问可以考虑容斥：

$x\ge X,y\ge Y$ 的数量 $c_1$。可以直接二维数点，与时间无关。
$x\leq X$ 且不在轮廓线数量 $c_2$。
$y\leq Y$ 且不在轮廓线数量 $c_3$。
$x\leq X,y\leq Y$ 的轮廓线数量 $c_4$。
轮廓线上有 $c_5$ 个点。

这样怎么想到的？划分为四个区域，分为是否在轮廓线上。$c_1+c_2+c_3+c_4+c_5-n$ 就是答案，因为被统计的会被加 $2$ 次，未被统计会被统计 $1$ 次。fhq treap 维护这条轮廓线。时间复杂度 $O(n\log n)$。

20240924

P10896

左括号看成 $+1$，右括号看成 $-1$，考虑实际上无法消去的都会让折线往上后下不来，$m=1$ 时记录折线的左端点减去最小值，加上右端点减去最小值就是实际权值。考虑怎么排列这 $n$ 个串，记录这两个值构成的二元组为 $(x_i,y_i)$。钦定一个最小值的位置往左右放即可。考虑让 $x_i\leq y_i$ 的都放到左边，否则放到右边，贡献为 $|x_i-y_i|$。注意到此时中间的串贡献为 $x_i+y_i=|x_i-y_i|+2\min(x_i,y_i)$。我们希望是最大化这个值，$\sum E(|x_i-y_i|)$ 可以和 $E(2\max(\min(x_i,y_i)))$ 分开求。对于 $E(\sum |x_i-y_i|)$ 是拆了对于每个 $l_m$ 求的。对于 $E(|x-y|)$ 显然是 $S$ 的左括号个数减去右括号个数，由于本质不同的 $|S|$ 只有 $O(\sqrt n)$ 种，所以可以对于每一种串长暴力求。对于 $\max(\min(x,y))=k$ 可以容斥成 $\geq k$ 减去 $\geq k+1$。这个可以对于每一个求 $\leq k$ 的概率最后相乘。这个可以转化为 $1-P[\min(x,y)\leq k]$，对于每一种串长去给这些算贡献。枚举第一个最低点的位置，这是反射容斥的形式。发现 $\min(x,y)<k$ 的数量可以组合数前缀和求出。

CF1919E

题意就是重新排列 $p$，要求 $p_1\in\lbrace-1,1\rbrace,|p_i-p_{i-1}|=1$。注意到对于每一种值只能从上一个值的位置加点，所以用上一种值的位置情况作为 dp 的状态，即考虑用连续段 dp 的套路从小到大加入点。考虑 $f_{i,j,0/1,0/1}$ 为加入前 $i$ 小的值时，只考虑 $i$ 形成了 $j$ 对相邻，左边是否允许加点，右边是否允许加点的方案数。允许加点的意思就是两边是否为 $i$。因为有效状态数很少，整体复杂度甚至是 $O(n)$ 的。

P9338

构造段数 $\leq k$ 的方案即可，盲猜可以 wqs 二分，考虑对于第 $i$ 个 A 必须匹配第 $i$ 个 B，那么要求 $c_i$ 表示第 $i$ 个 B 的前面有多少个 A。考虑要求 $[l,r]$ 的 A 去匹配 B 的代价是 $w(l,r)$，可以表示为 $\sum \max(c_i-l+1,0)$，可以用冒泡排序消去逆序对的过程来理解。wqs 二分过程中可以使用斜率优化，$w(l,r)$ 可以求出 $y=c_i$ 与 $y=x$ 的交点去掉对 $0$ 取 $\max$，时间复杂度 $O(n\log n)$。

CF1870F

考虑对于 $1\sim n$ 建立 $\text{trie}$ 树，要统计的就是 bfs 序等于 dfs 序的数量。bfs 序是 $+1$ 的，dfs 序是变化极大的，所以 $\text{bfn}-\text{dfn}=0$ 的位置对于 bfs 序每一层是一段区间，可以二分求。求一个数的 dfs 序是容易的。

NOIP2020 walk

判 $-1$ 是显然的。考虑换维，每一步开始前统计当前存活的起点数量。注意到存活的起点数量可以用：每一维存活的起点区间 $[l_i,r_i]$ 的区间长度乘积来表示。考虑每一维度存活的起点构成区间的长度 $f_i(x)$ 的情形，$x$ 为当前步数。分别考虑历史两个方向的位移最大值，以及一轮下来的位移量，可以列出关于三个量以及 $x$ 的一次不等式。所以 $f_i(x)$ 是个关于 $x$ 的一次不等式，这些函数的乘积就是 $k$ 次不等式。可以暴力模拟前 $k+1$ 轮，用拉格朗日插值算出第 $t$ 轮的函数前缀和值，手动模拟不完整的第 $t+1$ 轮即可。时间复杂度 $O(nk^2)$。

P5404

肯定要算不合法的串个数，要求 $t^{\infty}$ 任意长度为 $|s|$ 的子串的字典序都恒 $\ge|s|$。考虑在 $t$ 进行匹配时，要求最长的 lcp 进行匹配，可以首先对原串建立 kmp 自动机以求出新加上时该从哪里匹配，用好 $t$ 是无穷的限制。往小的出边走一定是不行的，要么从 $mx_u$ 表示最大的 $i$ 使得 $nxt_{u,i}$ 不指向根走到下一个，要么从 $>mx_u$ 的回到根节点重新匹配一轮。注意到 $t^{\infty}$ 并没什么用，假设 $t^{\infty}$ 匹配到的是 $x$，在 kmp 自动机上跑一遍还是回到当前节点 $x$，因为还是 $t^{\infty}$，而 $t$ 合法要求每步都是合法的转移边。对于每个 $x$ 作为 $t'$ 的终止节点，枚举第一次走到 $0$ 的时刻是 $x$，后面的部分可以预处理 dp，即 $f_{i,j}$ 为从 $0$ 走了 $i$ 步到自动机 $j$ 号节点的方案数，时间复杂度 $O(nm)$。

P9542

神秘操作必须考虑什么是不变的哦。

感觉这种神秘东西和图的形态联系很大啊。考虑什么时候可以直接让边权最大的边取到贡献的最大值。先考虑图不是一条链的情况。

图是一个环。如果是奇环，每个位置可以走到任意位置；如果是偶环，这个操作不会改变任意节点对的奇偶性。考虑对环黑白染色，那么原来距离偶数的点一定无法相遇。答案为 $(c_{LB}c_{RW}+c_{LW}c_{RB})$。这提示我们进行二分图染色。对于一个存在大于 $3$ 度点的树其实是类似的，只需要考虑 $(a,b),(a,c),(a,d)$ 的边，操作子树 $b$ 中的会让一个子树 $c$ 的与子树 $d$ 的距离减小 $2$，仍然需要二分图来刻画两点距离。
图不是一个二分图。利用奇环来分开黑白即可，可以取到 $c_{B}c_{w}\text{maxval}$。
图是一个二分图。对于一对左右部图是无法变为同种部图的，答案是 $(c_{LB}c_{RW}+c_{LW}c_{RB})$。

图是一个链是特殊的，注意到无论如何，每一个点都汇聚着原序列一个连续区间的点。考虑双射判定一个点对应一堆集合的序列是否合法。我们要求两点距离的奇偶性不变，并且都小于等于原来的距离。考虑进行区间 dp 来维护合并的过程，$f_{i,l,r}$ 表示前 $i$ 个点中，一个区间 $[l,r]\subseteq[1,k]$ 的点都聚集在 $i$ 上的贡献，转移考虑枚举下一个集合的位置 $j$ 以及区间 $[r+1,t]$。需要判定奇偶性，要求聚合在一起的奇偶性必须相同，且距离不变大。因此复杂度是 $O(n^4)$ 的。

P10202

其实想到区间 dp 以及至多剩下一种值才能往后贡献就做完了吧。$K$ 其实并没什么用，强调的是一个顺序，两种操作序列不会重复的。每次我们的描述应该是不进行移位的：每次操作 $a_l=a_r$，要求 $l,r$ 未被标记且 $[l,r]$ 中间未被标记的数值都等于 $a_l$，那么给 $[l,r]$ 打上标记。注意到合并时还要考虑两边独立的情况，需要加上步数限制。那么可以这样：$f_{l,r,x,y}$ 表示 $[l,r]$ 内部有多少种操作序列用了恰好 $y$ 步至少删去 $[l,r]$ 除了 $x$ 之外的所有数，但是要求至少留下一个 $x$。如果 $x=0$ 表示删空。$g_{l,r,x}$ 表示有多少种 $x$ 步的操作序列删空 $[l,r]$。其实是为了转移更明晰而让 $g_{l,r,x}=f_{l,r,x,0}$。区间 dp 考虑以 $l$ 来更新，枚举区间中每一个 $a_i=a_x$ 表示 $[l,x]$ 打标记的操作进行继承即可。时间复杂度怎么是 $O(n^6)$ 的。/fn。

P6789

你们 zr 还搬这玩意。kruskal 的思想拓展一下，对于每一条边拆贡献，产生贡献的概率只需要考虑边权小于它的，排序一下就是只考虑一个前缀的边。我们需要计算产生贡献的概率，正难则反，考虑这条边不产生贡献的概率即可，也就是已经插入了基环树连通块。先考虑 $x,y$ 已经连通的概率，要求已经成环，这个方案数是 $g_{S}$。对于 $x,y$ 不连通的方案数，枚举 $x$ 所在极大连通块 $S$ 以及对面的 $T$。连通子图方案数可以高维前缀和跑一下。难点在于求 $g_S$ 表示点集 $S$ 已经构成大于一个环的概率，减去 $f_S$ 表示 $S$ 为树的概率。总数是 $c_S$ 表示连通子图为 $S$ 的方案数。总复杂度 $O(3^nm)$。

P7470

这玩意拆成 $\log$ 段区间到线段树上，直接变成 01-trie 板子题了。$\min$ 的限制可以用排序消去一段前缀的加入。

T278695

考虑分类讨论路径的交集是直链还是弯的。如果交集是弯的，lca 必然相同，放在 lca 上统计，并且往两个方向向下走到的点对一定相同，我们还要求到这两个点的距离是相同的，这个可以 map 统计下。重点是交集为直链的情况。其实并不严格要求，对于一条弯的会被统计两次，减一下就行了。注意到直链的底部必然是 $\text{lca}(s_1,s_2)$ 或者 $\text{lca}(t_1,t_2)$，这样行进方向是相同的。我们希望对于每条 $(u,fa)$ 计算出有多少路径以这条作为底部。我们要求 $u=\text{lca}(s_1,s_2)\ne \text{lca}(s_1,t_1)$ 且 $u\neq \text{lca}(s_2,t_2)$。这样可以让交集至少为一条边。如果 $\text{dep}(s_1)=\text{dep}(s_2)$ 就有友好关系。再考虑 $u=\text{lca}(t_1,t_2)$ 的情况，同理要求 $u\ne \text{lca}(s_1,t_1)$ 且 $u\neq \text{lca}(s_2,t_2)$。这时我们要求 $\text{len}(t_1)-\text{dep}(t_1)=\text{len}(t_2)-\text{dep}(t_2)$。可以在 dfs 过程中用树上差分的套路保证一条链上时存在贡献。在保证一个点的 $\text{lca}$ 为 $u$ 时，用 map 维护启发式合并可以做到 $O(n\log^2 n)$。

20240925

不知道哪里看来的题

给你一个序列 $v_0,v_1,\cdots,v_{2^n-1}$，$m$ 次询问每次询问给出 $x,p,q$ 求：

\[\sum_{0\leq y<2^n,|x-y|\leq p,\text{popcount}(x\oplus y)\leq q}v_y \]
$m\leq 10^5,n\leq 18$。

容易将询问拆成 $y\leq k$ 且 $\text{popcount}(x\oplus y)\leq q$ 的和。考虑进行数位 dp，就是确定一段前缀后的做法。那么在确定一个 lcp 的过程中就相当于给所有值赋上了一个前缀，我们只关心后缀的 $\text{popcount}$，枚举这个 $x$，设计 dp 为 $f_{i,x,j}$ 表示最低 $i$ 位的 $y$ 的 $\text{popcount}(y\oplus x)$ 为 $j$，且更高位相等的 $v_y$ 的和，容易 $O(2^nn^2)$ 预处理，询问可以做到 $O(qn)$。

不知道哪里看来的题

给定一张有向图，对于每条从 $u$ 到 $v$ 的有向边，都满足 $u<v$。给定 $k$ 条图上的路径，对于每一个 $i(2≤i≤n)$，求 $1$ 号点到 $i$ 号点的路径的条数，满足该路径不包含给定的 $k$ 条路径的任何一条。换句话说，这 $k$ 条路径中每条路径都至少有一条边不在我们当前考虑的路径中。答案对 $998244353$ 取模。

$n,m,\sum l_i\leq 10^5$。

可以将所有点和边和路径进行反向，求出每个点到 $1$ 的方案数。按照拓扑序处理这张图。将路径视为字符串，对于所有路径考虑建立一个自动机，将走一条路径视为匹配字符串的过程，自动机上节点相当于给某个点赋上不能从根一直走到现在。将原图以及其出边重构成这个自动机上时就可以直接在上面匹配。100 分做法不会了。

T278697

这种问题一定要考虑拆贡献啊。我们考虑拆到每一个节点上，计算有多少个划分方式出现了这个节点表示的串。在字典树上出现过当且仅当某一个位置的左端点恰好是这个部分的起点，并且这段延续到了之后。对于原串的一个本质不同子串，找到所有 $c$ 个出现位置计算贡献。我们需要在 $O(c)$ 的复杂度内解决。正着算很不好去重，正难则反捏，考虑有多少种方案让这 $c$ 个都没贡献。考虑倒序 dp，首先状态的阶段一定是某一个出现位置作为一个段的左端点，这样才可以算不合法的，这个方案数是 $f_i$ 的话，要求后面都不会让 $S$ 出现，把有交集的段放在一起考虑。是容易前缀和 dp 优化的，时间复杂度 $O(n^2)$。

P10255

首先转化为两个点差分的修改，令 $c_i=a_i-a_{i-1}$，每次操作形如 $c_l\to c_l+x,c_{r+1}\to c_{r+1}-x$。考虑 $c$ 生成 $b$ 就是对于每一个极长的非 $0$ 连续段（需要特判 $c_1$），长度为 $x$ 时对 $b$ 进行一次函数加。首先用 set 维护所有 $0$ 的位置，可以高效维护所有的连续段信息，而本质不同的连续段长度种类是 $O(\sqrt n)$ 的，用另一个 set 维护所有的连续段长度即可。接下来考虑如何处理询问。对于每一种加的操作，会给整个数轴划分成 $O(\sqrt n)$ 段。对于每一种连续段长度 $t$，我们倒序扫，相当于找每一段，那么是对这一段进行一次函数加，斜率 $k$ 是倒序累加的。异或加上一次函数很唐，但是可以根号分治。如果 $k\leq B$ 直接用预处理的值，如果 $k>B$ 每一次暴力求的复杂度是对的。时间复杂度 $O(n\sqrt n)$。

P8935

由于类似剪枝，预处理出 $f_{u,i}$ 表示 $u$ 子树中用 $i$ 次操作的方案数，需要预处理组合数，容易 $O(n^2)$ 求出。之后考虑取出 $1\to x$ 的链，注意到前 $k-1$ 步是可以往上操作的，所以需要将这条链拿出来做。我们研究一下这条链的性质，发现前 $k$ 次只能处理这些链上挂着的子树，在这之后是无所谓的，那么一个来处理这里面用了 $t$ 步的，可以分为前 $k-1$ 次与后面的两个阶段。对于后面的阶段，我们也要在现在统计了。首先对于链上每个点处理一下 $c_i$ 表示 $i$ 步处理多余子树的方案数，对非链上的儿子合并一下就行了。考虑是当前进行了链的前 $i$ 个节点，令 $p_i=u$，需要迎合 $k$ 的限制，假设有一个 $u$ 的 shake 操作，那么我们钦定了前 $j$ 个操作是在 $u$ 标记操作之前的，我们需要求相对顺序的方案数，状态需要包含考虑之后往上删的方案数，这其实并不重要，因为最后一步总是 $1$ 的，但是我们仍然需要考虑 $i$ 是否删去，$fa\to u$ 时如果 $u$ 不需要进行操作可以直接继承，否则需要从 $j\geq i$ 进行转移，原因是中间必须隔一些操作调整顺序，必然都可以找到唯一的位置来插入，然后跑一遍 $u$ 自己挂的子树的贡献就行了。答案就是 $g_{x,k-1}$，时间复杂度 $O(n^2)$。

20240926

P8428

考虑进行贪心，每次取出没被看着的羊中深度最大的 $u$，多源 bfs 出 $dis_i$ 表示 $i$ 到最近一个羊的距离，找出 $u$ 的最浅祖先 $v$ 使得 $v$ 可以管辖到 $u$，同时更新哪些点可以被 $v$ 更新。暴力做是 $O(n^2)$ 的。显然可以快速找到 $dep_v-dep_u=dis_u$ 的这个点，并且由于每个边最多覆盖一次，可以暴力找离 $v$ 最近的所有点，具体就是在 bfs 过程中构造一个图用来找这些关键点，在这个图上考虑所有能走到的点即可，注意访问过就没用了，一条边最多覆盖一次。时间复杂度 $O(n+k\log k)$。

CF883B

显然图一定是一张 DAG 才有合法方案。对于一个点找拓扑序在其之后的一个到赋值点的最长路，那么这个点的上限一定是赋值点减最长路长度的最小值。同理需要考虑反图这个点可达的最长路加上赋值点长度。对两个分别跑一下拓扑排序求出 $a_i$ 的取值范围 $[l_i,r_i]$。我们希望尽可能小地去分配，这样就会尽可能满足边的限制。要求对于 $\forall j\in[1,k],\exist i\in[1,n],a_i=j$。扫描线当前的值并维护 $l\leq i$ 的集合 $S$，我们希望取出 $S$ 中某些元素赋值为 $i$，直接贪心维护 $S$ 中 $r$ 的最小元素即可。时间复杂度 $O(n\log n)$。

hdu6314

对于二维容斥是困难的，考虑对于一维进行容斥，$g(i)$ 表示钦定 $i$ 行全黑的方案数。显然对于 $g$ 进行二项式反演即可求出最终答案。$g(i)$ 统计的是钦定 $i$ 行，对于每一个染了 $j\ge B$ 列全黑的统计系数应该恰好为 $1$。这样做的好处就是只需要对于 $(n-i)\times m$ 的矩阵统计有多少方案存在 $\ge B$ 列全黑，对于这个内部自身进行容斥即可。时间复杂度 $O(nm)$。另一种做法是对于一个钦定 $x$ 行 $y$ 列的方案的容斥系数可以拆成两个方向的容斥系数 $a_x,b_y$ 相乘，$a,b$ 都是容易递推的。

ZR2961

一个额外边看成一条树上的路径时，要求剩余额外边对应的路径都不与这条边产生至少一条边交集。那么我们需要求出与该条路径相交的路径的 $p$ 的乘积。好写的做法是考虑【点减边容斥】的套路，类似地设计一个【有一条边重合的 $p$ 的乘积，除以，有连续两条边重合的 $p$ 的乘积】，这样对于一条需要统计的路径的系数就恰好为 $p$。注意到可能有 $0$，需要特殊处理。即对于一个乘积维护其可以表示为 $x\times 0^y$。时间复杂度 $O(n\log n)$。

CF2013F1

将走过一条边视为断边操作，考虑提取出来 $1\to u$ 的链，树的形态可以抽象为这个主链以及链上挂着的一堆子树。一个很明显的观察是如果一个人在两个人相邻之前下到了链的子树上时，后面那个人就无法跟上来，这个人会一直走到最底下。而剩下那个人会去选取当前连通块能走到的最远点。因此可以处理出 $a_i$ 表示走到 $i$ 时，如果决定离开这条链，往下拐时能最多走多远。可以线性处理出 $f_u$ 表示从 $u$ 往下走到最远叶子的距离。由此它变成了一个数列问题，A,B 分别在数列两个端点。枚举走到 $i$ 表示离开这条链的位置，注意 $i$ 要求 A 在 B 之前到达，不然 B 可以抢先占有这里，而前面的点都不是 A 的必胜点。考虑 $a_i$ 往下拐然后 B 最多能执行多少步操作即可，需要动态模拟一下 B 现在跑到哪里了。时间复杂度 $O(n)$。

ARC184D

转换计数对象，对选择的球的集合 $S$ 计数是有救的。记录 $a_i$ 表示 $x_j=i$ 的 $y_j$。这是一个子序列计数，考虑当前结尾的是 $i$，且 $i\in S$，在这之前的方案数是 $f_i$。希望判定是否可以从 $j<i$ 的 $f_j$ 转移到 $f_i$。显然这个 $S$ 中的 $a_i$ 必须是单调递减的。考虑怎么去重，因为两个合法操作序列的剩下来的球集合可能有重复。放到二维平面上，一个点会删去左下和右上中的所有球，那么连续的 $S$ 中的两个点 $i,j$，会让中间的一些点活着。我们希望 $S$ 的操作是“极长的”，也就是中间无法插入别的操作 $i<k<j$ 使得 $(i,j)$ 与 $(i,k,j)$ 删除后剩下的相同。对于每个 $(i,j)$ 暴力判定是否是“极长的”，时间复杂度 $O(n^3)$。

不知道哪里看来的题

给定一个序列 $a_i$，找到最小的 $k$ 使得存在 $[l,r]$ 满足以下条件：

$r-l+1\ge m$

$\forall i\in[l,r],\exist j\in([l,r]\setminus i),|a_i-a_j|\leq k$。

$n\leq 10^5$。

考虑二分答案 $k$，那么可以找到最小的 $nxt_i>i$ 使得 $|a_i-a_{nxt_i}|\leq k$ 以及最大的 $lst_i<i$ 使得 $|a_i-a_{lst_i}|\leq k$。就是判定是否存在一个区间 $[l,r]$ 使得任意 $i$ 都有 $nxt_i\leq r$ 或者 $lst_i\geq l$。首先求出 $nxt,lst$ 可以扫描线判定一个 $i$ 可以作为哪些 $j$ 的 $nxt$。用一个 std::set 维护出哪些 $j$ 是尚未匹配的即可。现在考虑倒序扫描线最终区间的左端点为 $l$。如果一个 $lst_j\ge j$，那么区间包含 $j$ 必然是合法的。但是如果有 $lst_j<i<j<nxt_j$，那么如果选了 $j$ 就必须要包含 $nxt_j$。这个在 $R$ 的大小关系上就是一段区间哦，正难则反，就相当于不能有 $R\in[j,nxt_j)$。扫描线过程中由于 $l_j$ 是出现过的所以可以对这些 $j$ 打上标记。考虑在线段树上维护限制，每个限制形如右端点不能是 $[j,nxt_j)$ 之中的，每次形如对 $[j,nxt_j)$ 区间 $+1$，每次判定在 $l_j$ 撤销贡献。每次判定是否有 $\ge i+m-1$ 的位置的限制值为 $0$ 即可。时间复杂度 $O(n\log n\log V)$。

P10548

结论：极短的区间 $[l,r]$ 使得 $[l,r]$ 的 $\text{mex}(l,r)$ 再缩短会变更个数是 $O(n)$ 的。把这些极短区间求了，再求出对应的极长区间，可以快速刻画出子区间的 $\text{mex}$ 为一堆矩形覆盖。只需要考虑子区间的话就是对一个区间进行处理。直接扫描线一下就行了。

CF1767E

考虑先消去数列的限制，我们要求相邻的两个数不能都不激活。也就是考虑对存在相邻的两个颜色之间连一条边，我们要求它的最小带权点覆盖，等价于点权和减去最大权独立集。$m=40$ 考虑进行 meet-in-the-middle。对前面考虑选出集合 $S$ 的最大值 $f_S$，容易状压 dp 求出。对于右半部分枚举集合 $T$ 选入最大独立集，左半部分形如 $T_i$ 补集的交的子集，可以进行 SOS-dp，时间复杂度 $O(n+m2^{m/2})$，判断一个集合是否可以作为最大独立集可以高维前缀和出导出子图的边数。

P5405

这个锤子性质就是保证 $(u,v)$ 视为无向边后图是一个树。考虑建图 $u\to v$，先考虑图是外向树的情况，那么就是一个求带权拓扑序，要求每个 $u$ 都是子树内第一个抽到的，分开独立求出概率求积即可，概率为：

\[\prod_{u=1}^n\dfrac{W_u}{W}\sum_{k\ge 0}\left(\dfrac{W-\text{wsum}_u}{W}\right)^k= \prod_{u=1}^{n}\dfrac{W_u}{\text{wsum}_u} \]

这样是只与子树有关的，如果是外向的直接记一个 $f_{u,i}$ 表示 $\text{wsum}_u=i$ 时 $u$ 子树内的合法概率之积即可。但是有反向边，正难则反，考虑用容斥处理。状态的定义变更为容斥的贡献和。对于一个集合 $S$ 我们计算强制不满足，剩下随意的贡献和，不满足相当于要求反向，没被钦定的相当于直接断开成独立的连通块。注意到我们不关心 $|S|$ 甚至不关心 $|S|\text{ mod }2$ 的值。树上背包合并一下，如果是反向的我们可以分讨一下是断开还是反向，分别向上的贡献系数是 $1$ 和 $-1$。时间复杂度 $O(n^2)$。

LOJ3102

哈密顿回路可以描述为若干条在某棵树上跳的链以及中间穿梭的步骤。考虑对于每棵树 dp 出来有多少划分成 $i$ 条链的方案数，那么相当于要求每棵树划分出来的链在最终回路中不可以相邻。这个子问题的做法是，求出 $f_{u,i,0/1/2}$ 表示 $u$ 子树中划分出 $i$ 条链的方案数，使得 $u$ 在其所在链上的度数为 $0/1/2$，由于链是可翻转的，所以在给一个非单点的链封口的时候需要乘上前后翻转的方案数。可以 $O(n^2)$ 求出来，最终我们关心的是 $coef_i$ 表示 $i$ 个 $u$ 颜色球的贡献和。问题转化为：有 $m$ 种颜色的球，内部是互相区分的，第 $i$ 种选取 $j$ 个的方案数是 $f_{i,j}$，对于所有选取的方案，要求排成一条链并且每种颜色的球不得相邻，求总和。考虑进行容斥，对于一个序列 $a_i$ 表示 $i$ 颜色选了 $a_i$ 个，$1\leq b_i\leq a_i$ 表示 $i$ 颜色有 $b_i$ 个块，此时贡献为：

\[\left (\prod \dfrac{a_i!}{b_i!}\binom{a_i-1}{b_i-1}(-1)^{a_i-b_i}\right )\left(\sum b_i\right)! \]

对于每一种颜色枚举 $(a,b)$，容易发现我们可以只考虑所有的 $b_i$，前面的 $a_i$ 可以放到内部自己做掉。然后跑一下卷积就行了。时间复杂度 $O(n^2)$。

CF1605F

总结：要对一类东西找到一个好计数的对象统一计数。

先考虑如何刻画一个序列是好的。考虑集合 $S=\lbrace0,1,\cdots,k-1\rbrace$。每次取出数列的两端 $x,y$，要求任意 $i\in S$ 有 $x_i=y_i$，将这两个数放在序列的两端，然后在 $S$ 中删除所有 $x_i=1$ 的 $i$，如果某一次找不到就是寄了。

注意到无法操作的情形是很好计数的，也就是互不相同，合法可重集有点抽象，同样是考虑正难则反的思想，我们希望求出一个不合法可重集中最长能填 $f(a)=x$ 个，可以对所有的 $x$ 分开求解。这样做的好处是，剩下的位两两一定没有相同的，而这就是在全集中选几个数再排列，这个是简单的。记录这个数量是 $f_{n,m}$ 表示长度为 $n$，有 $m$ 个位在其中有值的不合法序列方案数。$all_{n,m}$ 表示长度为 $n$，$m$ 个数或起来为 $2^m-1$ 的方案数，$g$ 是在 $all$ 的基础上要求互不相同。两者都可以容斥处理，也就是枚举仅在 $p\leq j$ 位中有值。对于 $g$ 需要暴力跑组合数，这一部分是 $O(n^4)$ 的。

显然有：不合法数量加上合法数量 $=all$。对于 $f$ 考虑枚举不合法序列 $a$ 的 $f(a)=x$，它的或的 popcount 为 $y$，此时转移为：

\[(all_{x,y}-f_{x,y})\binom{n}{x}\binom{m}{y}2^{(n-x)y}g_{n-x,m-y} \]

这个 $g$ 就是里面完全无法再消的方案数。时间复杂度 $O(n^4)$。

20240927

CF1951H

一碰到博弈就不会是这样的。考虑视为一个 $0\sim t$ 层节点的满二叉树也即线段树，叶子节点是一个 $2^{k-t}$ 长度的区间，再进行二分答案判定答案是否可以 $\ge mid$，将 $\ge mid$ 的视为 $1$，$<mid$ 的视为 $0$，这个序列为 $b$，可以进行前缀和来快速查询区间内 $1$ 的个数，原问题就变为 $01$ 序列，A 希望最终存在一个 $1$，B 希望走到最后没有 $1$。这个考虑进行 dp，求出来 $f_o$ 表示当前在 $o$ 表示的节点时，如果 A 想获胜最少需要换进来多少个 $1$。从上往下做是困难的，考虑从下往上做，也就是倒序枚举线段树当前在第几层来更新 dp。操作到第 $i$ 层之后，必须拥有不少于 $2^{t-i}$ 个 $1$，不然必然可以走到一个没有 $1$ 的叶子节点。这个作为 dp 初值，还需要考虑对 $f_{lson}+f_{rson}-1$ 取 $\max$，因为可以在本层进行一次交换。时间复杂度 $O(k^22^k)$。

P7065

显然可以把连续段缩到一起。通常我们需要变换分析的维度，改为值域上进行 dp。考虑在已有的 $\leq x$ 的方案上怎么加入 $\leq x+1$ 的。显然，所有 $x$ 的位置一定是所有段的结尾。我们可以用 dp 来解决最优合并问题。我们将值都映射到 $[1,k]$ 上使得对于每个 $i$ 都存在一个位置为 $i$，那么一个重要的观察是不能将值不相邻的位置合并，不然就会跳过中间的值无法插入。令 $b_i$ 表示序列中 $i$ 的个数，$f_i$ 表示考虑所有 $\leq a_i$ 的数，分段后 $i$ 为最后一段的最后一个时最多的合并次数。令当前扫描到 $x$：

如果与前面不能合并就跳过。
$b_x=1$，如果 $a_{pos(x)-1}=x-1$，可以有转移 $f_{i-1}+1\to f_i$。
$b_x>1$，那么考虑与前面连接时，是否是 $f_j$ 的最大值，如果是的话就改成次大值，否则直接从最大值转移。转移只有 $+1$ 的，剩余的都要分成单点。

时间复杂度 $O(n\log n)$，精细实现可以 $O(n)$。

LOJ4019

有点牛了，由于 $S=2^k$，所以我们先研究 $S=2$ 的情况，对于全分直接利用移球游戏的套路加个分治构造就行了。考虑是二元关系直接连无向边，要求一组定向方案使得每个点的出度和入度最多差 $1$。这个和欧拉路径很像，如果存在奇度点，建立虚点与这些奇度点连边之后，所有点度数都是偶数，再跑欧拉回路再去掉虚点就是正确的。由于会有重边，所以需要给出边的编号，直接 dfs 即可。考虑 $S>2$ 的分治构造的细节，类似地对每一行建一个点，每个对这个进行连边，在这张图跑上述做法，根据分到的左右重新分治即可。这样做的正确性在于每个颜色在前一半的出现次数与后一半的出现次数差 $\leq 1$，时间复杂度 $O((nS+T)\log S)$

20240928

联考和 zr 都坠机了。

CF2018F3

对于一个给定的起点，肯定是考虑贪心，如果存在当前点距离为 $t$ 的点需要在 $t$ 轮内过去，就需要过去，如果两个方向就有就寄了。而合法的起点集合一定构成一个区间 $I$，否则答案为 $0$。注意到 $I={\Large\cap}_{i=1}^n[i-a_i+1,i+a_i-1]$，要么 $I$ 全部合法，要么 $I$ 全不合法。考虑对于走向策略是尽量走左边，这样得出的遍历顺序 $p$ 是唯一的。此时有 $a_i\ge\max(i-l+1,r-i+1)$。直接钦定 $[l,r]\subseteq I$，可以得出每个位置的下界 $b$，对内部进行区间 dp，枚举 $l$ 在什么时间被抵达，同时计算 $a_l$ 的取值，再在外面进行容斥可以做到 $O(n^4)$。事实上这是一个断环成链的过程，注意到 $b$ 对 $|I|$ 固定时是差不多的。考虑对于所有的 $k=|I|$ 放在一起做，倍长一下原数列，就可以对所有 $f_{i,i+n-1}$ 做容斥。在注意到 $b_i$ 可以快速处理后，可以 $O(1)$ 转移，时间复杂度 $O(n^2)$。

P6700

记 $k=26$ 表示字符集大小。容易发现 $1$ 操作一定在最后执行，并且可以构造对于每种字符只进行一次的二操作，那么令 $c$ 表示字符 $c$ 通过操作二 / 不操作变成了字符 $p_c$，这一定是一个内向基环树。但是有解的图的操作顺序一定是没有长度 $>1$ 的环的。记录一个 $cnt_{x,y}$ 表示有多少个 $a_i=x,b_i=y$，那么如果将 $i$ 变为 $p_i$，其所需要的操作代价 $w_{x,y}$ 是容易确定的，那么贪心令 $i$ 的出边指向 $w$ 的最小值的 $j$。但是发现必须要消去所有的环。这个图的性质就是 $i\to p_i$ 不能连出环，自环除外。而一个根节点自环的基环树一定是符合条件的，但是我们希望解决的是环长 $\ge 2$ 需要中转点的情况，这个中转操作需要存在中转点并且需要花费 $k$ 的额外代价。注意对一个连通块成功移位之后其叶子节点一定是可以作为后续的中转点的。直接对基环树的形态进行 dp 是没救的，考虑自环可以单独处理，剩下都是环长 $\ge 2$ 的，最多有 $k/2$ 个环。而这些环不会增多，不然会产生额外代价，而为了消环可以去改变环上某些点的 $p_i$ 以断环。这样需要考虑的环可以直接状压维护，$f_{i,S,j}$ 表示前 $i$ 个点的 $p$ 中，有 $S$ 集合的环被破开了，此时是否有 $p$ 被修改。最后一维需要记录是因为在最开始有可能出现无法中转的情况，如果每个字符都在长度 $>1$ 的环中，一个出边都不改事实上是无法达成的。时间复杂度 $O(n+k^22^{k/2})$。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.ryyt.cn/news/66841.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈，一经查实，立即删除！