26.9.3 比赛记录
图论。这场时间太少了,一道都没有做出来。
A P8186
这题是 Floyd,但凡看出来这题是 Floyd 就好做了。
原来的礼物分配是如何变到最优解的,可以证明,一定存在这样一种方式,构造出一个环,让环上的牛按顺序把自己的礼物给下一个牛,从而达成最优解。
每头牛拿到的礼物都是不劣于原来的礼物的,所以如果礼物更不好了,就不要连边,否则就连边。用 Floyd 跑传递闭包,如果连成了一个环(也就是 可以到 , 也可以到 ),就说明有解。把最好的有解礼物输出即可。
B P8191
区完了,连最小生成树模板都看不出来。
这题的特点是 的范围很小,可以减少很多种情况。假如有一左一右两个点 A 和 B,还有一个点 C 在 A 的左边,和 A 同一行,很显然 B 和 C 连边一定不优,直接排除。我们枚举 行中的两行,把点按照 排序成为一行,然后只需要把相邻的点之间添加连边即可。之后正常跑 Kruskal。
C P10278
这题就是一道大%你。首先一个柱子和另一个柱子连边,当且仅当它们的 坐标值中有且仅有一个相同。我们把这样的柱子连边,形成一个环,之后从一个起点开始遍历,计算出每个柱子到起点的路径长度(注意是只能按一个方向,比如顺时针)。然后对于每一次行走,我们找出起点和终点在哪两个柱子间的栅栏上(用二分查找),之后我们就能计算出起点和终点之间顺时针走和逆时针走的路径长度,比较哪一个更小,就往哪个方向走。我们可以计算出这条路径上经过的柱子编号,可以把环上的柱子按照顺序依次编号,这样一个路径上的编号就是连续的。把路径上所有经过的柱子答案统计 。区间加,用差分数组解决,最后对整个查分数组求一次前缀和,输出答案。
D P9013
赛时想出了差不多的思路,可惜没调出来。
每个字母被换成另一个字母,相当于建一条有向边。合法的只有 种情况:环(强连通)、树(内向)、基环树(内向)。像一个节点有两个出边这种情况,可以直接判无解。
每次找一个连通块,判断它是环、树、基环树的哪一种情况。边数是点数减一就是树,入度全为 就是环,其余情况则是基环树。
然后手动模拟一下,树对答案的贡献是边数;环需要先打破成树,因此答案是边数加一;基环树可以构造出最优方案对答案贡献是边数。将所有连通块的答案累加即可。
还有一种特殊情况,目标串把 个字母都用上了,并且原串和目标串不相同,这种就是没有给我们留空余的地方,直接判无解。