Warning: session_start(): open(/tmp/sess_d020dc8a93a8c14cf93fb92125fb10b4, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/actions.php on line 38

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/lib/tpl/dokuwiki/main.php on line 12
2020-2021:teams:acm_life_from_zero:7.25-7.31 [CVBB ACM Team]

用户工具

站点工具


2020-2021:teams:acm_life_from_zero:7.25-7.31

2020/07/25-2020/07/31周报

团队训练

李元恺

题目

比赛

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$

袁熙

姜维翰

2020-2021/teams/acm_life_from_zero/7.25-7.31.1596172257.txt.gz · 最后更改: 2020/07/31 13:10 由 lak