ABC180 题解
[toc]
AC 代码
A – box
B – Various distances
C – Cream puff
D – Takahashi Unevolved
给定四个正整数 X,Y,A,B ,要求选择以下一项操作,执行 K 轮,求 Kmax 使得 X<Y 。
- 操作一:将 X 乘上 A 。
- 操作二:将 X 加上 B 。
X,Y≤1018,2≤A≤109,B≤109 。
考虑函数图像 fa(x)=ax 和 f(x)=x+b ,显然两者有一个交点,交点之前 fb 更大,交点之后 fa 更大。因此只需要在交点左侧执行操作一,越过交点后执行操作二就能使操作轮次最大。
E – Traveling Salesman among Aerial Cities
三维空间中有 N 个城市,从城市 (x,y,z) 到达城市 (p,q,r) 的距离为 |p−a|+|q−b|+max(0,r−c) ,求遍历每座城市然后返回起点的最短距离。
N≤17 。
很显然的旅行商问题,直接状压。由于每个点都要经过,因此固定起点为 1 ,就能写出一个 O(n22n) 的 dp 了。假设 dp[i][j] ,i 表示当前已经经过的城市集合,j 表示最后到达的城市,暴力转移即可。
F – Unbranched
求满足以下条件的无向无权图的个数:
- 有 n 个点,m 条边,最大连通块的大小为 l ;
- 无自环;
- 每个点的度数都不超过 2 。
n,m,l≤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≤l) 的直线段。
同时,考虑到我们需要除去同构的环和直线,可以推出大小为 k 的非同构圆排列,直线排列数量分别是 (k−1)!2,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 ,事实上就是找到了本质相同的图的一种最小表示法(所有连通块中标号最小的点构成的排列唯一确定),从而消解了枚举过程中的冗余情况。