USACO 2019 December Contest, Bronze

发表于 分类于 阅读次数： Valine：

比赛链接

第一题：

Cow Gymnastics

题目：

In order to improve their physical fitness, the cows have taken up gymnastics! Farmer John designates his favorite cow Bessie to coach the N other cows and to assess their progress as they learn various gymnastic skills. In each of K practice sessions (1≤K≤10), Bessie ranks the N cows according to their performance (1≤N≤20). Afterward, she is curious about the consistency in these rankings. A pair of two distinct cows is consistent if one cow did better than the other one in every practice session.

Help Bessie compute the total number of consistent pairs.

INPUT FORMAT (file gymnastics.in): The first line of the input file contains two positive integers K and N. The next K lines will each contain the integers 1…N in some order, indicating the rankings of the cows (cows are identified by the numbers 1…N). If A appears before B in one of these lines, that means cow A did better than cow B.

翻译：

为了提高健康水平，奶牛们开始进行体操训练了！Farmer John 选定了他最喜爱的奶牛 Bessie 来执教其他 N 头奶牛，同时评估她们学习不同的体操技术的进度。 K 次训练课的每一次（1≤K≤10），Bessie 都会根据 N 头奶牛的表现给她们进行排名（1≤N≤20）。之后，她对这些排名的一致性产生了好奇。称一对不同的奶牛是一致的，如果其中一头奶牛在每次训练课中都表现得都比另一头要好。

请帮助 Bessie 计算一致的奶牛的对数。

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

输入的第一行包含两个正整数 K 和 N。以下 K 行每行包含整数 1…N 的某种排列，表示奶牛们的排名（奶牛们用编号 1…N 进行区分）。如果在某一行中 A 出现在 B 之前，表示奶牛 A 表现得比奶牛 B 要好。

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

输入的第一行包含两个正整数 K 和 N。以下 K 行每行包含整数 1…N 的某种排列，表示奶牛们的排名（奶牛们用编号 1…N 进行区分）。如果在某一行中 A 出现在 B 之前，表示奶牛 A 表现得比奶牛 B 要好。

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

输出一行，包含一致的奶牛的对数。

输入样例：

3 4
4 1 2 3
4 1 3 2
4 2 1 3

输出样例：

4

一致的奶牛对为 (1,4)、(2,4)、(3,4) 和 (1,3).

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
ID: zhaojiayi
TASK: Cow Gymnastics
LANG: C++
*/
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[25][15];
int ans;
int main(){
	freopen("gymnastics.in","r",stdin);
	freopen("gymnastics.out","w",stdout);
	cin>>k>>n;
	int p;
	for(int i=1;i<=k;i++){
		for(int j=1;j<=n;j++){
			cin>>p;
			a[p][i]=j;
		}
	}
	bool book=false;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			book=true;
			if(j==i) continue;
			for(int w=1;w<=k;w++){
				if(a[i][w]>a[j][w]){
					book=false;
					break;
				}
			}
			if(book){
				ans++;
			}
		}
	}
	cout<<ans<<endl;
	fclose(stdin);
	fclose(stdout);
	return 0;
}

第二题：

Where Am I?

题目：

Farmer John has gone out for a walk down the road and thinks he may now be lost! Along the road there are N farms (1≤N≤100) in a row. Farms unfortunately do not have house numbers, making it hard for Farmer John to figure out his location along the road. However, each farm does have a colorful mailbox along the side of the road, so Farmer John hopes that if he looks at the colors of the mailboxes nearest to him, he can uniquely determine where he is.

Each mailbox color is specified by a letter in the range A..Z, so the sequence of N mailboxes down the road can be represented by a string of length N containing letters in the range A..Z. Some mailboxes may have the same colors as other mailboxes. Farmer John wants to know what is the smallest value of K such that if he looks at any sequence of K consecutive mailboxes, he can uniquely determine the location of that sequence along the road.

For example, suppose the sequence of mailboxes along the road is 'ABCDABC'. Farmer John cannot set K=3, since if he sees 'ABC', there are two possible locations along the road where this consecutive set of colors might be. The smallest value of K that works is K=4, since if he looks at any consecutive set of 4 mailboxes, this sequence of colors uniquely determines his position along the road.

翻译：

Farmer John 出门沿着马路散步，但是他现在发现可能迷路了！ 沿路有一排共 N 个农场（1≤N≤100）。不幸的是农场并没有编号，这使得 Farmer John 难以分辨他在这条路上所处的位置。然而，每个农场都沿路设有一个彩色的邮箱，所以 Farmer John 希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。

每个邮箱的颜色用 A..Z 之间的一个字母来指定，所以沿着道路的 N 个邮箱的序列可以用一个长为 N 的由字母 A..Z 组成的字符串来表示。某些邮箱可能会有相同的颜色。Farmer John 想要知道最小的 K 的值，使得他查看任意连续 K 个邮箱序列，他都可以唯一确定这一序列在道路上的位置。

例如，假设沿路的邮箱序列为 'ABCDABC' 。Farmer John 不能令 K=3，因为如果他看到了 'ABC'，沿路有两个这一连续颜色序列可能所在的位置。最小可行的 K 的值为 K=4，因为如果他查看任意连续 4 个邮箱，这一颜色序列可以唯一确定他在道路上的位置。

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

输入的第一行包含 N，第二行包含一个由 N 个字符组成的字符串，每个字符均在 A..Z 之内。

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

输出一行，包含一个整数，为可以解决 Farmer John 的问题的最小 K 值。

输入样例：

7
ABCDABC

输出样例：

4

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
ID: zhaojiayi
TASK: Where Am I?
LANG: C++
*/
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int ans=1;
int main(){
	freopen("whereami.in","r",stdin);
	freopen("whereami.out","w",stdout);
	cin>>n;
	cin>>s;
	int len=s.size();
	for(int i=0;i<len;i++){
		for(int j=i+1;j<len;j++){
			int cnt=1;
			bool b=false;
			while(s[i]==s[j]){
				b=true;
				i++;
				j++;
				cnt++;
			}
			if(b){
				i-=1;
				j-=1;
			}
			ans=max(ans,cnt);
		}
	}
	cout<<ans;
	fclose(stdin);
	fclose(stdout);
	return 0;
}

第三题：

Livestock Lineup

题目：

Every day, Farmer John milks his 8 dairy cows, named Bessie, Buttercup, Belinda, Beatrice, Bella, Blue, Betsy, and Sue. The cows are rather picky, unfortunately, and require that Farmer John milks them in an order that respects N constraints (1≤N≤7). Each constraint is of the form "X must be milked beside Y", stipulating that cow X must appear in the milking order either directly after cow Y or directly before cow Y.

Please help Farmer John determine an ordering of his cows that satisfies all of these required constraints. It is guaranteed that an ordering is always possible. If several orderings work, then please output the one that is alphabetically first. That is, the first cow should have the alphabetically lowest name of all possible cows that could appear first in any valid ordering. Among all orderings starting with this same alphabetically-first cow, the second cow should be alphabetically lowest among all possible valid orderings, and so on.

翻译：

每天，Farmer John 都要给他的 8 头奶牛挤奶。她们的名字分别是 Bessie，Buttercup，Belinda，Beatrice，Bella，Blue，Betsy，和 Sue。 不幸的是，这些奶牛相当难以伺候，她们要求 Farmer John 以一种符合 N 条限制的顺序给她们挤奶（1≤N≤7）。每条限制的形式为“X 必须紧邻着 Y 挤奶”，要求奶牛 X 在挤奶顺序中必须紧接在奶牛 Y 之后，或者紧接在奶牛 Y 之前。

请帮助 Farmer John 求出一种满足所有限制的奶牛挤奶顺序。保证这样的顺序是存在的。如果有多种顺序都满足要求，请输出字典序最小的一种。也就是说，第一头奶牛需要是所有可能排在任意合法奶牛顺序的第一位的奶牛中名字字典序最小的。在所有合法的以这头字典序最小的奶牛为首的奶牛顺序中，第二头奶牛需要是字典序最小的，以此类推。

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

输入的第一行包含 N。以下 N 行每行包含一句句子，以 "X must be milked beside Y" 的格式描述了一条限制，其中 X 和 Y 为 Farmer John 的某些奶牛的名字（上文列举了八个可能的名字）。

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

请用 8 行输出一个奶牛的顺序，每行输出一头奶牛的名字，满足所有的限制。如果由多种顺序符合要求，输出字典序最小的奶牛顺序。

输入样例：

3
Buttercup must be milked beside Bella
Blue must be milked beside Bella
Sue must be milked beside Beatrice

输出样例：

Beatrice
Sue
Belinda
Bessie
Betsy
Blue
Bella
Buttercup

代码 (20分) ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
/*
ID: zhaojiayi
TASK: Livestock Lineup
LANG: C++
*/
//Bessie=1,Buttercup=2,Belinda=3,Beatrice=4,Bella=5,Blue=6,Betsy=7,Sue=8
#include<bits/stdc++.h>
using namespace std;
int n;
string s[10];
int a[10][2];
bool book[10];
int ans[10];
bool killer=false;
bool check(){
	for(int i=1;i<=8;i++){
		if(a[ans[i]][0]!=0){
			if(a[ans[i]][0]!=ans[i-1]&&a[ans[i]][0]!=ans[i+1]) return false;
			else if(a[ans[i]][1]!=0){
				if(a[ans[i]][1]!=ans[i-1]&&a[ans[i]][1]!=ans[i+1]) return false;
			}
		}
	}
	return true;
}
void f(int step){
	if(killer) return;
	if(step>=8){
		//cout<<11111111111;
		if(check()){
			
			for(int i=1;i<=8;i++){
				
				if(i==4) cout<<"Bessie"<<endl;
				else if(ans[i]==7) cout<<"Buttercup"<<endl;
				else if(ans[i]==2) cout<<"Belinda"<<endl;
				else if(ans[i]==1) cout<<"Beatrice"<<endl;
				else if(ans[i]==3) cout<<"Bella"<<endl;
				else if(ans[i]==6) cout<<"Blue"<<endl;
				else if(ans[i]==5) cout<<"Betsy"<<endl;
				else if(ans[i]==8) cout<<"Sue"<<endl;
				
				//cout<<ans[i]<<" ";
			}
			//cout<<endl;
			killer=true;
		}
		return;
	}
	for(int i=1;i<=8;i++){
		if(!book[i]){
			book[i]=true;
			ans[step+1]=i;
			f(step+1);
			book[i]=false;
		}
	}
}
string p;
int main(){
	freopen("lineup.in","r",stdin);
	freopen("lineup.out","w",stdout);
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>p;
		//cout<<p<<" ";
		int num1=0;
		int num2=0;
		if(p[2]=='s'&&p[3]=='s') num1=4;
		else if(p[2]=='t'&&p[3]=='t') num1=7;
		else if(p[2]=='l'&&p[3]=='i') num1=2;
		else if(p[2]=='a'&&p[3]=='t') num1=1;
		else if(p[2]=='l'&&p[3]=='l') num1=3;
		else if(p[2]=='u'&&p[3]=='e') num1=6;
		else if(p[2]=='t'&&p[3]=='s') num1=5;
		else num1=8;
		cin>>p;
		cin>>p;
		cin>>p;
		cin>>p;
		cin>>s[i];
		int len=s[i].size();
		//Bessie=1,Buttercup=2,Belinda=3,Beatrice=4,Bella=5,Blue=6,Betsy=7,Sue=8
		//Bessie=4,Buttercup=7,Belinda=2,Beatrice=1,Bella=3,Blue=6,Betsy=5,Sue=8
		if(s[i][len-1]=='e'&&s[i][len-2]=='i')num2=4;
		else if(s[i][len-1]=='p'&&s[i][len-2]=='u')num2=7;
		else if(s[i][len-1]=='a'&&s[i][len-2]=='d')num2=2;
		else if(s[i][len-1]=='e'&&s[i][len-2]=='c')num2=1;
		else if(s[i][len-1]=='a'&&s[i][len-2]=='l')num2=3;
		else if(s[i][len-1]=='e'&&s[i][len-2]=='u'&&s[i][len-3]=='l')num2=6;
		else if(s[i][len-1]=='y'&&s[i][len-2]=='s')num2=5;
		else if(s[i][len-1]=='e'&&s[i][len-2]=='u'&&s[i][len-3]=='S')num2=8;
		if(a[num1][0]==0) a[num1][0]=num2;
		else a[num1][1]=num2;
		if(a[num2][0]==0) a[num2][0]=num1;
		else a[num2][1]=num1;
	}
	//cout<<a[8][1]<<endl;
	for(int i=1;i<=8;i++){
		if(killer){
			return 0;
		}
		memset(book,0,sizeof(book));
		memset(ans,0,sizeof(ans));
		book[i]=true;
		ans[1]=i;
		f(1);
	}
	return 0;
}