USACO历年青铜组真题解析 | 2021年1月-编程实验室

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

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

适合人群：

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

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

P9940 Uddered but not Herd

【题目来源】

洛谷：[P9940 USACO21JAN] Uddered but not Herd B - 洛谷

【题目描述】

一个鲜为人知的事实是，奶牛拥有自己的文字：「牛文」。牛文由26 2626个字母a到z组成，但是当奶牛说牛文时，可能与我们所熟悉的abcdefghijklmnopqrstuvwxyz不同，她会按某种特定的顺序排列字母。

为了打发时间，奶牛 Bessie 在反复哼唱牛文字母歌，而 Farmer John 好奇她唱了多少遍。

给定一个小写字母组成的字符串，为 Farmer John 听到 Bessie 唱的字母，计算 Bessie 至少唱了几遍完整的牛文字母歌，使得 Farmer John 能够听到给定的字符串。Farmer John 并不始终注意 Bessie 所唱的内容，所以他可能会漏听 Bessie 唱过的一些字母。给定的字符串仅包含他记得他所听到的字母。

【输入】

输入的第一行包含26 2626个小写字母a到z的牛文字母表顺序。下一行包含一个小写字母组成的字符串，为 Farmer John 听到 Bessie 唱的字母。字符串的长度不小于1 11且不大于1000 10001000。

【输出】

输出 Bessie 所唱的完整的牛文字母歌的最小次数。

【输入样例】

abcdefghijklmnopqrstuvwxyz mood

【输出样例】

【算法标签】

《洛谷 P9940 Uddered but not Herd》 #模拟# #USACO# #O2优化# #2021#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;string s1,s2;intans=1;intmain(){cin>>s1>>s2;// 输入字符串s1和s2for(inti=1;i<s2.length();i++){// 遍历s2字符串if(s1.find(s2[i])<=s1.find(s2[i-1]))ans++;// 查找s2[i]与s2[i-1]在s1中的先后位置，如果小于等于，则说明一遍中无法唱到，需要再唱一遍}cout<<ans<<endl;// 最后打印结果return0;}

【运行结果】

abcdefghijklmnopqrstuvwxyz mood 3

P9941 Even More Odd Photos

【题目来源】

洛谷：[P9941 USACO21JAN] Even More Odd Photos B - 洛谷

【题目描述】

Farmer John 正再一次尝试给他的N NN头奶牛拍照**( 2 ≤ N ≤ 1000 ) (2\le N\le 1000)(2≤N≤1000)**。

每头奶牛有一个范围在 **$1\dots 100 $**之内的整数的「品种编号」。Farmer John 对他的照片有一个十分古怪的构思：他希望将所有的奶牛分为不相交的若干组（换句话说，将每头奶牛分到恰好一组中）并将这些组排成一行，使得第一组的奶牛的品种编号之和为偶数，第二组的编号之和为奇数，以此类推，奇偶交替。

Farmer John 可以分成的最大组数是多少？

【输入】

输入的第一行包含N NN。下一行包含N NN个空格分隔的整数，为N NN头奶牛的品种编号。

【输出】

输出 Farmer John 的照片中的最大组数。可以证明，至少存在一种符合要求的分组方案。

【输入样例】

7 1 3 5 7 9 11 13

【输出样例】

【算法标签】

《洛谷 P9941 Even More Odd Photos》 #数学# #贪心# #USACO# #O2优化# #2021#

【代码详解】

#include<iostream>usingnamespacestd;intn,odd,even;intmain(){cin>>n;// 输入nfor(inti=1;i<=n;i++){// 遍历n个数intx;cin>>x;// 输入数xif(x%2==1)odd++;// 判断奇偶性，并统计奇数和偶数的个数elseeven++;}while(even<odd){// 当奇数个数大于偶数个数时odd-=2;// 将奇数变为偶数，变一次奇数个数需要减2even++;// 偶数个数自增1}if(even>odd+1){// 如果偶数大于奇数+1even=odd+1;// 则偶数等于奇数+1，如8个偶、1个奇，最后会变成2个偶、1个奇(1个偶数和1个奇数组成1个奇数，奇数个数没有变化，偶数在递减，直至奇数个数+1）}cout<<odd+even<<endl;// 最后输出奇数和偶数个数之和return0;}

【运行结果】

7 1 3 5 7 9 11 13 3

P9942 Just Stalling

【题目来源】

洛谷：[P9942 USACO21JAN] Just Stalling B - 洛谷

【题目描述】

Farmer John 有N NN头奶牛**( 1 ≤ N ≤ 20 ) (1\le N\le 20)(1≤N≤20)，高度为a 1 … a N a_1\dots a_Na1…aN。他的牛栏有N NN个牛棚，高度限制分别为b 1 … b N b_1\dots b_Nb1…bN（例如，如果b 5 = 17 b_5=17b5=17**，那么一头高度不超过17 1717的奶牛可以住在牛棚5 55里）。Farmer John 有多少种不同的方式安排他的奶牛，使得每头奶牛均住在不同的牛棚里，并且使得每个牛棚的高度限制均得到满足？

【输入】

输入的第一行包含N NN。第二行包含N NN个空格分隔的整数a 1 , a 2 , … , a N a_1,a_2,\dots,a_Na1,a2,…,aN。第三行包含N NN个空格分隔的整数b 1 , b 2 , … , b N b_1,b_2,\dots,b_Nb1,b2,…,bN。所有的高度和高度限制均在范围[ 1 , 10 9 ] [1,10^9][1,109]内。

【输出】

输出 Farmer John 可以将每头奶牛安排到不同的牛棚里，使得每个牛棚的高度限制均得到满足的方法数。注意输出的数量可能需要使用64 6464位整数型，例如 C++ 中的 long long。

【输入样例】

4 1 2 3 4 2 4 3 4

【输出样例】

【算法标签】

《洛谷 P9942 Just Stalling》 #USACO# #O2优化# #2021#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;intn,a[25],b[25];boolcmp(intx,inty)// 定义比较函数，按照从大到小排序{returnx>y;}intmain(){cin>>n;// 输入nfor(inti=1;i<=n;i++)cin>>a[i];// 记录奶牛的高度for(inti=1;i<=n;i++)cin>>b[i];// 记录牛棚的高度sort(a+1,a+n+1,cmp);// 按照牛棚的高度，从大到小排序longlongans=1;// 定义连乘的初始值为1for(inti=1;i<=n;i++){// for循环遍历n头奶牛intc=0;// 计算每头牛可分配的牛棚数量for(intj=1;j<=n;j++){// 遍历所有牛棚if(b[j]>=a[i])c++;// 如果牛棚高度大于等于牛的高度，牛棚数量自增1}c-=(i-1);// 因为前i-1头牛已经分配了牛棚，所以c要减去(i-1)ans*=c;// 将可用牛棚数量乘以ans，类似于C(1,2)*C(1,2)*C(1,2)*1}cout<<ans<<endl;// 最后输出方案数return0;}