AtCoder Beginner Contest 180 题解

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,Y1018,2A109,B109

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

E – Traveling Salesman among Aerial Cities

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

N17

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

F – Unbranched

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

  1. n 个点,m 条边,最大连通块的大小为 l
  2. 无自环;
  3. 每个点的度数都不超过 2

n,m,l300

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

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

  1. 加入一个大小为 k 的环;
  2. 加入一个大小为 k(kl) 的直线段。

同时,考虑到我们需要除去同构的环和直线,可以推出大小为 k 的非同构圆排列,直线排列数量分别是 (k1)!2,k!2 (除以二是因为需要去除对称的情况)。我们再每次从剩余的 ni 个点中挑出 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 ,事实上就是找到了本质相同的图的一种最小表示法(所有连通块中标号最小的点构成的排列唯一确定),从而消解了枚举过程中的冗余情况。

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇