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

2407. Bucket Brigade

农场上起火了，奶牛们正在紧急赶去灭火！
农场可以用一个像这样的10×10的字符方阵来描述：

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


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

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

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

样例输出
7

数据范围限制

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

思路

这题算是一题水题，只要用B、L的x相减然后求绝对值加B、L的y相减然后求绝对值再减一。
然后用特判，看一下B、R、L三点是否能连成一条直线，并且R在B、L中间那么再把原来算出来的值加2。

核心代码

这里我就给出特判的代码了

if(bx==rx&&rx==lx&&((ry>by&&ry<ly)||(ry<by&&ry>ly)))
	ans+=2;
if(by==ry&&ry==ly&&((rx>bx&&rx<lx)||(rx<bx&&rx>lx)))
	ans+=2;

代码信息

时间复杂度	总时间
Θ（1）	200

2408. 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

思路

这题定义一个out数组用来存能从i出去的数量，in数组用来存能从i进来的数量。把ans的初始值赋值为-1。从i~n循环，如果i没有能出去的方法并且ans不等于-1，就把ans=-1，break掉循环。但如果只是i没有能出去的方法那么就把ans的值更换为i。

核心代码

for(int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		out[a]++;
		in[b]++; 
	}
	int ans=-1;
	for(int i=1;i<=n;i++) 
	{
		if(out[i]==0&&ans!=-1){ans=-1;break;}
		if(out[i]==0)ans=i;
	}

2409. 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
数据范围限制

2≤N≤25
0≤K≤25

思路

想法

这道题算是一道数学题，要我们证明同一特性的叶子节点必有同样的祖先这一 结论_ 1，如果成立那就输出“yes”，否则就“no”。我们先设这一特性成立，那么就又得出一个结论_2——特性完全不同的叶子节点必有不同的祖先。再根据这个结论枚举任意两种 特性所拥有子节点 （题目中给的是子节点所拥有特性，所以我们要转换，并将特性字符串改成数字不用在意顺序），会有三种情况，一是没子节点重叠，不用理会，因为这两个不同性质成功分成两个不同的结点中；二是子节点完全重叠，并且多数覆盖少数，也不用理会，因为这两个不同性质成功分成一个相同的结点中；三是子节点重叠，并且两者没完全覆盖，这种情况就有违背于上没的结论，就输出“no”，因为重叠部分满足结论_1，而双方未重叠部分又满足结论_2，矛盾。

实现

想法清楚后，再来看看如果实现。
实现代码有两个难点， 一是转换“子节点所拥有特性”为“特性所拥有子节点”;二是那三种情况的实现

核心代码

在这里我就上第二个难点的核心代码给大家参考：

for(int i=1;i<=bj[0][0];i++){
    for(int j=1;j<=bj[0][0];j++){//任意两种特性所拥有子节点
        if(i!=j){
            int o;
            if(b[i][0]>b[j][0])o=i;
            else o=j;
            int js=0,js1=0;//js表示重叠了几个，js1表示是否重叠
            for(int k=1;k<=b[o][0];k++){
                for(int l=1;l<=b[i+j-o][0];l++){
                    if(b[o][k]==b[i+j-o][l]){
                        js++;
                        js1=1;
                        break;
                    }
                }
            }
            if(js1==1&&js<b[i+j-o][0]){//重叠了并且两者没完全覆盖
                printf("no");//矛盾，输出“no”
                return 0;
            }
        }
    }
}
printf("yes");//证明不可能不成立，代表成立；