USACO 2019 US Open Contest, Bronze

- 日理万妓 2023-06-23 10:59 21阅读 0赞

## USACO 2019 US Open Contest, Bronze ##

## Problem 1. Bucket Brigade ##

农场上起火了，奶牛们正在紧急赶去灭火！

农场可以用一个像这样的10×1010×10的字符方阵来描述：

..........
    ..........
    ..........
    ..B.......
    ..........
    .....R....
    ..........
    ..........
    .....L....
    ..........

字符'B'表示正着火的牛棚。字符'L'表示一个湖，而字符'R'表示农场上的一块巨大岩石。

奶牛们想要沿着一条湖到牛棚之间的路径组成一条“水桶传递队列”，这样她们就可以沿着这条路径传递水桶来帮助灭火。当两头奶牛在东南西北四个方向上相邻时水桶可以在她们之间传递。这对于湖边的奶牛也是对的——奶牛只能在紧挨着湖的时候才能用水桶从湖里取水。类似地，奶牛只能在紧挨着牛棚的时候才能用水去灭牛棚的火。

请帮助求出奶牛们为了组成这样的“水桶传递队列”需要占据的'.'格子的最小数量。

奶牛不能站在岩石所在的方格之内，此外保证牛棚和湖不是相邻的。

输入格式（文件名：buckets.in）：

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

输出格式（文件名：buckets.out）：

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

输入样例：

..........
    ..........
    ..........
    ..B.......
    ..........
    .....R....
    ..........
    ..........
    .....L....
    ..........

输出样例：

在这个例子中，以下是一个可行的方案，使用了最小数量的奶牛（7）：

..........
    ..........
    ..........
    ..B.......
    ..C.......
    ..CC.R....
    ...CCC....
    .....C....
    .....L....
    ..........

供题：Brian Dean

> 思路：本题需要确定一下R、B、L三者的位置关系。
> 
> 1. B、L在同一行或者同一列，并且R在B、L之间；
> 
> 2. B、L在同一行或者同一列，并且R在B、L之外；
> 
> 3. B、L不在同一行并且同一列。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70][]

#include<iostream>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    char a[15][15];
    int abs2(int m, int n)//求绝对值 
    {
    	if(m > n) return m-n;
    	else return n-m;
    }
    int main()
    {
    	freopen("buckets.in","r",stdin);
    	freopen("buckets.out","w",stdout);
    	int sum = 0,x1,y1,x2,y2,x3,y3;
    	for(int i = 1; i <= 10; ++i)//记录B、R、L的位置 
    	{
    		for(int j = 1; j <= 10; ++j)
    		{
    			cin >> a[i][j];
    			if(a[i][j]=='B')
    			{
    				x1 = i;
    				y1 = j;
    			}
    			if(a[i][j] == 'R')
    			{
    				x2 = i;
    				y2 = j;
    			}
    			if(a[i][j] == 'L')
    			{
    				x3 = i;
    				y3 = j;
    			}
    		}
    	}
    	if(((x1 == x2 && x2 == x3) || (y1 == y2 && y2 == y3)) && (((x2-x1)*(x2-x3)<0)||((y2-y1)*(y2-y3)<0)))//如果为同一行或者同一列并且R在B、L之间 
    		sum = abs2(x1,x3)+abs2(y1,y3)+1;
    	else if(((x1 == x2 && x2 == x3) || (y1 == y2 && y2 == y3)) && (((x2-x1)*(x2-x3)>0)||((y2-y1)*(y2-y3)>0))) //如果为同一行或者同一列并且R在B、L之外 
    		sum = abs2(x1,x3)+abs2(y1,y3)-1;
    	else//B、L 不在同一行同一列 
    		sum = abs2(x1,x3)+abs2(y1,y3)-1;
    	cout << sum << endl;
    	fclose(stdin);
    	fclose(stdout);
    	return 0;	
    }

> 官方解答：
> 
> (Analysis by Brian Dean)
> 
> The key insight into solving this problem is that the answer can be computed easily using just the locations of the three objects in the scene.
> 
> To simplify things, imagine there is no rock. In this case, the answer is just the difference in xx coordinate between the barn and lake, plus the difference in yy coordinate (minus one, since the endpoints don't count). This is sometimes known as "Manhattan" distance, since in downtown Manhattan the streets form a grid and you can only get from one location to another by moving along the xx or yy directions following the grid, not diagonally.
> 
> If we add the rock back to the picture, this actually rarely affects the answer, since we can always route around the rock unless the rock is in the same vertical or horizontal line as the barn and lake and lies between the two, in which case our path takes two additional steps to route around the rock.

#include <iostream>
    #include <fstream>
    #include <cmath>
    using namespace std;
     
    int barn_i, barn_j, rock_i, rock_j, lake_i, lake_j;
     
    int main(void)
    {
      ifstream fin ("buckets.in");
      for (int i=0; i<10; i++) {
        string s;
        fin >> s;
        for (int j=0; j<10; j++) {
          if (s[j] == 'B') { barn_i = i; barn_j = j; }
          if (s[j] == 'R') { rock_i = i; rock_j = j; }
          if (s[j] == 'L') { lake_i = i; lake_j = j; }
        }
      }
     
      ofstream fout ("buckets.out");
      int dist_br = abs(barn_i - rock_i) + abs(barn_j - rock_j);
      int dist_bl = abs(barn_i - lake_i) + abs(barn_j - lake_j);
      int dist_rl = abs(rock_i - lake_i) + abs(rock_j - lake_j);
    
      // Check for special case where rock is between barn and lake  
      if ((barn_i==lake_i || barn_j==lake_j) && dist_bl == dist_br + dist_rl)
        fout << dist_bl + 1 << "\n";
      else
        fout << dist_bl - 1 << "\n";
     
      return 0;
    }

##  ##

## Problem 2. Milk Factory ##

牛奶生意正红红火火！Farmer John的牛奶加工厂内有NN个加工站，编号为1…N1…N（1≤N≤1001≤N≤100），以及N−1N−1条通道，每条连接某两个加工站。（通道建设很昂贵，所以Farmer John选择使用了最小数量的通道，使得从每个加工站出发都可以到达所有其他加工站）。

为了创新和提升效率，Farmer John在每条通道上安装了传送带。不幸的是，当他意识到传送带是单向的已经太晚了，现在每条通道只能沿着一个方向通行了！所以现在的情况不再是从每个加工站出发都能够到达其他加工站了。

然而，Farmer John认为事情可能还不算完全失败，只要至少还存在一个加工站ii满足从其他每个加工站出发都可以到达加工站ii。注意从其他任意一个加工站jj前往加工站ii可能会经过ii和jj之间的一些中间站点。请帮助Farmer John求出是否存在这样的加工站ii。

输入格式（文件名：factory.in）：

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

输出格式（文件名：factory.out）：

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

输出样例：

3
    1 2
    3 2

输出样例：

供题：Dhruv Rohatgi

> 思路：自己多举几个例子，看是否有什么规律。发现只要a中有重复的出发点，都不存在，否则就输出最小的a中没有出现过的点。

#include<iostream>
    #include<algorithm>
    #include<cstdio>
    using namespace std;
    int a[105],b[105];
    int main()
    {
    	freopen("factory.in","r",stdin);
    	freopen("factory.out","w",stdout);
    	int n;
    	cin >> n;
    	for(int i = 1; i < n; ++i)
    	{
    		cin >> a[i] >> b[i];
    	}
    	sort(a+1,a+n); //a[1~n-1]排序 
     	for(int i = 1; i < n-1; ++i)//如果出发点有重复的，就一定不存在 
     	{
     		if(a[i] == a[i+1]){
     			cout << "-1" << endl;
     			return 0;
    		 }
    	}
    	for(int i = 1; i < n; ++i)//如果出发点没有重复的，就找到第一次没有出现过的出发点 
    	{
    		if(a[i] != i) {
     			cout << i << endl;
     			return 0;
    		 }
    	}
    	fclose(stdin);
    	fclose(stdout);
    	return 0;
    }

> 官方解答：(Analysis by Brian Dean)
> 
> This is a nice problem where the coding is straightforward once you have figured out the right structure to search for as an answer.
> 
> The abstract structure we are dealing with here is a tree --- a set of nn nodes connected by n−1 edges, where every node is reachable from every other node and there is no cycle. Trees are everywhere in computer science and you can expect to see them often in higher divisions.
> 
> Let's call a node with only incoming directed edges a "sink", since things can flow into it but not out. The short answer to the problem is that we need to see if our tree has a single unique sink, in which case this is the answer. Let's see if we can argue this:
> 
> 1. If all nodes in the tree can reach node x , then we claim node xx must be the unique sink. All nodes aside from x need at least one outgoing directed edge to be able to escape from them, so they aren't sinks. Further, node xx cannot have any outgoing edges, since if there was an edge x→then y couldn't reach x.
> 
> 2. If x is the unique sink, then all nodes in the tree can reach x. Suppose some node y cannot reach x. We know yy has an outgoing edge since it isn't a sink, so let's follow such an edge. This lands us on another node (say, z) which if not a sink must also have an outgoing edge, so let's follow such an edge. If we keep following outgoing edges until we no longer can, we inevitably must get stuck at a sink, since this is the only node with no outgoing edges (and we can't go around in cycles since a tree has no cycles). This means we have reached x, since x is the only sink.

> 接收点一定不能再指向其他的点,只能其他的点通过传播路径指向它。
> 
> 接收点一定不会出现在a中，并且只可能存在一个接收点，如果出现2个以上，则说明没有符合条件的点。

#include <iostream>
    #include <fstream>
    using namespace std;
     
    int N, incoming[101], outgoing[101];
     
    int main(void)
    {
      ifstream fin ("factory.in");
      fin >> N;
      for (int i=0; i<N-1; i++) {
        int a, b;
        fin >> a >> b;
        outgoing[a]++;
        incoming[b]++; 
      }
     
      ofstream fout ("factory.out");
      int answer = -1;
      for (int i=1; i<=N; i++) {
        if (outgoing[i]==0 && answer != -1 ) { answer = -1; break; } // found two sinks -- bad!
        if (outgoing[i]==0) answer = i;  // found first sink; remember it
      }
      fout << answer << "\n";
      return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191218173526732.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc=,size_16,color_FFFFFF,t_70