USACO历年青铜组真题解析 | 2019年12月

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总贴：USACO历年青铜组真题解析 | 汇总-CSDN博客

P5831 Cow Gymnastics

【题目来源】

洛谷：[P5831 USACO19DEC] Cow Gymnastics B - 洛谷

【题目描述】

为了提高健康水平，奶牛们开始进行体操训练了！Farmer John 选定了他最喜爱的奶牛 Bessie 来执教其他N NN头奶牛，同时评估她们学习不同的体操技术的进度。

K KK次训练课的每一次，Bessie 都会根据N NN头奶牛的表现给她们进行排名。之后，她对这些排名的一致性产生了好奇。称一对不同的奶牛是一致的，如果其中一头奶牛在每次训练课中都表现得都比另一头要好。

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

【输入】

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

【输出】

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

【输入样例】

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

【输出样例】

4

【解题思路】

【算法标签】

《洛谷 P5831 Cow Gynmnastics》 #枚举# #USACO# #2019#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;intk,n,a[25][25]={0},t[25]={0},ans=0;intmain(){cin>>k>>n;// 输入k和nwhile(k--){// 依次读入k行数据for(inti=1;i<=n;i++){// 依次记录n个数据cin>>t[i];}for(inti=1;i<n;i++){// 定义二维矩阵，分别记录每2个数的先后关系for(intj=i+1;j<=n;j++){a[t[j]][t[i]]=1;// t[j]在t[i]后面，将表现不好的标记为1}}}for(inti=1;i<=n;i++){// 处理二维矩阵的斜线位置（左上到右下的斜线）for(intj=1;j<=n;j++){if(i==j)a[i][j]=1;// 这些也标记为1}}for(inti=1;i<=n;i++){// 遍历二维矩阵for(intj=1;j<=n;j++){if(a[i][j]==0)ans++;// 对于值为0的单元格，就是一对A优于B的存在。统计ans就是一致的奶牛的对数}}cout<<ans<<endl;return0;}

【运行结果】

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

P5832 Where Am I?

【题目来源】

洛谷：[P5832 USACO19DEC] Where Am I? B - 洛谷

【题目描述】

Farmer John 出门沿着马路散步，但是他现在发现可能迷路了！

沿路有一排共N NN个农场。不幸的是农场并没有编号，这使得 Farmer John 难以分辨他在这条路上所处的位置。然而，每个农场都沿路设有一个彩色的邮箱，所以 Farmer John 希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。

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

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

【输入】

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

【输出】

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

【输入样例】

7 ABCDABC

【输出样例】

4

【解题思路】

【算法标签】

《洛谷 P5832 Where Am I?》 #字符串# #USACO# #2019#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;intn;string s;intmain(){cin>>n>>s;// 输入n和字符串sfor(inti=1;i<=s.length();i++){// 遍历1-n的长度intmark=0;// 定义mark，用来指示是否查找到相同子串for(intj=0;j<s.length();j++){// 从0开始遍历字符串string s1=s.substr(j,i);// 截取字符串s1for(intk=j+1;k<s.length();k++){// 从j+1的位置遍历字符串string s2=s.substr(k,i);// 截取字符串s2if(s1==s2){// 如果两个字符串相等mark=1;// 修改mark为1，表示找到相同内容break;// 退出循环}}}if(mark==0){// 每轮都会检查mark是否为0，如果为0，则说明没有相等的字符串cout<<i<<endl;// 输入此时字符串长度return0;// 退出程序}}return0;}

【运行结果】

7 ABCDABC 4

P5833 Livestock Lineup

【题目来源】

洛谷：[P5833 USACO19DEC] Livestock Lineup B - 洛谷

【题目描述】

每天，Farmer John 都要给他的8 88头奶牛挤奶。她们的名字分别是 Bessie，Buttercup，Belinda，Beatrice，Bella，Blue，Betsy，和 Sue。

不幸的是，这些奶牛相当难以伺候，她们要求 Farmer John 以一种符合N NN条限制的顺序给她们挤奶。每条限制的形式为“X XX必须紧邻着Y YY挤奶”，要求奶牛X XX在挤奶顺序中必须紧接在奶牛Y YY之后，或者紧接在奶牛Y YY之前。

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

【输入】

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

【输出】

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

【输入样例】

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

【解题思路】

【算法标签】

《洛谷 P5833 Livestock Lineup》 #字符串# #USACO# #2019#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;intn;string a[9]={"","Bessie","Buttercup","Belinda","Beatrice","Bella","Blue","Betsy","Sue"};string b[10];intbook[10]={0};structnode{string x,y;}p[10];voiddfs(intstep)// 排列模板{if(step==8+1){// 排列退出条件intmark=0;// 定义标记位for(inti=1;i<=n;i++){// 遍历输入的n对相邻奶牛组合intpos1,pos2;// 查找两头奶牛的位置for(intj=1;j<=8;j++){// 找到后赋值给pos1和pos2if(b[j]==p[i].x)pos1=j;if(b[j]==p[i].y)pos2=j;}if(abs(pos1-pos2)!=1){// 如果位置之差的绝对值不为1，说明不相邻mark=1;// 修改markbreak;// 退出循环，之后走到return}}if(mark==0){// 如果两层循环下来确定n对奶牛都是相邻的，那说明符合条件for(inti=1;i<=8;i++){// 输出8头奶牛cout<<b[i]<<endl;// 注意换行输出}exit(0);// 退出程序}return;}for(inti=1;i<=8;i++){// 排列模板if(book[i]==0){b[step]=a[i];// 这里这里b[step]要赋值为选择的奶牛名称book[i]=1;dfs(step+1);b[step]="";// 还原现场book[i]=0;}}}intmain(){cin>>n;// 输入nstring tmp;// 定义临时字符串，接受输入多个字符串中的无效信息for(inti=1;i<=n;i++){// 遍历n次输入cin>>p[i].x>>tmp>>tmp>>tmp>>tmp>>p[i].y;// 记录相邻的奶牛组合}sort(a+1,a+8+1);// 对于8个头奶牛的名字按照字典序排序（这样排列出来的，就一定是按照字典序最小的排前面）dfs(1);// 排列模板return0;}

【运行结果】

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