ABC180 题解

[toc]

AC代码

A – box

B – Various distances

C – Cream puff

D – Takahashi Unevolved

给定四个正整数 $X,Y,A,B$ ，要求选择以下一项操作，执行 $K$ 轮，求 $K_{\max}$ 使得 $X<Y$ 。

操作一：将 $X$ 乘上 $A$ 。

操作二：将 $X$ 加上 $B$ 。

$X,Y\leq 10^{18},2\leq A\leq 10^9,B\leq10^9$ 。

考虑函数图像 $f_a(x)=ax$ 和 $f(x)=x+b$ ，显然两者有一个交点，交点之前 $f_b$ 更大，交点之后 $f_a$ 更大。因此只需要在交点左侧执行操作一，越过交点后执行操作二就能使操作轮次最大。

E – Traveling Salesman among Aerial Cities

三维空间中有 $N$ 个城市，从城市 $(x,y,z)$ 到达城市 $(p,q,r)$ 的距离为 $|p-a|+|q-b|+\max(0,r-c)$ ，求遍历每座城市然后返回起点的最短距离。

$N\leq 17$ 。

很显然的旅行商问题，直接状压。由于每个点都要经过，因此固定起点为 $1$ ，就能写出一个 $O(n^22^n)$ 的dp了。假设 $dp[i][j]$ ，$i$ 表示当前已经经过的城市集合，$j$ 表示最后到达的城市，暴力转移即可。

F – Unbranched

求满足以下条件的无向无权图的个数：

有 $n$ 个点，$m$ 条边，最大连通块的大小为 $l$ ；

无自环；

每个点的度数都不超过 $2$ 。

$n,m,l\leq 300$ 。

首先，容易想到通过容斥将这个问题归约到一个子问题：$f(n,m,l)$ 表示最大连通块大小不超过 $l$ 且有 $n$ 个点 $m$ 条边的图的数量，那么本题答案显然为 $f(n,m,l)-f(n,m,l-1)$ 。

然后考虑如何求出 $f$ 。不难想到一个 $O(nml)$ 的dp：我们用 $dp[i][j]$ 表示含有 $i$ 个点和 $j$ 条边且最大连通块大小不超过 $l$ 的图的数量，转移方程考虑题面中的限制条件：每个点的度数都不超过 $2$ ，这说明这个图一定是由一堆直线段和环构成的（独立点可以视为退化的直线段）。因此我们一共有两类不同的转移：

加入一个大小为 $k$ 的环；
加入一个大小为 $k(k\leq l)$ 的直线段。

同时，考虑到我们需要除去同构的环和直线，可以推出大小为 $k$ 的非同构圆排列，直线排列数量分别是 $\frac{(k-1)!}{2},\frac{k!}{2}$ （除以二是因为需要去除对称的情况）。我们再每次从剩余的 $n-i$ 个点中挑出 $k$ 个就能够写出转移式：

dp[i + k][j + k] += dp[i][j] * binom(n - i, k) * (k - 1)! / 2; // k = 2, 3, ..., n
dp[i + k][j + k - 1] += dp[i][j] * binom(n - i, k) * k! / 2;   // k = 1, 2, ..., n

注意要特判一下 $k=1,2$ 两种情况，就做完了。。。但是这样你就会发现无法通过第二个样例：n=4, m=3, k=2 ，答案为 $6$ ，但是上述 $dp$ 却算出了 $12$ 。

迷茫了一下午后，通过各种途径终于发现了上方的组合式子是存在问题的，比如 $[[1,2],[3,4]]$ 和 $[[3,4],[1,2]]$ 会被重复枚举两次，但是他们交换顺序其实并不会影响图的总体结构。为了解决这一问题，我们可以引入一个小 $trick$ ：每次枚举之前，我们先固定当前剩余点中最小的那个，假设我们一定会选择该点。这样的话，我们就不会出现上方这类重复情况了，因为每一次枚举都必定含有当前最小点，那么每个连通块就可以看作是一个排好序的数组，其次序是唯一确定的，所有重复情况都可以被规约到这个最小表示中。

因此本题的正解只需要对上方的dp作出一点微小的修改：

dp[i + k][j + k] += dp[i][j] * binom(n - i - 1, k - 1) * (k - 1)! / 2; // k = 2, 3, ..., n
dp[i + k][j + k - 1] += dp[i][j] * binom(n - i - 1, k - 1) * k! / 2;   // k = 1, 2, ..., n

仔细回想一下这个小 $trick$ ，事实上就是找到了本质相同的图的一种最小表示法（所有连通块中标号最小的点构成的排列唯一确定），从而消解了枚举过程中的冗余情况。