2019搜索训练

概述

训练于 2019-11-01 18:30 星期五举行,共有$latex 7$题

没什么好说的,就是锻炼一下建模和编程实现的能力

把 $Snacks$ 视为节点,客人的喜好视为边,如果存在包含$latex C$个节点的 连通块 则这 $latex C$ 块糖可以满足 $latex C-1$ 人

只要将所有连通块所包含的糖的数量减去连通块的数量就是开心的客人的数量,再拿客人总数去减,就得到答案

仔细看题发现,任何人只能从一个人那里得到书,只会给一个人书.

研究一下发现,必然每个节点都在某个环上

同一个环上的点对应的答案是一致的,就是这个环的长度

方法很多

求从 $latex 1$ 开始的命令传播顺序,每个人的下属数量(包括自己),和每个人在命令传播顺序中的索引(序号)

对于询问可以直接查表

对 $latex 4\times n \times m$种状态 bfs