CF913F Strongly Connected Tournament

题意

\(n\) 个点，对于 \(i<j\)，有 \(\frac{a}{b}\) 的概率由 \(i\rightarrow j\) 连边，有 \(1-\frac{a}{b}\) 的概率由 \(j\rightarrow i\) 连边。对这张完全图缩点，对于每个强连通分量重新加边，使得最后每个强连通分量内只剩一个点，求期望的连边数。

\(n\le 5000\)

Sol

概率期望dp，竞赛图缩点性质。

设有 \(i\) 个点时的期望连边数是 \(f_i\)，枚举最弱的强连通分量，设其大小为 \(j\)，由于是完全图那么其内部已经连有 \(\frac{1}{2}j(j-1)\) 条边，考虑剩下的 \(i-j\) 个点都要打赢 \(j\) 个点，于是连边数量 \(j(i-j)\)。

考虑这种情况的形成概率，即设 \(c_j\) 为能形成 \(j\) 大小为 \(j\) 的强连通分量的概率，\(d_{i,j}\) 为 \(i\) 个点中有 \(j\) 个点被其它 \(i-j\) 个点都打败的概率。

于是有转移：

\[\large \begin{align*} f_i&=\sum\limits_{j=1}^i c_j d_{i,j}\left(\frac{j(j-1)}{2}+j(i-j)+f_j+f_{i-j}\right)\\ f_i&=\sum\limits_{j=1}^{i-1} c_j d_{i,j}\left(\frac{j(j-1)}{2}+j(i-j)+f_j+f_{i-j}\right)+c_id_{i,i}\left(f_i+\frac{i(i-1)}{2}\right)\\ (1-c_id_{i,i})f_i&=\sum\limits_{j=1}^{i-1} c_j d_{i,j}\left(\frac{j(j-1)}{2}+j(i-j)+f_j+f_{i-j}\right)+c_id_{i,i}\frac{i(i-1)}{2}\\ f_i&=\frac{1}{1-c_id_{i,i}}\left(\sum\limits_{j=1}^{i-1} c_j d_{i,j}\left(\frac{j(j-1)}{2}+j(i-j)+f_j+f_{i-j}\right)+c_id_{i,i}\frac{i(i-1)}{2}\right) \end{align*} \]

对于 \(c_i\)，考虑简单容斥，枚举有多少个点没有被打败过，得到无法形成强连通分量的概率。

\[\large c_i=1-\sum\limits_{j=1}^{i-1}c_jd_{i,j} \]

对于 \(d_{i,j}\) 考虑，按从小到大的顺序将点加入，判断加入 \(j\) 还是加入 \(i-j\) 的部分。

\[d_{i,j}=(1-p)^jd_{i-1,j}+p^{i-1}d_{i-1}{j-1} \]

CF1383F Special Edges

题意

给定一张 \(n\le10^4\) 个点有向图，每条边的容量范围为 \([0,25]\)，有 \(k\le 10\) 条特殊边其容量会变。

现在有 \(q\) 次询问，每次询问给定 \(k\) 条边的新容量，求出此时的最大流。

Sol

网络流，最小割，格雷码

由于最大流等于最小割，每条边只有割和不割两种状态，联系到 \(k\) 很小所以自然考虑枚举 \(2^k\) 种情况。

• 如果钦定不割一条边，只需要使其流量变成 \(+\infty\)，即此时的 \(25\)。
• 如果钦定割一条边，只需要使其流量变成 \(0\)，最后加上对应边权即可。

但是对于 \(2^k\) 都跑一次 dinic 就太慢了，考虑如果每次只该边一条边割或者不割的状态，格雷码恰好满足这个性质。首先先以最大边权跑一边 dinic，在残余网络上进行操作。

对于不割一条边，直接加边即可。

对于割一条边，强制退流，并清空流量。

最后每次询问依然按照格雷码加入删除边即可。

[ARC082E] ConvexScore

题意

平面上 \(n\) 个点，对于一个可构成凸包的点集 \(S\)，其贡献是 \(2^k\)，\(k\) 是其内部或边上（不含顶点）的点数。

Sol

组合意义

\(2^k\) 的组合意义是枚举边上和内部的点是否选入集合，考虑对于 \(n\) 个点的集合 \(U\) 的子集 \(S\)，称子集 \(S\) 合法当且仅当其内部的某些点可以构成一个凸包并使剩下的点包括在这个凸包里面。

考虑简单容斥，总子集数量是 \(2^n\)，空集和一个点的集合不合法。

考虑如果一个集合的所有点都位于一条直线上，则无法构成凸包，剩下的情况，无论多少个点总是合法的。

考虑枚举这条直线的两端，判断线段上点数 \(x\)，如此一来这 \(x\) 个点的所有子集与端点的并是不合法的，数量为 \(2^x\)，这部分可以 \(n^3\) 求出。

答案是 \(2^n-n-1-\sum\limits_{x}2^x\)。

CF1810G The Maximum Prefix

题意

长为 \(n\le5000\) 的数组，\(a_i\) 有 \(p_i\) 的概率填 \(1\)，\(1-p_i\) 的概率填 \(-1\)。即数组最大前缀和（包括第 \(0\) 项在内）为 \(s\)，则可以获得 \(h_s\) 的分数。

对于每个 \(k\in[1,n]\) 求出数组长度为 \(k\) 时的期望分数。

Sol

期望概率 dp，正难则反，反推贡献系数。

考虑暴力的 dp，即考虑到第 \(i\) 位，当且前缀和为 \(j\)，最大前缀和为 \(k\) 期望分数，但是状态和复杂度都飞了。

正难则反，考虑倒着做，倒着做前缀和有良好的性质，考虑当前加入第 \(i\) 位，如果 \([i+1,k]\) 的最大前缀和为 \(j\)，当前 \(i\) 放数一定会使最大前缀和 变成 \(j-1\) 或 \(j+1\)。考虑 \(f_{i,j}\) 表示当前考虑到第 \(i\) 位，当前最大前缀和为 \(j\)，有转移：

\[f_{i,\max(j-1,0)}\rightarrow f_{i,\max(j-1,0)}+(1-p_i)f_{i+1,j} \]

\[f_{i,j+1}\rightarrow f_{i,j+1}+p_if_{i+1,j} \]

初始值为 \(f_{k+1,0}=1\)，答案为 \(\sum\limits_{i=0}^n f_{1,i}h_i\)。

这样做复杂度还是飞的，因为要考虑所有长度的答案。

注意到对于每一个 \(k\)，其终点的状态都是 \(f_{1,i}\)，他们的系数也大抵相同。

考虑类比倒着做的前缀和的性质，设 \(g_{i,j}\) 表示考虑到第 \(i\) 位，后 \([i+1,k]\) 位的前缀最大值需要为 \(j\) 的期望分数，初始令 \(g_{0,j}=h_j\)，有转移：

\[g_{i,j}=(1-p_i) g_{i-1,\max{j-1,0}}+p_ig_{i-1,j+1} \]

答案为 \(g_{k,0}\) 。本质上是将一个起点贡献多个终点变为多个起点贡献一个终点。

CF2004G Substring Compression

题意

给定长为 \(2\le n\le2\times10^5\) 的纯数字不含 0 字符串 \(s\) 和 \(k\)，你需要对 \(s\) 的每个长为 \(k\) 的连续子串 \(t\) 求出 \(f(t)\)：

\(f(t)\) 的含义为：将 \(t\) 分成 \(2p\) 份连续子串 \(t_1,t_2,\cdots ,t_{2p}\)，记 \(f(t)\) 的值为，对于所有 \(i\le p\)，写 \(t_{2i-1}\) 次字符串 \(t_{2i}\) 后拼接起来的字符串的最小长度。

即求出：$$f(t)=\min\limits_{\forall t_i,p} \left{\sum\limits_{i=1}^p t_{2i-1}\times|t_{2i}| \right}$$

前者为奇数段是字符串对应的数，后者为偶数段是字符串对应的长度。

Sol

参考了 这个视频的解法，orz Inaba_Meguru。

考虑如果 \(k=n\) 的情况如何处理：

有一个比较显然的贪心：奇数段 \(t_{2i-1}\) 的长度永远是 \(1\)，否则答案会更劣。

感性理解反证法证明，假设存在一个 \(i\) 使得我们要写 \(10x+y\) 次长为 \(l\) 的段，得到的长度是 \((10x+y)l\)，如果考虑把 \(10x+y\) 的最后一位 \(y\) 分配给 \(l\)，得到的新长度为:

\[x(l+1)=xl+x< xl+9xl<10xl+yl=(10x+y)l \]

知道了奇数段只能选一个就很好考虑了，设 \(f_i\) 表示考虑前 \(i\) 个位置，钦定 \(i\) 位置为偶数段的最后一位，即 \(i+1\) 为奇数段，不难得到转移：

\[f_i=\min_{j<i}\left\{f_j+s_{j+1}\times (i-j+1)\right\} \]

这样做是 \(O(n^2)\) 的，注意到奇数段受到靠前 \(j\) 的限制，考虑倒着转移，使奇数段和当前转移的 \(i\) 绑定，该变状态为 \(f_i\) 表示考虑了 \([i+1,n]\) 位，选择 \(i\) 位为奇数段的最小答案：

\[f_i=\min_{i<j} \left\{f_{j+1}+s_{i}\times(j-i)\right\}=\min_{i<j} \left\{f_{j+1}+j\times s_i\right\}-i\times s_{i} \]

由于 \(s_i\in [1,9]\)，所以可以记录 \(g_{s_i}=\min_{i<j}\left\{f_{j+1}+j\times s_i\right\}\)，转移变成 \(f_i=g_{s_i}-i\times s_i\)，这样复杂度是 \(O(n)\) 的，带个 \(9\) 的常数。

考虑 \(k\) 的限制，注意到我们的转移方式比较固定且具有结合律（可以先转移左边再转移右边，再用右边的 \(g_i\) 更新左边，与从右到左依次更新效果一样），可以用广义矩阵乘法，改 \(*/+\) 操作为 $\min/+ $，需要维护 \(f_i\) 和对应的 \(g_{s_i}\)，即维护 \(10\times 10\) 大小的矩阵：

考虑 \(i\) ，\(s_i=5\) 时矩阵 \(A_i\) 的样子，使 \(A_{mid+1,r}\) 右乘一个 \(A_{l,mid}\) 可以得到 \(A_{l,r}\)。

\[A_i=\begin{bmatrix} +\infty &i &2 i &3 i &4 i&5 i&6 i&7 i&8i &9i\\ +\infty&0&+\infty&+\infty&+\infty&+\infty&+\infty&+\infty&+\infty&+\infty&\\ +\infty&+\infty&0&+\infty&+\infty&+\infty&+\infty&+\infty&+\infty&+\infty&\\ +\infty&+\infty&+\infty&0&+\infty&+\infty&+\infty&+\infty&+\infty&+\infty&\\ +\infty&+\infty&+\infty&+\infty&0&+\infty&+\infty&+\infty&+\infty&+\infty&\\ -s_i\times i&+\infty&+\infty&+\infty&+\infty&0&+\infty&+\infty&+\infty&+\infty&\\ +\infty&+\infty&+\infty&+\infty&+\infty&+\infty&0&+\infty&+\infty&+\infty&\\ +\infty&+\infty&+\infty&+\infty&+\infty&+\infty&+\infty&0&+\infty&+\infty&\\ +\infty&+\infty&+\infty&+\infty&+\infty&+\infty&+\infty&+\infty&0&+\infty&\\ +\infty&+\infty&+\infty&+\infty&+\infty&+\infty&+\infty&+\infty&+\infty&0&\\ \end{bmatrix} \]

解释一下这样填的意义：

• \((0,0)\) ：即此时的 \(f_i\)，由于此时只有一个元素，所以没有答案填 \(+\infty\)。
• \((0,j)\) ：即此时的 \(g_j\)，此时候选只有 \(i\)，而 \(f_{i+1}=0\)，所以就是 \(i\times j\)。
• \((j,j)\) ：转移时 \(g_j\) 不更新的情况，需要保证仍然可以取 \(g_j\)。
• \((0,s_i)\) ：转移时得到 \(f_i\) 的答案需要 \(-i\times s_i\)。

考虑得到矩阵后如何计算答案，可以使用分块，块长为 \(k\)，维护块内前缀矩乘 \(pre_i\) 和后缀矩乘 \(suf_i\)。

\[pre_i=A_i\times pre_{i-1} \]

\[suf_i=suf_{i+1} \times A_i \]

对于考虑计算 \([i-k+1,i]\) 时的答案为 \(A_{i-k+1,i}\)：

• \(i \equiv 0\pmod k\) ，答案为 \(suf_i\)
• 其它情况，答案为 \(A_{i-k+1,i}=A_{kp+1,i}\times A_{i-k+1,kp}=pre_i\times suf_{i-k+1}\)。

时间复杂度 \(O(nm^3)\)，\(m\) 是矩阵的大小。

P3642 [APIO2016] 烟火表演

题意

一棵树，给每条边确定一个新边权，代价为新旧之差，使得根节点到每个叶子节点的距离相同，求最小代价。

Slope Trick 部分

本题解主要讲述的部分，简单了解什么 Slope Trick 可以看这篇博客。

记 \(f(x)\) 表示在当前节点将子树内所有叶子的燃烧时间统一为 \(x\) 的最小费用函数，\(g(y)\) 表示在当前节点的儿子节点将子树内所有叶子的燃烧时间统一为 \(y\) 的最小费用函数，\(w\) 为他们之间的边权，显然有转移方程：

\[f(x)=\sum\limits_{y\in son_x}\left( \min_{y} g(y)+|y+w-x|\right) \]

注意到 \(g(y)\) 显然是下凸的（感性理解，修改的值过大过小都不合适，严格的证明可以参考其它题解），于是便有上升段，最优答案的水平段 \([L,R]\) ，下降段，画出儿子的答案下凸包，研究一个儿子向父亲合并的过程，分为两部分：

• 儿子的凸包增加一条边的贡献，以下简称为加边操作。
• 将若干加完边的凸包在父亲处合并，以下简称为合并操作。

先考虑加边对于凸包的影响，改变 \(f(x)\) 的定义为 \(g(y)\) 加边后子树内的总代价，对 \(x\) 处于不同位置分情况讨论，以下每种分类讨论种对于 \(y+w\) 与 \(x\) 关系的方程：

前半部分统一为： \(f(x)=g(y)+x-y-w\)。

后半部分统一为： \(f(x)=g(y)+y+w-x\)。

注意一个隐藏条件：\(y\le x\)，也就是说只能选择 \(x\) 左边的位置作为转移点。

---

\(x<L\)

由于绝对值的存在，考虑对转移点位置分类讨论来确定最优情况。

• \(y+w\le x\)：

  注意到 \(g(y)-y\) 单调递减，其它不变，\(y=w-x\) 最优，\(f(x)=g(x-w)\)。

• \(x-w\le y\le x\)：

  \(y\) 每增大 \(1\)，由于斜率 \(k\le-1\)，所以 \(g(y)\) 减小值 \(\ge 1\)，所以 \(g(y)+y\) 单调递减，其它不变，取 \(y=x\) 最优，\(f(x)=g(x)+w\le g(x-w)\)。

综上所述，这种情况取 \(f(x)\) 选 \(x\) 作为转移点最优。

---

\(L\le x\le L+w\)

• \(y\le x-w\le L\)：

  \(g(y)\) 单调递减，\(y\) 越大越优，取 \(f(x)=g(x-w)\) 最优。

• \(x-w\le L\le y\le x\)：

  \(g(y)\) 不变，所以 \(y\) 越小越优，取 $ y=L$ 最优，\(f(x)=g(L)+L+w-x\)，由于 \(y\le L\) 段斜率 \(\le -1\)，\(g(x-w)-g(L)\ge L+w-x\)，所以第二种情况更优。

综上所述，这种情况取 \(f(x)\) 选 \(L\) 作为转移点最优。

---

\(L+w\le x\le R+w\)

• \(y\le L\le x-w\)：
  

  \(g(y)\) 单调递减， \(y\) 越大越优，取 \(y=L\) 最优，取 \(f(x)=g(L)+x-w-L\)。

• \(L+w\le x-w\le y\le x\)：
  

  \(g(y)\) 不变，\(y\) 越小越优，取 \(y=x-w\) 最优，\(f(x)=g(x-w)=g(L)\le g(L)+x-w-L\) ，比第一种优。

综上所述，这种情况取 \(f(x)\) 选 \(x-w\) 作为转移点最优。

---

\(R+w \le x\)

• \(y\le R\le x-w\)：
  

  \(g(y)\) 不变，\(y\) 越大越优，取 \(y=R\) 最优，\(f(x)=g(R)+x-w-R=g(L)+x-w-R\)。

• \(R\le x-w\le y\le x\)：
  

  \(g(y)+y\) 单调递增，取 \(y=x-w\) 最优，\(f(x)=g(x-w)\)，由于斜率不小于一，\(x-w-R\le g(x-w)-g(R)\)，所以不如第一种情况优。

综上所述，这种情况 \(f(x)\) 选 \(R\) 作为决策点最优。

---

所以总的转移方程为：

\[ f(x)=\begin{cases} g(x)+w &,\text{if } x\le L \\ g(L)+L+w-x &,\text{if } L\le x\le L+w\\ g(L) &,\text{if } L+w\le x\le R+w \\ g(L)+x-w-R &,\text{if } R+w\le x \end{cases}\]

加边合并

考虑如何快速实现 \(g(y)\) 的加边操作的更新以及儿子间的合并，分段来看：

• 对于 \(x\le L\) 来说，实际上是将 \(g(x)\) 的图像向上平移了 \(w\)。
• 对于 \(L\le x\le L+w\) 来说，实际上是插入了一条斜率为 \(-1\) 的直线 \(f(x)=-x+g(L)+L+w\)。
• 对于 \(L+w\le x\le R+w\) 来说，这段成为新的水平段，也是 \(f(x)\) 的最小答案，相当于把原来的 \([L,R]\) 向右平移了 \(w\)。
• 对于 $ R+w\le x $ 来说，相当于改变成了斜率为 \(1\) 的直线 \(f(x)=x+g(L)+x-w-R\)。

加边后的凸包有几个优良的性质：

• 代入端点值进行计算不难发现函数仍然是连续的。
• 每次加边后，凸包的左端斜率单调递增，右端斜率变成 \(1\)。
• \(f(0)\) 的值为边权和。

考虑合并凸包，暴力的方法是直接相加，瓶颈在于合并后对 \(f(x)\) 的维护更新。注意到凸包经过拐点斜率增加的性质，不妨认为经过每个拐点后斜率增加 \(1\)，不存在的段多个拐点重叠即可。

这样做的优点：

• 方便合并凸包，只需要把儿子的凸包拐点全塞给父亲即可。
• 容易找到某段特定斜率的起始点：合并完后右边最右端斜率变成 \(d\)，从右往左数 \(d\) 个可以找到 \(R\) 的位置，再往左一个可以找到 \(L\) 的位置。
• 知道斜率，截距 \(f(0)\)，可以推出第一段的表达式，知道每一个拐点的横坐标，就知道了整个凸包的表达式，从而可以算出 \(g(L)\)。

于是我们发现，只需要维护拐点的横坐标，就能知道 \([L,R]\) 的位置，和 \(g(L)\) 的大小，把我们需要的要素集齐了，而维护横坐标的合并只需要一个可并堆即可。

返回去考虑加边在可并堆上如何操作，根据大根堆的性质，从右往左一个部分一个部分维护：

• 对于 $ R+w\le x $ 来说，弹出儿子数量 \(d-1\) 个拐点就能使斜率变成 \(1\)。
• 对于 \(L+w\le x\le R+w\) 来说，弹出 \(d-1\) 次后的栈顶元素是 \(R\)，再弹出一次就是 \(L\)，弹出 \(L\)，\(R\) 后重新塞入 \(L+w\) 和 \(R+w\) 即可。
• 对于 \(L\le x\le L+w\) 来说，由于 \([L+w,R+w]\) 斜率为 \(0\)，所以前一段斜率必定是 \(-1\)，且必定包含 \([L,L+w]\)，上一步已经顺带完成了。
• 对于 \(x\le L\) 来说，只需要对 \(f(0)\) 增加 \(w\) 即可，横坐标不需要修改。

考虑最后答案的表示方法，对每个拐点按照右边线段斜率编号 \(0\) 到 \(k\)，于是有：

\[f(L)+\sum\limits_{i=0}^{k-1} i(x_i-x_{i+1})=f(0) \]

然后变形：

\[f(L)=f(0)-\sum\limits_{i=0}^{k-1} i(x_i-x_{i+1})=f(0)-\sum\limits_{i=0}^k ix_i-(i-1)x_i=f(0)-\sum\limits_{i=0}^k x_i \]

只需要所有边权之和减去 \(L\) 及以前的所有点的横坐标就是答案。