欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总贴：USACO历年青铜组真题解析 | 汇总-CSDN博客
P8183 Sleeping in Class
【题目来源】
洛谷：[P8183 USACO22FEB] Sleeping in Class B - 洛谷
【题目描述】
奶牛 Bessie 最近很高兴能够重返线下课堂！不幸的是，她的老师 Farmer John 讲课非常无聊，因此她经常在课堂上睡着。
Farmer John 注意到 Bessie 在课堂上没有专心听讲。他让班上的另一位学生 Elsie 记录 Bessie 在每节课上睡着的次数。总共有 \(N\) 节课（\(1 \leq N \leq 10^5\)），Elsie 记录到 Bessie 在第 \(i\) 节课上睡着了 \(a_i\) 次（\(0 \leq a_i \leq 10^6\)）。所有课程中 Bessie 睡着的总次数不超过 \(10^6\)。
Elsie 对 Bessie 感到非常竞争，她希望让 Farmer John 觉得 Bessie 在每节课上睡着的次数是一致的——让问题看起来完全是 Bessie 的错，而与 Farmer John 有时无聊的讲课无关。Elsie 修改记录的唯一方式是将两节相邻的课合并。例如，如果 \(a = [1,2,3,4,5]\)，那么如果 Elsie 合并第二和第三节课，记录将变为 \([1,5,4,5]\)。
请帮助 Elsie 计算她需要对记录进行的最少修改次数，以使记录中的所有数字相等。
【输入】
每个输入包含 \(T\)（\(1 \leq T \leq 10\)）个需要独立解决的测试用例。
第一行包含 \(T\)，表示测试用例的数量。接下来的 \(T\) 组测试用例，每组由两行描述。每组的第一行包含 \(N\)，第二行包含 \(a_1, a_2, \ldots, a_N\)。
保证每个测试用例中，\(a\) 的所有值之和不超过 \(10^6\)。同时，所有测试用例的 \(N\) 之和不超过 \(10^5\)。
【输出】
请输出 \(T\) 行，每行表示 Elsie 为使记录中的所有数字相等所需的最少修改次数。
【输入样例】
3
6
1 2 3 1 1 1
3
2 2 3
5
0 0 0 0 0
【输出样例】
3
2
0
【解题思路】
【算法标签】
《洛谷 P8183 Sleeping in Class》 #USACO# #2022#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
int t, n, avg;
int a[100005];int main()
{cin >> t; // 输入twhile (t--) { // 遍历t组数据cin >> n; // 输入nlong long sum = 0; // 定义sum，因为a最大为10^6，所以设定sum为longloong（定义为int也可以AC）for (int i=1; i<=n; i++) { // 遍历n个数cin >> a[i]; // 记录每个数sum += a[i]; // 并计算所有数之和}if (sum==0) { // 特判和为0cout << 0 << endl; // 则直接输出0continue; // 继续下组数据}int maxn = 0; // 定义最大合并堆数for (int i=n; i>=1; i--) { // 从n堆开始遍历至1堆if (sum%i==0) { // 如果可以平均分int tot = 0; // 定义多个数之和，初始为0int cnt = 0; // 定义堆数计数器，初始为0for (int j=1; j<=n; j++) { // 从第一个数开始遍历tot += a[j]; // 计算数之和if (tot>sum/i) { // 如果相加之和大于平均数cnt = 0; // 重置堆数，并从下个堆数i开始计算break;} else if (tot==sum/i) { // 如果相加之和等于平均数cnt++; // 堆数加1tot = 0; // 并重置数之和，便于计算后面的数}}maxn = max(maxn, cnt); // 计算最大的堆数}}cout << n - maxn << endl; // n减最大的堆数，就是最少的合并次数}return 0;
}
【运行结果】
3
6
1 2 3 1 1 1
3
3
2 2 3
2
5
0 0 0 0 0
0
P8184 Photoshoot 2
【题目来源】
洛谷：[P8184 USACO22FEB] Photoshoot 2 B - 洛谷
【题目描述】
在一个熟悉的情景中，Farmer John 正在为他的 \(N\) 头奶牛（\(1 \leq N \leq 10^5\)，编号为 \(1 \cdots N\)）排队拍照。
初始时，奶牛从左到右的排列顺序为 \(a_1, a_2, \cdots , a_N\)。Farmer John 的目标是将奶牛从左到右排列成 \(b_1, \cdots , b_N\) 的顺序。为了实现这一目标，他可以对排列顺序进行一系列修改。每次修改包括选择一头奶牛并将其向左移动若干位置。
请计算 Farmer John 将奶牛排列成目标顺序所需的最少修改次数。
【输入】
输入的第一行包含 \(N\)。第二行包含 \(a_1, a_2, \cdots , a_N\)。第三行包含 \(b_1, \cdots , b_N\)。
【输出】
输出将奶牛排列成目标顺序所需的最少修改次数。
【输入样例】
5
5 1 3 2 4
4 5 2 1 3
【输出样例】
2
【解题思路】
【算法标签】
《洛谷 P8184 Photoshoot 2》 #USACO# #2022#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
int n, ans=0;
int a[100005], b[100005];
int main()
{cin >> n; // 输入nfor (int i=1; i<=n; i++) { // for循环遍历n个数cin >> a[i]; // 记录n个数}for (int i=1; i<=n; i++) { // for循环遍历n个数int tmp; cin >> tmp; // 记录n个数的下标b[tmp] = i;}int pre = b[a[1]]; // 定义起始位置为a数组中第1个数的位置for (int i=2; i<=n; i++) { // 依次遍历后续n-1个数if (b[a[i]]> pre) { // 如果当前这个数的位置比前一个数大pre = b[a[i]]; // 说明相对位置没有变化，更新下一次要比较的位置} else { // 否则说明相对位置发生了改变ans++; // 需要挪一次}}cout << ans << endl; // 返回挪的次数return 0;
}
【运行结果】
5
5 1 3 2 4
4 5 2 1 3
2
P8185 Blocks
【题目来源】
洛谷：[P8185 USACO22FEB] Blocks B - 洛谷
【题目描述】
为了提高词汇量，母牛贝西得到了一套四块木块，其中每块都是一个立方体，六面各写着一个字母。她正在通过将木块排成一排使得木块顶部的字母拼出单词来学习拼写。
给定 Bessie 的四个木块上的字母，以及她想拼写的单词列表，请确定列表中哪些单词可被她使用木块成功拼写。
【输入】
输入的第一行包含 \(N(1\le N\le 10)\)，为 Bessie 想要拼写的单词数。接下来的四行每行包含一个带有六个大写字母的字符串，表示 Bessie 的一个块的六个侧面上的字母。接下来的 \(N\) 行包含 Bessie 想要拼写的\(N\)个单词。其中每一个的长度在 \(1\) 到 \(4\)个大写字母之间。
【输出】
对于 Bessie 列表中的每个单词，如果她能够使用木块拼写，则输出 YES，否则输出 NO。
【输入样例】
6
MOOOOO
OOOOOO
ABCDEF
UVWXYZ
COW
MOO
ZOO
MOVE
CODE
FARM
【输出样例】
YES
NO
YES
YES
NO
NO
【解题思路】
【算法标签】
《洛谷 P8185 Blocks》 #USACO# #2022#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
int n, len;
string s[5], t;
bool f[5][30], flag, use[5]; // 定义use数组标记某行是否已经使用过
void dfs(int d) // 定义dfs搜索
{if (d==len) { // dfs退出条件，如果t字符串的每个字符都可以找到，此时d=lenflag = true; // 则返回truereturn; // 退出搜索}for (int i=1; i<=4; i++) { // 依次遍历4行数据if (!use[i] && f[i][t[d]-'A']) { // 如果该行没有使用过，且存在XX字符// cout << "f[i][t[d]] " << i << " " << t[d]-'A' << endl;use[i] = true; // 则标记该行为truedfs(d+1); // 搜索下一个字符use[i] = false; // 还原现场}}
}
int main()
{cin >> n; // 输入nfor (int i=1; i<=4; i++) { // 依次遍历4行cin >> s[i]; // 以字符串形式记录每行的字符for (int j=0; j<=s[i].length(); j++) { // 对每行的字符进行住逐位存储f[i][s[i][j]-'A'] = true; // 记录XX行是否存在XX字符}}while (n--) { // 依次遍历n个循环cin >> t; // 输入字符串tlen = t.length(); // 获取t的长度，用于dfs的结束判断memset(use, false, sizeof(use)); // 每次dfs前初始化use数组flag = false; // 初始化是否找到的标志位flag，初始为falsedfs(0); // 进行dfs搜索，传入参数为t字符串的位置，起始为0if (flag==true) cout << "YES" << endl; // 如果找到输出YESelse cout << "NO" << endl; // 否则输出NO}return 0;
}
【运行结果】
6
MOOOOO
OOOOOO
ABCDEF
UVWXYZ
COW
YES
MOO
NO
ZOO
YES
MOVE
YES
CODE
NO
FARM
NO