ABC199 题解

[toc]

AC代码

A – Square Inequality

B – Intersection

C – IPFL

给定一个字符串 $s$ ，有两种操作：

交换两个字符；

交换前一半字符和后一半字符。

$q$ 次操作后，问最终的字符串。

设置一个标志位记录操作 $2$ 的奇偶，若为偶则正常执行操作 $1$ ；若为奇，则执行操作 $1$ 时需要注意此时交换的前后两部分相反。

D – RGB Coloring 2

给定一个 $N$ 个点 $M$ 条边的无向无权图，每个点都不一样。现在对这个图上的点进行染色（颜色集大小为 $3$ ），询问一共有几种不同染色方案。

$N\leq 20$ 。

直接暴搜是 $O(3^n)$ 肯定不行，但是我们发现，如果我们按照 $dfs$ 序枚举每个点的颜色，那么除了第一个点以外的每个点最多只有 $2$ 种可能，复杂度为 $O(n2^n)$ 。

E – Permutation

询问满足以下条件的排列个数：

大小为 $N$ ；

前 $X_i$ 个数中不超过 $Z_i$ 个数 $\leq Y_i$ （这种限制一共 $M$ 个）。

$N\leq 18, M\leq 100$ 。

$N\leq 18$ 提示我们显然可以状压，我们用 $dp_S$ 表示前 $|S|$ 个数恰好是集合 $S$ 时的合法情况数，转移考虑每次向 $S$ 中加入一个数 $x$ ，并且满足前 $|S|+1$ 个数的限制即可。这利用了前 $|S|$ 个数的限制不会被后续加入的数影响的性质。

F – Graph Smoothing

给定一个 $N$ 个点，$M$ 条边的无向无权图，每个点初始有一个点权 $A_i$ 。询问执行以下操作 $K$ 次后，每个点的点权是多少？每次操作指的是：独立等概率地选择一条边，然后将这条边两个端点的点权改写为他们的算术平均值。

$N\leq 100, K\leq 10^9$ 。

考虑每一次操作对所有点的影响，由于每一次操作都是等概率地选中 $M$ 条边中的一条且每一轮操作独立，因此我们可以写出每一个点在这一轮操作后的期望权值：
$$
\begin{aligned}
dp[u][i+1]=\frac{1}{M}(\sum_{v}\frac{dp[u][i]+dp[v][i]}{2} + (M-|v|)dp[u][i])
\end{aligned}
$$
$dp[u][i]$ 表示节点 $u$ 在第 $i$ 轮操作后的期望，上式中 $v$ 是与点 $u$ 相邻的点集。

注意到这可以看作是一个矩阵形式，$K$ 次迭代实际上就是这个矩阵的 $K$ 次方，因此我们可以使用矩阵快速幂在 $O(N^3\log(K))$ 的复杂度下解决本问题。