欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-12 12:29:07
...

2407. Bucket Brigade

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

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

字符'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是唯一既会飞又会心灵感应的。

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

像上图这样每一种进化出的新特性都恰好在树中的一条边上产生(也就是说,在整个进化历史中仅在一个时间点产生),这样的进化树被称为是“合法的”。例如,如果斑点这一特性在两个不同分支中均进化产生,这棵进化树就不是合法的。给定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");//证明不可能不成立,代表成立;