首页 > 其他分享 >BUPT 2022 Autumn Training #5

BUPT 2022 Autumn Training #5

时间:2022-10-05 22:22:54浏览次数:72  
标签:bfs Training 01 题意 水题 BUPT 距离 Autumn 入队

题目链接: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: 最小环专题

标签:bfs,Training,01,题意,水题,BUPT,距离,Autumn,入队
From: https://www.cnblogs.com/wild-chicken/p/16756582.html

相关文章