2021.12.13~2021.12.19 一周小结

CF1416F Showing Off

题意：

$n\cdot m$ $A$ $B$ $A$ $w(i,j)$ $B$ 的每个元素为一个方向 L/R/D/U
$(i,j)$ $B_{i,j}=L$ $(i,j-1)$ $S_{i,j}$ $(i,j)$ $A_{i,j}$ $S$ $A$ $B$ $S$
$A$ $n\cdot m\le 10^5,S_i>1$ 。

题解：

$S$ $S$ 依次增大。

$S$ $S$ $S$ 小。

$S$ $S_i=x$ $S$ dinic $O(nm\sqrt{nm})$ 的了。

CF1368G Shifting Dominoes

题意：

$n\times m$ $1\times 2$ $2|n\times m$ 。现在你需要执行以下操作：
移去恰好一个骨牌。
将其他骨牌沿着其长边进行移动。
你需要保证每张骨牌的最终位置与初始位置至少有一个交点。
$n\cdot m\le 2\cdot 10^5$ 。

题解：

讲一下经典套路：骨牌的移动可以转化为空格的移动。我们把空格移动的起始点向终止点连边，这张图构成外向森林。并且：按行+列的奇偶性黑白染色后，黑图和白图互不相交。

$(dfn_u,dfn_v)$ $(dfn_u+sz_u-1, dfn_v+sz_v-1)$ 这个平面。我们把所有矩形预处理出来，扫描线求出矩形面积并即是答案。

CF1392H ZS Shuffles Cards

题意：

$n+m$ $n$ $1,2,\cdots,n$ $m$ 张牌是鬼牌。现在我们打乱这些牌，然后开始抽牌游戏，每一轮你可以抽一张牌：
$x$ $x$ $S$ ；
$S$ $[1,n]$ $n$ 个数，那么抽牌游戏结束。
$n,m\le 2\times 10^6$ 。

题解：

首先，我们称上一次抽到鬼牌之后的步骤到这次抽到鬼牌为止称为一个周期。我们可以得到：期望轮数=期望周期数乘以每个周期的期望长度。

周期的期望长度：枚举是第几张牌抽到鬼牌，利用组合数可以轻松计算。

min-max 容斥 $T$ $T$ $\frac {|T|}{|T|+m}$ ，而期望周期数就是它的倒数。

CF1534G A New Beginning

题意：

$(0,0)$ $1$
$n$ $i$ $(x_i,y_i)$ $n$ $(X,Y)$ $(x,y)$ $\max(|X-x|,|Y-y|)$
$1\leq n\leq8\times10^5;0\leq x_i,y_i\leq10^9;$

题解：

$(X,Y)$ 到折线的最小切比雪夫距离的性质 $x+y=X+Y$ 的交点处取得最小值，因为不管是往左还是往右走都会使一维变大。

DP $f_{i,x}$ $x+y=x_i+y_i$ $x$ $x_i+y_i$ 从小到大转移。如下：

f_{i,x}=|x-x_i|+\min_{x'\in[0,a_i+b_i-a_{i-1}-b_{i-1}]}{ f_{i-1,x-x'} }

$min$ ，一个是加一个绝对值函数。

$f_i(x)$ $|x-x_i|'<0$ $a_i+b_i-a_{i-1}-b_{i-1}$ $f'\le 0$ 。

这里我们使用 slope trick 技巧：由于绝对值函数增加的只有很有限个位置的二阶差分，因此我们用一个堆，存下所有差分增加一的位置（可重）。为了能方便地找到峰值的位置，我们把它拆成两个堆，分别存放峰值左边的差分增长点和峰值右边的差分增长点，其中右边的这个堆还要维护一个整体偏移量。

$0$ $1$ 的位置，可能能起到左移低谷的作用。详见代码：


x
1
priority_queue<int> L; L.push(a[p[1]]);
2
priority_queue<int, vector<int>, greater<int> > R; R.push(a[p[1]]);
3
int del = 0; ll as = 0;
4
for (int i = 2; i <= n; i++)
5
{
6
    del += a[p[i]] + b[p[i]] - a[p[i - 1]] - b[p[i - 1]];
7
    int x = a[p[i]], l = L.top(), r = R.top() + del;
8
    if (x < l) L.pop(), L.push(x), L.push(x), R.push(l - del), as += l - x;
9
    else if (x > r) R.pop(), R.push(x - del), R.push(x - del), L.push(r), as += x - r;
10
    else L.push(x), R.push(x - del);
11
}