M-SOLUTIONS Programming Contest 2020(atcoder) pros:5/6/6 rk:249

没有专题

没有比赛

Codeforces Round 659 1C

标签：图论、状压dp

题意：两个字符串S、T，字符集大小20，每次可以从S中选任意多个相同字符，将他们变成另一个字符，问最小多少次可以将S变成T。

思路：将每个字符作为一个点，如果存在字符$s_i = a$ 且$t_i = b$ 建立一条a→b的有向边，计这个图为$G_1$。

1、观察可以发现，如果一个弱联通图的最优解不是链状（若所有操作都满足上一次操作选择的边的终点等于下一次操作的起点，则是链状），则一定存在一个操作数相同的链状方案。证明：显然每个点都至少要被一条边覆盖，如果不是链状，则一定有两条边指向相同点，此时可以把先操作的边的目标改为后操作的边的起点，重复这样调整，最终会得到一个操作数相同的链状解。

2、现在我们可以用一个序列{$a_n$}来表示答案，$a_1,a_2,\ldots,a_n$表示依次执行$a_1$→$a_2$,$a_2$→$a_3$,…,$a_{n-1}$→$a_n$，

序列合法 iff 任意$G_1$中的边u→v，存在i，j满足i<j且$a_i = u,a_j = v$