[atcoder abc180]解题报告

又好久都没更博客了……

最近的 abc 最后一题画风都有点不太对啊(

比赛链接

A – box

水题

B – Various distances

水题。记得用 long double,不然精度要炸。

C – Cream puff

水题

D – Takahashi Unevolved

贪心,先乘,直到乘以 $A$ 增加的值大于 $B$ 的时候后面就一直加 $B$,即当 $(A-1)X\ge B$ 的时候就一直加 $B$ 就可以了。

不过在判断 $(A-1)X\ge B$ 的时候要爆 long long……无奈之下我就套了个高精度板子上去。

E – Traveling Salesman among Aerial Cities

水题。直接把 TSP 状压 dp 板子套上去就可以了。

F – Unbranched

嘛这个题画风就不太对了……

一开始去想了一下可不可以生成函数搞,类似于整数划分这种,但是想到还可以有环,以及这个题 $n\le 300$ 比较小,那就考虑 dp 算了(

设 $dp(n,m,lim)$ 表示还剩下 $n$ 个点和 $m$ 条边没用,最大的连通分量点数是否等于 $L$,$lim=1$ 表示达到了,$lim=0$ 表示还没有。

转移其实很简单……容易发现初值就是 $dp(i,0,1)=1,i\in [1,n]$,然后每次转移就拿 $k$ 个点组成一个新的连通分量,以及用这 $k$ 个点组成一个环还是一条链。

组成一个环,那么首先要满足的条件就是 $k\ge 2$。并且如果 $k\ge 3$ 的时候,因为这个环顺时针读还是逆时针读是等价的,那么这个环的总数就是 $\frac{(k-1)!}{2}$。然后要考虑哪些标号在这个环上,还要乘以一个组合数 $C_{n-1}^{k-1}$。那么,dp 方程就是 $dp(i,j) += dp(i-k,j-k) \times \frac{(k-1)!}{2} \times C_{n-1}^{k-1}$. 当然,当 $k=2$ 的时候就不用除以 $2$ 了。

组成一个链,那么首先要满足的条件就是 $k\ge 1$。并且如果 $k\ge 2$ 的时候,因为这个链从头到尾读还是从尾到头读是等价的,那么这个链的总数就是 $\frac{k!}{2}$。同样要乘以一个组合数 $C_{n-1}^{k-1}$。那么,dp 方程就是 $dp(i,j) += dp(i-k,j-k+1) \times \frac{k!}{2} \times C_{n-1}^{k-1}$。当然,当 $k=1$ 的时候就不用除以 $2$ 了。

上面 dp 方程没有把 lim 这一维加进去。加上去之后写一发记忆化搜索实际上很贱单,只要中间枚举的时候当前决策用了 $L$ 个点,那么之后的搜索过程 $lim=1$ 一直成立。那么这个题就做完了~

 

发表评论