欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总贴：USACO历年青铜组真题解析 | 汇总-CSDN博客
P10131 Majority Opinion
【题目来源】
洛谷：[P10131 USACO24JAN] Majority Opinion B - 洛谷
【题目描述】
Farmer John 有一项重要的任务——弄清楚要为他的奶牛们购买什么类型的干草。
Farmer John 的 \(N\) 头奶牛（\(2\le N\le 10^5\)）编号为 \(1\) 到 \(N\)，每头奶牛喜欢恰好一种类型的干草 \(h_i\)（\(1\le h_i\le N\)）。他希望他的所有奶牛都喜欢同一种干草。
为了实现这一目标，Farmer John 可以主持焦点小组访谈。一次焦点小组访谈为让编号从 \(i\) 到 \(j\) 的连续范围内的所有奶牛聚集在一起参加一次访谈。如果有一种干草是小组中超过一半的奶牛喜欢的，则此次焦点小组访谈结束后，所有奶牛最终都会喜欢这种干草。如果不存在这种类型的干草，那么奶牛们不会改变她们喜欢的干草类型。例如，在由 \(16\) 头奶牛组成的焦点小组访谈中，需要有其中 \(9\) 头或更多的奶牛具有相同的干草喜好，才能使其余奶牛改变其喜好以与之一致。
Farmer John 想知道哪些类型的干草有可能变为同时受到所有奶牛的喜爱。他一次只能主持一个焦点小组访谈，但为了使所有奶牛都喜欢同一类型的干草，他可以根据需要任意多次地主持焦点小组访谈。
【输入】
输入的第一行包含一个整数 \(T\)，为独立的测试用例的数量（\(1\le T\le 10\)）。
每一个测试用例的第一行包含 \(N\)。
第二行包含 \(N\) 个整数，为奶牛们喜爱的干草类型 \(h_i\)。
输入保证所有测试用例的 \(N\) 之和不超过 \(2\cdot 10^5\)。
【输出】
输出 \(T\) 行，对于每个测试用例输出一行。
如果可能使所有奶牛同时喜欢同一种干草，则以升序输出所有可能的此类干草的类型，否则输出 \(-1\)。在同一行内输出一列整数时，相邻的数用空格分隔，并确保行末没有多余空格。
【输入样例】
5
5
1 2 2 2 3
6
1 2 3 1 2 3
6
1 1 1 2 2 2
3
3 2 3
2
2 1
【输出样例】
2
-1
1 2
3
-1
【算法标签】
《洛谷 P10131 Majority Opinion》 #数学# #USACO# #O2优化# #2024#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int T; // 测试用例的数量
int n; // 每个测试用例的数字个数
int a[100005]; // 存储输入的数字序列
int b[100005]; // 标记数组，记录哪些数字满足条件int main()
{// 输入测试用例数量cin >> T;// 处理每个测试用例for (int t = 1; t <= T; t++){// 清空数组，重置为0memset(a, 0, sizeof(a));memset(b, 0, sizeof(b));// 输入数字个数cin >> n;// 输入数字序列for (int i = 1; i <= n; i++){cin >> a[i];}// 特殊情况处理：当n=2时if (n == 2 && a[1] != a[2]){// 只有两个数字且不相等，无解cout << "-1" << endl;continue; // 跳过后续处理}else if (n == 2 && a[1] == a[2]){// 只有两个数字且相等，直接输出该数字cout << a[1] << endl;continue; // 跳过后续处理}// 遍历序列，检查满足条件的数字for (int i = 1; i < n - 1; i++){// 检查连续三个数字的相等关系// 情况1：相邻两个数字相等if (a[i] == a[i + 1]){b[a[i]] = 1; // 标记该数字满足条件}// 情况2：间隔一个数字相等（i和i+2）if (a[i] == a[i + 2]){b[a[i]] = 1; // 标记该数字满足条件}// 情况3：后两个数字相等（i+1和i+2）if (a[i + 1] == a[i + 2]){b[a[i + 1]] = 1; // 标记该数字满足条件}}int flag = 0; // 标记是否找到满足条件的数字string s = ""; // 用于构建输出字符串// 遍历所有可能的数字（1到100000）for (int i = 1; i <= 100000; i++){// 如果当前数字被标记为满足条件if (b[i] != 0){// 将数字添加到输出字符串s += to_string(i);s += " ";flag = 1; // 设置找到标志}}// 移除最后一个空格s = s.substr(0, s.length() - 1);// 根据是否找到结果输出if (flag){cout << s << endl; // 输出所有满足条件的数字}else{cout << "-1" << endl; // 无解情况}}return 0;
}
【运行结果】
5
5
1 2 2 2 3
2
6
1 2 3 1 2 3
-1
6
1 1 1 2 2 2
1 2
3
3 2 3
3
2
2 1
-1
P10132 Cannonball
【题目来源】
洛谷：[P10132 USACO24JAN] Cannonball B - 洛谷
【题目描述】
Bessie 已经精通了变成炮弹并沿着长度为 \(N\)（\(1\le N\le 10^5\)）的数轴弹跳的艺术，数轴上的位置从左到右编号为 \(1,2,\cdots,N\)。她从某个整数位置 \(S\)（\(1\le S\le N\)）开始，以 \(1\) 的起始能量向右弹跳。 如果 Bessie 的能量为 \(k\)，则她将弹跳至距当前位置向前距离 \(k\) 处进行下一次弹跳。
从 \(1\) 到 \(N\) 的每个整数位置上均有炮击目标或跳板。每个炮击目标和跳板都有一个在 \(0\) 到 \(N\) 范围内的整数值。一个数值为 \(v\) 的跳板会使 Bessie 的能量增加 \(v\) 并反转她的方向。一个数值为 \(v\) 的炮击目标会当着陆时能量不小于 \(v\) 时被击破。着陆在炮击目标上不会改变 Bessie 的能量和方向。被击破的炮击目标将保持击破状态，Bessie 依然可以该炮击目标上弹跳，同样不会改变能量和方向。
如果 Bessie 弹跳无限长的时间或直到她离开数轴，她会击破多少个炮击目标？
如果 Bessie 开始时位于一个她可以击破的炮击目标，她会立刻这样做。类似地，如果 Bessie 开始时位于一个跳板，跳板的效果将在她第一次跳跃之前生效。
【输入】
输入的第一行包含 \(N\) 和 \(S\)，其中 \(N\) 为数轴的长度，\(S\) 为 Bessie 的起始位置。
以下 \(N\) 行描述了每一个位置。其中第 \(i\) 行包含整数 \(q_i\) 和 \(v_i\)，如果位置 \(i\) 上有一个跳板则 \(q_i=0\)，位置 \(i\) 上有一个炮击目标则 \(q_i=1\)，\(v_i\) 是位置 \(i\) 上的跳板或炮击目标的数值。
【输出】
输出一个整数，为将被击破的炮击目标数量。
【输入样例】
5 2
0 1
1 1
1 2
0 1
1 1
【输出样例】
1
【算法标签】
《洛谷 P10132 Cannonball》 #模拟# #USACO# #2024#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int n; // 房间数量
int s; // 起始房间编号
int cnt; // 已击败的敌人数量
int tot; // 敌人总数
int step; // 移动步数（用于调试或限制循环次数）// 房间结构体
struct node
{int type; // 房间类型：0=弹簧，1=敌人int weight; // 房间数值：弹簧的弹力值/敌人的生命值int vis; // 标记弹簧是否被访问过int lastpower; // 上次访问弹簧时的力量值
} p[100005];// 人物结构体
struct Person
{int dir; // 移动方向：1=向右，-1=向左int power; // 当前力量值int pos; // 当前位置（房间编号）
};int main()
{// 输入房间数量和起始位置cin >> n >> s;// 输入每个房间的信息for (int i = 1; i <= n; i++){cin >> p[i].type >> p[i].weight;if (p[i].type == 1){tot++; // 统计敌人总数}}// 初始化贝西的状态Person bessie = {1, 1, s}; // 初始方向向右，力量为1，位置为sint flag = 0; // 标志变量（未使用）// 主循环：贝西在房间之间移动while (bessie.pos >= 1 && bessie.pos <= n){// 调试用的步数限制（注释掉的代码）// if (step > n - 1) break;// 如果已击败所有敌人，退出循环if (tot == cnt){// flag = 1;break;}// 调试输出（注释掉的代码）// cout << "pos " << bessie.pos << endl;// cout << "power " << bessie.power << endl;// 处理敌人房间（type=1）if (p[bessie.pos].type == 1){// 调试输出（注释掉的代码）// cout << "1 power " << bessie.power << endl;// 如果力量足够击败敌人if (bessie.power >= p[bessie.pos].weight){cnt++; // 击败敌人计数加1p[bessie.pos].weight = 1e9; // 将敌人生命值设为极大值（标记为已击败）}}// 处理弹簧房间（type=0）if (p[bessie.pos].type == 0){// 调试输出（注释掉的代码）// cout << "0 power " << bessie.power << endl;// 检测循环：如果弹簧已被访问过且力量值相同，说明进入死循环if (p[bessie.pos].vis == 1 && bessie.power == p[bessie.pos].lastpower){break; // 退出循环避免无限循环}// 改变移动方向bessie.dir = bessie.dir * -1;// 标记弹簧已被访问，记录当前力量值p[bessie.pos].vis = 1;p[bessie.pos].lastpower = bessie.power;// 增加力量值（弹簧效果）bessie.power = bessie.power + p[bessie.pos].weight;}// 移动到下一个位置bessie.pos = bessie.pos + (bessie.dir * bessie.power);step++; // 步数计数（用于调试或循环控制）}// 输出击败的敌人数量cout << cnt << endl;return 0;
}
【运行结果】
5 2
0 1
1 1
1 2
0 1
1 1
P10133 Balancing Bacteria
【题目来源】
洛谷：[P10133 USACO24JAN] Balancing Bacteria B - 洛谷
【题目描述】
Farmer John 有 \(N\)（\(1\le N\le 2\cdot 10^5\)）块草地排成一行，其中草地 \(i\) 的细菌水平与健康草的细菌水平相差 \(a_i\)（\(−10^{15}\le a_i\le 10^{15}\)）。例如，如果 \(a_i=−3\)，则草地 \(i\) 的细菌水平比正常水平低 \(3\)，需要额外添加恰好 \(3\) 个单位的细菌才能将其提高到被认为是健康的程度。
Farmer John 想要确保每一块草地都被修复至健康的细菌水平。方便的是，他有两种品牌的农药可以喷洒在他的田地里，一种可以添加细菌，另一种可以去除细菌。当 Farmer John 喷洒任一类型的农药时，他站在草地 \(N\)（最右边的草地）并为他的喷雾器选择功率等级 \(L\)（\(1\le L\le N\)）。
喷雾器对靠近 Farmer John 的草地效果最大，随着距离增加效果逐渐减弱。如果 Farmer John 选择添加细菌的农药，则 \(L\) 单位的细菌将被添加至草地 \(N\)，\(L−1\) 单位添加至草地 \(N−1\)，\(L−2\) 单位添加至草地 \(N−2\)，以此类推。草地 \(1\ldots N−L\) 不会得到任何细菌，因为喷雾器设置的功率不足以到达它们。类似地，如果 Farmer John 选择去除细菌的农药，则 \(L\) 单位的细菌将被从草地 \(N\) 去除，\(L−1\) 单位被从草地 \(N−1\) 去除，以此类推。同样，草地 \(1\ldots N−L\) 将不受影响。
求 Farmer John 使用喷雾器的最少次数，使得每块草地都具有健康草的推荐细菌值。输入保证答案不超过 \(10^9\)。
注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，C/C++ 中的 "long long"）。
【输入】
输入的第一行包含 \(N\)。
第二行包含 \(N\) 个整数 \(a_1\ldots a_N\)，为每块草地的初始细菌水平。
【输出】
输出一个整数，为使每块草地都具有健康草的推荐的细菌值所需使用喷雾器的最少次数。
【输入样例】
2
-1 3
【输出样例】
6
【算法标签】
《洛谷 P10133 Balancing Bacteria》 #USACO# #2024#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int n;
long long a[200005], b[200005], c[200005], ans, delta;
long long b_gc, b_st, c_gc, c_st;int main()
{cin >> n;int cnt = 0;// 读取数组a并统计0的个数for (int i = 1; i <= n; i++){cin >> a[i];if (a[i] == 0){cnt++;}}// 如果数组全为0，直接输出0if (cnt == n){cout << 0 << endl;return 0;}// 找到第一个非0元素的位置int mark = 1;for (int i = 1; i <= n; i++){if (a[i] == 0){continue;}else{mark = i;break;}}// 根据第一个非0元素的正负性分别处理if (a[mark] < 0){// 处理负数序列for (int i = mark; i <= n; i++){// 计算b和c数组的当前值（基于增量）b[i] = b[i - 1] + b_gc;c[i] = c[i - 1] + c_gc;// 计算目标值与当前值的差值// 目标：形成递减等差数列 a[i] = a[i-1] - 1delta = (a[i - 1] - 1) - (a[i] + b[i] + c[i]);// 根据差值调整增量if (delta > 0){b_gc = b_gc + delta; // 正偏差，增加b的增量}else if (delta < 0){c_gc = c_gc + delta; // 负偏差，减少c的增量}// 更新b和c的累积值b_st = b_st + b_gc;b[i] = b_st;c_st = c_st + c_gc;c[i] = c_st;// 更新a[i]为期望的等差数列值a[i] = a[i - 1] - 1;// 累加调整代价ans += abs(delta);}// 检查最后一个元素是否符合等差数列if (a[n] != a[n - 1] - 1){ans += abs(a[n - 1] - 1 - a[n]);}}else if (a[mark] > 0){// 处理正数序列（逻辑与负数情况对称）for (int i = mark; i <= n; i++){b[i] = b[i - 1] + b_gc;c[i] = c[i - 1] + c_gc;// 目标：形成递增等差数列 a[i] = a[i-1] + 1delta = (a[i - 1] + 1) - (a[i] + b[i] + c[i]);if (delta > 0){b_gc = b_gc + delta;}else if (delta < 0){c_gc = c_gc + delta;}b_st = b_st + b_gc;b[i] = b_st;c_st = c_st + c_gc;c[i] = c_st;a[i] = a[i - 1] + 1;ans += abs(delta);}// 检查最后一个元素if (a[n] != a[n - 1] + 1){ans += abs(a[n - 1] + 1 - a[n]);}}// 输出总调整代价+1cout << ans + 1 << endl;return 0;
}
【运行结果】
2
-1 3
6