2020.04.01【NOIP普及组】模拟赛C组22 总结

2020.04.01【NOIP普及组】模拟赛C组22 总结
第一题：Bucket Brigade

题目描述
农场上起火了，奶牛们正在紧急赶去灭火！
农场可以用一个像这样的10×10的字符方阵来描述：
..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........
字符'B'表示正着火的牛棚。字符'L'表示一个湖，而字符'R'表示农场上的一块巨大岩石。奶牛们想要沿着一条湖到牛棚之间的路径组成一条“水桶传递队列”，这样她们就可以沿着这条路径传递水桶来帮助灭火。当两头奶牛在东南西北四个方向上相邻时水桶可以在她们之间传递。这对于湖边的奶牛也是对的——奶牛只能在紧挨着湖的时候才能用水桶从湖里取水。类似地，奶牛只能在紧挨着牛棚的时候才能用水去灭牛棚的火。
请帮助求出奶牛们为了组成这样的“水桶传递队列”需要占据的'.'格子的最小数量。奶牛不能站在岩石所在的方格之内，此外保证牛棚和湖不是相邻的。

输入
输入包含10行，每行10个字符，描述这个农场的布局。输入保证图案中恰有一个字符'B'、一个字符'L'以及一个字符'R'。

输出
输出一个整数，为组成一条可行的水桶传递队列所需要的奶牛的最小数量。

样例输入
..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........

样例输出
7

数据范围限制

提示
在这个例子中，以下是其中一个可行的方案，使用了最小数量的奶牛（7）：
..........
..........
..........
..B.......
..C.......
..CC.R....
...CCC....
.....C....
.....L....
..........

方法：我用的是记忆化搜索，满分。正解：数学 。
设$b_{i,j}$bi,j​是起点$L$L到$(i,j)$(i,j)这个点的最短距离，
则
$b_{i,j}=min(b_{i-1,j},b_{i,j-1},b_{i+1,j},b_{i,j+1})$bi,j​=min(bi−1,j​,bi,j−1​,bi+1,j​,bi,j+1​)。
$b_{L_{i},L_{j}}=0$bLi​,Lj​​=0。
上述式子必须在$i$i$\not=$​=$R_i$Ri​,$j$j$\not=$​=$R_j$Rj​才能递推。
第二题：Milk Factory

题目描述
牛奶生意正红红火火！Farmer John的牛奶加工厂内有N个加工站，编号为1…N（1≤N≤100），以及N−1条通道，每条连接某两个加工站。（通道建设很昂贵，所以Farmer John选择使用了最小数量的通道，使得从每个加工站出发都可以到达所有其他加工站）。
为了创新和提升效率，Farmer John在每条通道上安装了传送带。不幸的是，当他意识到传送带是单向的已经太晚了，现在每条通道只能沿着一个方向通行了！所以现在的情况不再是从每个加工站出发都能够到达其他加工站了。
然而，Farmer John认为事情可能还不算完全失败，只要至少还存在一个加工站i满足从其他每个加工站出发都可以到达加工站i。注意从其他任意一个加工站j前往加工站i可能会经过i和j之间的一些中间站点。请帮助Farmer John求出是否存在这样的加工站i。

输入
输入的第一行包含一个整数N，为加工站的数量。以下N−1行每行包含两个空格分隔的整数ai和bi，满足1≤ai,bi≤N以及ai≠bi。这表示有一条从加工站ai向加工站bi移动的传送带，仅允许沿从ai到bi的方向移动。

输出
如果存在加工站i满足可以从任意其他加工站出发都可以到达加工站i，输出最小的满足条件的i。否则，输出−1。

样例输入
3
1 2
3 2

样例输出
2

数据范围限制

方法：先用$floyd$floyd预处理，然后直接判断。时间复杂度：$O(n^3)$O(n3) 。
$floyd$floyd：
设$f_{i,j}$fi,j​表示$i$i到$j$j是否连通。
则$f_{i,j}=1(f_{i,k}=1⋀f_{k,j}=1)$fi,j​=1(fi,k​=1⋀fk,j​=1)。
最后只要看是否所有其他点到点$i$i是否连通就行了。
$f_{j,i}=1(1\leq j\leq n)$fj,i​=1(1≤j≤n)
当所有$j$j不等于$i$i时上述式子都成立，则输出$i$i。
第三题：Cow Evolution
下面题目的图片如下：

题目描述
现在是3019年，在过去的一千年里发生了不计其数的牛类进化，产生了具有各种有趣特性的奶牛。
牛类进化的记录可以用一棵树来表示，起源是位于树根位置的没有特殊特性的奶牛。树上每一个产生后代的结点，有可能所有的奶牛都进化出了一种新的特性（比如说喷火（fire breathing），如下图所示，其中所有斑点（spots）奶牛最后都能喷火），或者是奶牛种群产生了分支进化，其中有些进化出了新的特性（比如，飞（flying）），有的没有。

树底部的叶结点表示3019年所有产生的奶牛的子种群。没有不同的叶结点（子种群）具有完全相同的一组特性。例如，子种群#1是没有特殊特性的奶牛，子种群#3是能够心灵感应的（telepathic）并且会飞的奶牛。相比之下，子种群#2是会飞但不能心灵感应的奶牛。子种群#3是唯一既会飞又会心灵感应的。
像上图这样每一种进化出的新特性都恰好在树中的一条边上产生（也就是说，在整个进化历史中仅在一个时间点产生），这样的进化树被称为是“合法的”。例如，如果斑点这一特性在两个不同分支中均进化产生，这棵进化树就不是合法的。给定3019年奶牛子种群的描述，请判断是否这可以由一棵合法的进化树所解释。

输入
输入的第一行包含子种群的数量N（2≤N≤25）。以下N行每行描述一个子种群。每行包含一个整数K（0≤K≤25），之后是K个该子种群奶牛所拥有的特性。特性是由至多20个小写字母（a..z）组成的字符串。没有两个子种群拥有完全相同的特性。

输出
如果可能构造一棵可以解释所有子种群产生途径的进化树，输出"yes"，否则输出"no"。

样例输入
4
2 spots firebreathing
0
1 flying
2 telepathic flying

样例输出
yes

数据范围限制

方法：不懂。直接输出Yes能得50分 。