Skip to content

Latest commit

 

History

History
151 lines (97 loc) · 9.17 KB

2021.12.13~12.19 一周小结.md

File metadata and controls

151 lines (97 loc) · 9.17 KB
Raw

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$ 的位置，可能能起到左移低谷的作用。详见代码：

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

CF1598G The Sum of Good Numbers

题意：

给你一个不含 $0$ 的字符串 $s$，然后给你一个整数 $x$，请你可以找到一个三元组 $(a, b, c)$，使得 $s_{a, b} + s_{b + 1, c} = x$，输出两行，第一行为 $a, b$，第二行为 $b + 1, c$，保证有解。$s,x\le 10^6$。

题解：

先将问题转换为判定性问题：枚举分界点，左边和右边至少有一边是 $|x|$ 位数或者 $|x|-1$ 位数，而不是这么多位数的一边，一定是 $|x|-|lcp(x,y)|$ 或者 $|x|-|lcp(x,y)|-1$。

现在的问题就变成了如何快速判定两个区间的和是否等于 $x$。我们随机产生几个质数，计算出左边的数和右边的数和 $x$ 对 $p$ 取模的余数，即可快速判断。总复杂度 $O(n)$。

CF1603E A Perfect Problem

CF1558E Down Below

题意：

给定一张无向图 $G$，除了 $1$ 节点每个节点有两个权值 $a_i,b_i$。你初始在 $1$ 节点，有一个权值 $val$，你可以从 $u$ 移动到 $v$ 当且仅当：

  • $u,v\in G$
  • 你当前的 $val&lt;a_v$
  • 如果这不是第一次移动，移动到 $u$ 前的一个节点不能是 $v$

移动了之后，$val\leftarrow val+b_v$。你可以重复经过一个点，但是你无法重复获得 $b$ 的加成。你需要经过所有的点，问你初始 $val$ 至少是多少。数据范围 $n\le 10^3,m\le 2\times 10^3$，保证图联通。任何点的度数都 $\ge 2$。

题解：

首先二分答案，考虑如何判断。假设当前已经确定可以到达的集合为 $S$。那么用 dfs 增广 $S$ 的情况分为以下三种：

  1. 搜到了一个在 $S$ 内的点。这种情况显然可以直接将栈内所有数加入 $S$。
  2. 搜到了一个在栈内的点。这种情况下我们可以从这个环上绕回 $S$ 内，因此也将整个栈加入 $S$。
  3. 回溯回了 $S$。这种情况下啥也不能做，并且啥也不做的总复杂度还是对的，因为遍历到的点不会被其他的深搜遍历到。

因此直接按照上面的 dfs 来增广 $S$ 即可。$O(nm\log{V})$。

CF1556H DIY Tree

题意：

给出 ${n}$ 个点的无向带权完全图，找出以下条件的最小生成树：

第 ${i(1\le i\le k)}$ 个点的度数 $\le d_i$

输出满足条件的生成树的最小权值。$k\le 5,n\le 50,v\le 100$。

题解：

首先给出一个很正确的做法：五层 wqs 二分！emmmmmmmmmm

再不加解释地给出题解做法：MST 是拟阵问题，$2^{10}$ 枚举了前 $5$ 个点间连边情况后的度数限制也是一个拟阵问题，因此把边权倒过来，求最大拟阵交即可。