Codeforces 杂题选讲

讲师：PinkRabbit 时间：20210701 地点：福建师范大学附属中学

Example.1 724E. Goods transportation

题意：

$n$ $i$ $p_i$ $s_i$ 单位货物。
$1≤i<j≤n$ $i$ $j$ 。
$c$ 单位货物。不能反向运输，但是货物可以经过任意多个运输线路。
请求出总共最多能卖出去多少单位货物。
数据范围：n≤10^4。时间限制：2 s。Bonus：n≤10^6。

题解：

$O(n^2)$ 的且难以优化。

这时一个惊世骇俗的步骤登场了——由最大流等于最小割，然后用动态规划来优化！

根据最小割的第二种定义：

将原图划分为两个点集，使得他们之间的连边边权和最小。

$s$ $t$ $t$ $t$ 割掉或者是要切断中层的所有连边。

$f_{i,j}$ $i$ $s$ $j$ $t$ 的最小割，有

f_{i,j}=\min(f_{i,j-1}+ic+s_{i+j},f_{i-1,j}+p_{i+j})

于是这个及其震撼人心的 DP 就诞生了！

$a_{1\sim k}$ $s$ 连接的点集，有：

ans=\left(\sum_{i=1}^n p_i\sum_{i=1}^k(s_{a_i}-p_{a_i})+\right)+\left(\sum_{i=1}^k(a_i-1)c -\begin{pmatrix}k\\2\end{pmatrix}\cdot c\right)

提取一下：

ans=\sum_{i=1}^n p_i-\begin{pmatrix}k\\2\end{pmatrix}\cdot c-kc+\sum_{i=1}^k(s_{a_i}-p_{a_i}+a_ic)

$k$ $O(n\log n)$ 。

Example.2 802O. April Fools’ Problem (hard)

题意：

$n$ $a_{1∼n}$ $b_{1∼n}$ $k$ 。
$k$ $(p_i,q_i)$ $p_i≤q_i$ $p_{i-1}<p_i$ $q_{i-1}<q_i$ 。
$\sum_{i=1}^k a_{p_i} +\sum_{i=1}^k b_{q_i}$ 。
$n,k≤5×10^5$ 。时间限制：10 s。

题解：

$k$ 的限制怎么办？wqs 二分即可解决。

$a_i$ $b$ $-b_i$ $a$ 加入堆中。

$\log$ 呢？考虑更加暴力地模拟费用流，发现复杂度瓶颈在于最短路，用线段树来维护最短路即可。

Example.3 827F. Dirty Arkady’s Kitchen

题意：

$n$ $m$ $1$ $i$ $[l_i,r_i]$ $[l_i,r_i-1]$ 内），而且是禁止在一个点处停留的，也就是到达了一个点就必须选择一条出边继续走，经过一条边必须恰好花费 1 的时间，并且必须到达另一个端点。
$1$ $n$ 的最短路。
$n,m≤5×10^5$ $6$ s。

题解：

$4$ 条有向边。

$f_{x,0/1}$ $l$ $f_{u,l\&1}\ge l$ $r+1$ $f_{v,!(l\&1)}$ $v$ $[r+1,r_{v,1\sim?}]$ $l+1$ 。

$l$ $f>l$ $l$ $l+1$ 也就很显然了。

Example.4 908H. New Year and Boolean Bridges

题意：

$n$ $f(i,j)$ $i$ $j$ 。
$A_{n×n}$ 。
$A_{i,j}$ $i≠j$ $A, O, X$ $A_{i,i}$ 均为字符 -。
$u,v$ $u≠v$ ）：
$A_{u,v}$ A $f(u,v) \and f(v,u)=1$ 。
$A_{u,v}$ O $f(u,v) \or f(v,u)=1$ 。
$A_{u,v}$ X $f(u,v) \oplus f(v,u)=1$ 。
请求出满足条件的有向图的最小可能边数，或判定这样的图不存在。
$n≤47$ $5$ s。

题解：

考虑先将以 A 连接的进行缩点，如果同一个强连通分量内存在 X 就矛盾无解。

注意到，若一个强连通分量大小大于等于二，那么它会多产生一的代价；如果大小等于一，那么没有额外代价；那么我们只要尝试将可以合并的尽可能合并。

$\le \frac n2$ $2^{\frac n2}$ 是可以接受的！

$f=\sum_X judge(X)\cdot z^X$ $X$ 是否可以缩在一起（内部是否没有 X）。

$k$ $[z^U]f^k=1$ $n^3\cdot 2^{\frac n2}$ ，不可接受。

$n^2\cdot 2^{\frac n2}$ ，不可接受。

iFWT $2^{\frac n2}$ $n\cdot 2^{\frac n2}$ ，可接受。

FWT $M_{x,y}=(-1)^{\operatorname{popcount}(x\oplus y)}\cdot[x\and y=x]$ $f_X'=\sum (-1)^{\operatorname{popcount}(x\oplus y)}\cdot[Y\subseteq X]\cdot f_Y$ 。

这时我来吊打标算随机化 $50n^2$ 草过。

Example.5 1067D. Computer Game

题意：

$n$ $a_i$ $p_i$ 。
每秒可以玩一个游戏，如果成功了则获得收益，并且获得一次可以升级游戏的机会。
$b_i$ $a_i<b_i$ ）。
$t$ 秒游戏可以获得的期望收益的最大值。输出浮点数即可。
$n≤10^5$ $t≤10^10$ $1≤a_i<b_i≤10^{18}$ $0<p_i<1$ 。时间限制：3 s。

题解：

$p_i\cdot b_i$ 最大得，然后一直点那个。

$f_t$ $t$ 时间、没有升级时的最大期望收入，则：

f_t=\max_{i=1}^n(1-p_i)f_{t-1}+p_i(a_i+bp_{\max}\cdot(t-1))

变形一下：

f_t=\min_{i=1}^np_i\cdot(bp_{\max}\cdot t-f_{t-1})+f_{t-1}+p_ia_i-p_i\cdot bp_{\max}

$p_i\cdot x+p_ia_i-p_i\cdot bp_{\max}$ $f_{t-1}$ 看作常数，直接忽略）。

$\log$ 。

\begin{bmatrix}f_t\\t\\1\end{bmatrix}\times \begin{bmatrix} 1-p_i & 0 & 0 \\ p_i\cdot bp_{max} & 0 & 0 \\ -p_i\cdot bp_{max}+p_i\cdot a_i & 0 & 1 \end{bmatrix} =\begin{bmatrix}f_{t+1}\\t+1\\1\end{bmatrix}

Example.6 1239E. Turtle

题意：

$2$ $n$ $a_{i,j}$ 。
$(1,1)$ $(2,n)$ ，只能往下走和往右走。定义路径权值为路径上经过的数值之和，乌龟想要最大化这个权值。
你可以对棋盘上的数字重新排列，最小化乌龟可能获得的最大权值。
请构造达到这个最小值的方案。
$n≤25$ $0≤a_{i,j}≤5×10^4$ 。时间限制：5 s。

题解：

性质 1：第一行递增、第二行递减，证明使用交换法，显然不劣。

性质 2：乌龟要么走第一行，要么走第二行，证明考虑权值和的差分数组，即可证明是下凸的。

于是就可以愉快地背包拉！

Example.7 1270H. Number of Components

题意：

$n$ $a_1∼a_n$ $a_i$ 互不相同。
顺序对 $i<j$ $a_i<a_j$ $i,j$ 之间连一条无向边。
求图中连通块个数。
$q$ $a_i←x$ $a_i$ 互不相同。
$n,q≤5×10^5$ $1≤a_i,x≤10^6$ 。时间限制：8 s。

题解：

Example.8 1285F. Classical?

题意：

$n$ $a_1,a_2,…,a_n$ $max_{1≤i,j≤n} ⁡\operatorname{lcm}⁡(a_i,a_j)$ 。
$n,a_i≤10^5$ 。时间限制：1 s。

题解：

$\gcd$ $a_x \perp a_y$ $a_x\cdot a_y$ 最大的。

考虑从大到小加入一个栈中，如果存在栈中元素与当前元素互质，我们可以把这个元素及其之后所有元素弹出，因为显然没用了。

问题就转化为维护栈中是否有元素与当前元素互质，有：

\sum_{i=1}^n[gcd(a_i,m)=1]=\sum_{k|m}\mu(k)\sum_{i=1}^n[k|a_i]

$\sum_{i=1}^n[k|a_i]$ $\sum d=n\ln n$ 的。

$\ln$ $a$ $a$ $a_x \perp a_y$ $a_x\cdot a_y$ $\operatorname{lcm}$ 必然是可以拆成这样两部分。