260519 - 260529

260519 B

给定一个排列 \(p_{1\sim n}\)，每次你均匀随机一个 \(i\in [1,n]\)，将 \([1,i],[i+1,n]\) 分别排序，求排好序的期望步数。

\(n\le 5000\)

考虑第一次排序之后会形成两个上升链，我们记 \(c_i\) 表示数字 \(i\) 在左边还是在右边。此时一次排序形如把左边链的一个后缀合并到右边，或者把右边链的一个前缀合并到左边，即形如把一个 0 的后缀改成 1 或者把一个 1 的前缀改成 0，合法当且仅当 0 都在 1 的左边。先枚举第一次排序的位置，然后记 \(dp_{l,r}\) 表示 \(l\) 左边都是 \(0\)，\(r\) 右边都是 \(1\) 并且 \(l,r\) 还不合法，期望步数，转移是容易的，时间复杂度 \(O(n^3)\)。

我们对子串 10 消失的时间进行 \(\min-\max\) 容斥，发现 \(\min\) 一定取在两侧的 10，所以如果中间还有其他的 10 那么容斥系数就会互相抵消，因此只有相邻的两个 10 或者单独一个 10 有贡献。我们只关心它左边还剩多少个 1，右边还剩多少个 0，所以只需要一次 \(O(n^2)\) 的 dp。

260519 C

给定一个长为 \(2n\) 的序列（\(n\le 5\times 10^5\)），\(1\sim n\) 的每个数都恰好出现 \(2\) 次。你需要使用 \(K\le 180\) 个栈，将 \(2n\) 个数依次压栈（你选择要放到哪个栈），使得可以通过每次弹出两个不同栈的栈顶的相同数字来把所有栈弹空。

保证序列从所有合法序列中等概率均匀随机生成。

考虑一些做法，我们把所有数第一次出现放到一个栈里，剩下的直接跑 LIS 划分，由于排列随机所以期望使用 \(2\sqrt n+O(1)\) 个栈。

我们可以把所有数按照第二次出现的位置分块，每 \(x\) 个分一块，把它们对应的第一次出现的所有数都放到一个栈里，把它们分开放到 \(x\) 个栈里。由于之后的块完全在之前的块之后，我们可以直接复用 \(x\) 个栈，这样就需要 \(\lceil\frac{n}{x}\rceil+x\) 个栈。

两个做法可以拼接，注意到后 \(x\) 个栈实际上只需要满足可以按照第一次出现的顺序依次取出，所以进行 LIS 划分可以做到 \(O(\lceil\frac{n}{x}\rceil+2\sqrt x)\) 个栈，也就是 \(O(n^{1/3})\)，实际上不能通过。

发现取最后面一组的时候，前面的 \(\lceil\frac{n}{x}\rceil-1\) 个栈实际上在偷懒，所以实际上可以想到

RRRRRRL4
RRRRRL
RRRRL
RRRL
RRL
RL

的结构。我们从左往右遍历，对第二次出现的位置进行 LIS 划分，如果数量超过 cur 了就新开一行 cur++，只需要 28 行代码。

P3347 [ZJOI2015] 醉熏熏的幻想乡

可以建出费用流，只有源点向左部点的边有费用，那么最短路的长度就等于对应左部边的费用，所以答案显然是 \(\int cost~dflow\) 其中 \(flow\) 表示所有边的单位费用都不超过 \(cost\) 时的最大流。考虑如何求出 \(f:cost\to flow\) 的函数，如果单位费用为 \(\lambda\)，那么一条左部边的最大流量就是 \(\min(c[i],\frac{\lambda-b[i]}{2a[i]})\)，特别的如果 \(a[i]=0\) 那么会在 \(\lambda\) 走到 \(b[i]\) 时突变成 \(c[i]\)。

如果每一条边的流量都是凸的，那么全体割的大小都是凸的，其交集也就是最小割自然也是凸的。所以，我们可以把每条边的流量-cost 折线在 \(b[i]\) 处断开，又因为 \(b[i]\in\{0,1,2,3\}\)，所以 \(cost\to flow\) 的函数在 \((0,1),(1,2),(2,3),(3,+\infty)\) 四个区间内分别上凸。

如果确定了全体左部边是否在最小割里面，那么右部边的方案就唯一确定了，而左部边显然不可能中途满流也就是最小割只会变化 \(O(n)\) 次，所以段内可以被划分成 \(O(n)\) 段一次函数。然后考虑分治，假如我们要求区间 \((l,r)\) 内的线段，考虑求出 \(l+\epsilon\) 和 \(r-\epsilon\) 处的两条线段的交点 \(mid\)，然后考察 \(mid+\epsilon\) 处的线段是否和 \(r-\epsilon\) 处是一条直线，若不是则按中心点向下递归即可。时间复杂度是 \(n\) 次 Dinic。

260521 B 淇

有 \(n\) 个人，初始随机给一个人发一个足球，然后当第 \(i\) 个人拿球时他有 \(p_{i,j}\) 的概率传球给 \(j\)。当所有人都传了偶数次球时游戏结束，问结束前的期望传球次数。

\(n\le 16\)，\(p_{i,j}\) 等概率均匀随机从模 \(998244353\) 的域内选取。

考虑朴素 dp：设 \(f_{S,i}\) 表示 \(S\) 内的人传了奇数次球，最后球在 \(i\) 脚下，期望还能传多少次。终止状态 \(f_{\varnothing,i}=0\)，转移 \(f_{S,i}=1+\sum_{j}P(i,j)f_{S\oplus\{i\},j}\quad\text{for }S\ne \varnothing\)，答案 \(ans=1+\sum_{i,j}P(i,j)f_{\{i\},j}\)。统一可以写成：

\[ \begin{align*} x_i&=1+\sum_{j}P(i,j)f_{\{i\},j}\\ f_{S,i}&=1+\sum_{j}P(i,j)f_{S\oplus \{i\},j}-[S=\varnothing]x_i \end{align*} \]

这样状态有 \(n2^n\) 个，直接解方程只能做到 \(O(n^38^n)\)。考虑到式子中有一个位运算卷积，想到 fwt，所以给式子两边对 \(S\) 做异或 fwt：

\[ \hat f_{S,i}=[S=\varnothing]2^n-x_i+\sum_{j}P(i,j)(-1)^{[i\in S]}\hat f_{S,j} \]

记矩阵 \(E_s\) 为 \(e_{i,i}=(-1)^{[i\in S]}\) 的对角矩阵，那么对于 \(x\ne \varnothing\)，上式为

\[ X=(E_sP-I)\hat F_s \]

对于 \(x=\varnothing\)，上式为

\[ X=2^n\textbf{1}+(P-I)\hat F_\varnothing \]

注意到 \(F_\varnothing=\frac{1}{2^n}\sum \hat F_s=0\)，所以将上面两个式子移项，相加：

\[ \Big(\sum_{S\ne \varnothing}(E_SP-I)^{-1}+(P-I)^{-1}\Big)X-(P-I)^{-1}(2^n\textbf{1})=\sum \hat F_S=\textbf{0}\\ X=((P-I)B+I)^{-1}(2^n\textbf{1}) \]

需要 \(2^n\) 次求逆，复杂度 \(O(n^32^n)\)。

P6789 寒妖王

发现最大基环树森林其实也可以像 kruskal 一样从大往小加边。考虑正难则反，一条边不被加入当且仅当比它大的边形成了一个同时包含 \(u,v\) 的有环的连通块，或者 \(u,v\) 所处的两个连通块分别有环。枚举边，有环连通块数用连通块减去树，树可以用逐点迭代，复杂度 \(O(mn^22^n)\)。

qoj6184 Atcoder Problem

只有第二个限制仍然是简单的，只需枚举解除限制的一位然后简单做即可。本题考虑对第一个限制使用 burnside 引理，转化为环分解。设 \(f_i\) 表示考虑了前 \(i\) 个数形成的环分解，那么我们可以删去最后一个数，如果环长 \(\ge 2\) 那么有转移 \(f_i\gets (i-1)(i-2)f_{i-2}+(i-1)(m+1)f_{i-2}\) 否则 \(f_{i}\gets f_{i-1}\)。

然后同时处理第二个限制，我们在最外层枚举解除限制的一位，那么只需要在刚刚的 dp 中再记录 \(3\) 个 \(0/1\) 分别表示奇环数量的奇偶性，第 \(k\) 位有没有遇到填 \(0\) 的，第 \(k\) 位的奇偶性，时间复杂度 \(O(n\log m)\)。

P4189 [CTSC2010] 星际旅行

贪心策略比较显然。

P15246 [WC2026] 猫和老鼠

先变换坐标系转化成向右和向上走，机器猫就是水平和竖直的线段。如果要想让杰瑞必然被抓住一次，就需要让一些线段形成一段分界线，通过手模和分讨可以观察出分界线合法的条件：将水平线段定向为左到右，竖直线段定向为上到下，那么下一条线段开头必须在上一条线段末尾的左上方。

可以用二维偏序优化建图，那么 \(k=1\) 的答案就是最短路。若 \(k>1\)，那么需要存在 \(k\) 条不交的分界线，此条件显然充分，必要性考虑如果分界线数量不够，我们把 \(<k\) 条分界线都扔了，剩下的东西不形成分界线，根据定义，杰瑞可以以 \(0\) 的代价穿过这一坨。于是建出图跑原始对偶即可，实际上是 \(k\) 遍最短路，复杂度 \(O(Tnk\log ^2n)\)。

CF1830F The Third Grace

KTT 是一种 \(O((n+m)\log^3 n+q\log n)\) 支持区间 \(x_i\) 加正数，区间查询 \(\max\{k_ix_i+b_i\}\) 的数据结构，具体就是对每个区间额外维护一个阈值 \(lim\) 表示再加多少会改变最大值所在的直线，均摊分析是这个复杂度。

据说常数非常小，具体可见本算法在 \(2200\) ms 内通过了本题的 \(n,m=10^6\)。

P5693 EI 的第六分块

由于最大子段和维护的 \(3\) 个信息都是关于长度和区间加标记的一次函数，所以也可以用 KTT。

260526 B 网络流

如果知道起点和终点 \((s,t)\)，那么答案形如 \(s\to t\) 路径走奇数次，其余边走偶数次。对于一棵子树，只要 \(\min(x,sum+x)\ge 0\) 就可以将子树以 \(2(sz-1)\) 的代价下界做完。考察 \(s\to t\) 路径上的边要走几次，如果某条边在起点方向的子树的 \(sum<0\) 那么至少要走 \(3\) 次，其余 \(1\) 次，我们尝试构造到这个下界。考虑一个 \(3\) 次边的极长连续段，我们第一次走过去，把所有 \(sum\ge 0\) 的子树吃了，\(a>b\) 的节点吃了，然后走回去，把剩下 \(<0\) 的吃了即可。起点和终点可以通过一次 dp 得到。

CF2229G Roadworks

发现一定是走到左边或右边第一个更大的位置进行停留，所以转移是 \(O(1)\) 的。

CF2229H Wowee Binary String

一段区间合法当且仅当存在问号或者有偶数个 1。考虑对子序列 dp，由于有前面的限制所以似乎要用一个集合来记录所有能匹配到的位置（非确定自动机），但发现这时不必的。设 \(s_i\) 表示前缀 1 个数的奇偶性，那么对于 \(s_i\) 相同的若干位置，我们显然只需要最左边的那个，所以只需要记两个位置即可，这样状态数就是 \(O(n^2)\) 的。

260528 A

给你一个长为 \(n+1\) 的序列 \(a\)，每次你可以交换 \(i\in [1,n]\) 和 \(n+1\) 两个位置的值，问最少操作次数使得 \([1,n]\) 单调不降。

\(n\le 2\times 10^5\)

如果序列中没有重复数字，那么直接枚举最终状态的 \(n+1\) 位置的值，然后贡献就是 \(n+1+k-c_1-2[a_{n+1}\ne b_{n+1}]\)。如果有重复数字，由于 \(b\) 中的重复数字可以任意交换，因此一定可以变成一个环，自环还是贪心匹配。这里需要对 \(n+1\) 处理边界，由于包含 \(n+1\) 的环的贡献更低，我们更愿意把自环调整成非自环，所以最终答案就是 \(n+1+k-c_1-c_{all}-2[a_{n+1}\ne b_{n+1}]-[a_{n+1}=b_{n+1}\wedge pos_a(a_{n+1})\ne pos_b(a_{n+1})]\)。\(k\) 可以用线段树分治简单维护，其他的也是简单维护。

260528 B

有一个长为 \(n\) 的排列 \(a\)。定义一次操作为：选出 \(a\) 的前缀最大值，把它们拉出来放到序列末尾。请对于每个 \(k\in [1,n]\) 求出数字 \([k,n]\) 相对有序的最小时刻。

\(n\le 6.8\times 10^7\)

发现插入一个更小的数不会影响更大的数的全部过程，所以考虑从大到小依次插入。由于 \(ans_i\le ans_{i+1}+1\) 因此考虑 \(i\) 能否跟着 \(i+1\) 直接完成。考虑 \(ans_{i+1}-1\) 次操作后，\(i+1\) 一定不在开头，因此设开头为 \(x\)，发现充要条件就是此时 \(i\) 位于 \(x\) 和 \(i+1\) 中间。

然后尝试发现 \(x\) 成为开头就需要任意时刻不能成为非开头的前缀最大值，进而简化分讨，发现 \(i,i+1,x\) 的循环移位不会改变，所以判定是容易的。

260528 C

交互库有一个隐藏的无向连通图，每次你可以询问一个边集 \(E'\) 和一个点 \(p\)，交互库回答你 \(E'\) 能否将 \(0\) 和 \(p\) 连通。你需要在 \(3\times 10^4\) 次询问内确定这个 \(n,m\le 600\) 的图。交互库是非自适应的。

考虑链怎么做，可以按随机顺序加点，维护点把链划分成的若干段，每段内的边。加入一个点时，先二分出所在的段，然后枚举段内的所有边并尝试删除，判断它被划分到左边还是右边。由于加入 \(i\) 个点之后的段长期望是 \(\frac{n}{i}\) 的，所以复杂度 \(O(n\log n)\)。

考虑树怎么做，仍然随机加点，维护前缀虚树。如果当前加的点 \(p\) 没有被之前的虚树连通，那么二分出 \(p\) 到虚树之间链上的所有边，形成一条新的链；否则直接二分出 \(p\) 所在的链。插入所有点后，按照链产生的顺序依次做链的子问题，需要先二分出链的父亲是谁。

考虑图怎么做，发现直接做上面的过程就可以得到一棵生成树，然后按照 dfs 序处理所有点，二分出所有非树边，然后再二分 dfs 序得到非树边的另一端。