题目链接:https://vjudge.net/contest/519146
B - Best Relay Team
水题。
D - Distinctive Character
题意
给n(n<=100000)个长为k(k<=20)的01串,定义两个01串的相似度为相同位的个数,找一个长为k的01串使得与这n个01串相似度的最大值最小。
思路
将有一位不同的两个01串连边,将一开始给定的n个01串入队,使用bfs解决,答案为最后入队的01串。bfs的每轮扩展都会增加一位不同(相似度减一),这样最后遇到的点就是距离一开始的n个01串的“最近距离”最远的。
(可以将这个图理解为k维超立方体,两个点之间不同的位数就是两个点之间的曼哈顿距离,每次bfs都扩展一个曼哈顿距离。)
J - Judging Moose
水题。
I - Import Spaghetti
题意
抛弃较为繁琐的读入后就是求有向图最小环并输出任意一个。
思路
一开始写了个dfs,发现dfs找最小环是错的,bfs才行。
// TODO: 最小环专题