欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总贴：USACO历年青铜组真题解析 | 汇总-CSDN博客
P1696 Blocked Billboard II
【题目来源】
洛谷：[P1696 USACO18JAN] Blocked Billboard II B - 洛谷 (luogu.com.cn)
【题目描述】
奶牛 Bessie 曾经在她的谷仓里拥有如此美好的视野，可以看到马路对面两块广告牌，广告牌上宣传着看起来美味的牛饲料。不幸的是，其中一个广告牌最近更新了，现在宣传的是「农夫 Larry 的割草机」。Bessie 对割草机并不感兴趣，因为据她所知，割草机的唯一用途就是割掉她田里那些她觉得美味的草（如果你还没有注意到，Bessie 的思维过程大多围绕着食物）。
幸运的是，剩下的牛饲料广告牌位于割草机广告牌的前面，可能会遮挡它。
Bessie 决心要完全从她的视野中移除这个令人讨厌的割草机广告牌，于是她想出了一个冒险的计划。她计划从谷仓里偷一块大矩形防水布，然后在深夜偷偷溜出去，盖住割草机广告牌的剩余部分，这样她就再也看不到它的任何部分了。
给定两个广告牌的位置，请帮助 Bessie 计算她需要的最小防水布面积。由于谷仓里只有矩形大小的防水布，Bessie 观察到她可能需要一块面积稍大于割草机广告牌暴露面积的防水布，如下例所示。防水布只能放置在其边与其他广告牌的边平行的位置（即不能「倾斜」）。
【输入】
输入的第一行包含四个用空格分隔的整数：\(x_1, y_1, x_2, y_2\)，其中 \((x_1, y_1)\) 和 \((x_2, y_2)\) 是 Bessie 的二维视野中割草机广告牌的左下角和右上角的坐标。下一行包含四个整数，同样指定牛饲料广告牌的左下角和右上角的坐标。牛饲料广告牌可能遮挡割草机广告牌的全部、部分或没有。所有坐标的范围是 \(-1000\) 到 \(+1000\)。
【输出】
请输出 Bessie 需要使用的防水布的最小面积，以覆盖割草机广告牌的部分，使其完全被遮挡。
【输入样例】
2 1 7 4
5 -1 10 3
【输出样例】
15
【解题思路】
【算法标签】
《洛谷 P1696 Blocked Billboard II》 #USACO# #O2优化# #2018#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int a[5], b[5]; // 存储两个矩形的坐标：a[广告牌], b[覆盖物]
int ans = 0, ans2 = 0; // ans: 未被覆盖的面积, ans2: 被覆盖的面积int x[5], y[5]; // 存储所有x坐标和y坐标（用于网格划分）// 矩形的四个顶点坐标
int x11, x12, x21, x22; // 广告牌和覆盖物的x坐标
int y11, y12, y21, y22; // 广告牌和覆盖物的y坐标ifstream filein("billboard.in");
ofstream fileout("billboard.out");/*** 判断网格单元是否在矩形内部* @param i x方向网格索引* @param j y方向网格索引* @param k 矩形的坐标数组* @return 如果网格单元完全在矩形内返回true，否则false*/
bool in(int i, int j, int k[])
{// 检查网格单元是否完全包含在矩形内if (x[i] >= k[1] && x[i + 1] <= k[3] && y[j] >= k[2] && y[j + 1] <= k[4]){return true;}return false;
}int main()
{// 输入广告牌的坐标（左下角和右上角）for (int i = 1; i <= 4; i++){filein >> a[i];}x11 = a[1]; // 广告牌左下角xx12 = a[3]; // 广告牌右上角xy11 = a[2]; // 广告牌左下角yy12 = a[4]; // 广告牌右上角y// 输入覆盖物的坐标（左下角和右上角）for (int i = 1; i <= 4; i++){filein >> b[i];}x21 = b[1]; // 覆盖物左下角xx22 = b[3]; // 覆盖物右上角xy21 = b[2]; // 覆盖物左下角yy22 = b[4]; // 覆盖物右上角y// 收集所有x坐标和y坐标x[1] = a[1]; // 广告牌左边界x[2] = a[3]; // 广告牌右边界x[3] = b[1]; // 覆盖物左边界x[4] = b[3]; // 覆盖物右边界y[1] = a[2]; // 广告牌下边界y[2] = a[4]; // 广告牌上边界y[3] = b[2]; // 覆盖物下边界y[4] = b[4]; // 覆盖物上边界// 对坐标进行排序，用于网格划分sort(x + 1, x + 4 + 1);sort(y + 1, y + 4 + 1);// 特殊情况处理：覆盖物完全包含广告牌或广告牌完全包含覆盖物if ((y22 >= y12 && y11 >= y21 && x12 >= x22 && x21 >= x11) || (y12 >= y22 && y21 >= y11 && x22 >= x12 && x11 >= x21)){// 输出广告牌的面积（完全被覆盖或完全覆盖）fileout << (y12 - y11) * (x12 - x11) << endl;return 0;}// 遍历所有网格单元（3x3网格）for (int i = 1; i <= 3; i++){for (int j = 1; j <= 3; j++){// 检查网格单元是否在广告牌内但不在覆盖物内if (in(i, j, a) && !in(i, j, b)){// 计算未被覆盖的网格单元面积并累加ans += (y[j + 1] - y[j]) * (x[i + 1] - x[i]);}// 检查网格单元是否同时在广告牌和覆盖物内if (in(i, j, a) && in(i, j, b)){// 计算被覆盖的网格单元面积并累加ans2 += (y[j + 1] - y[j]) * (x[i + 1] - x[i]);}}}// 特殊情况：部分覆盖且覆盖区域不规则if (ans2 % (y12 - y11) != 0 && ans2 % (x12 - x11) != 0){// 使用整个广告牌的面积作为结果ans = (y12 - y11) * (x12 - x11);}// 输出未被覆盖的面积fileout << ans << endl;return 0;
}
【运行结果】
2 1 7 4
5 -1 10 3
15
P1697 Lifeguards
【题目来源】
洛谷：[P1697 USACO18JAN] Lifeguards B - 洛谷
【题目描述】
Farmer John 为他的奶牛们开设了一个游泳池，认为这将帮助它们放松并产更多的奶。
为了确保安全，他雇佣了 \(N\) 头奶牛作为救生员，每头奶牛的班次覆盖一天中的某个连续时间段。为简单起见，游泳池每天从时间 \(t=0\) 开放到时间 \(t=1000\)，因此每个班次可以用两个整数描述，分别表示奶牛开始和结束其班次的时间。例如，一头救生员从时间 \(t=4\) 开始到时间 \(t=7\) 结束，覆盖了 \(3\) 个单位的时间（注意端点表示时间点）。
不幸的是，Farmer John 多雇佣了 \(1\) 名救生员，超出了他的资金支持范围。鉴于他必须解雇恰好 \(1\) 名救生员，剩下的救生员的班次能够覆盖的最长时间是多少？如果至少有一名救生员在场，则某个时间段被视为被覆盖。
【输入】
输入的第一行包含 \(N（1≤N≤100）\)。接下来的 \(N\) 行每行描述一名救生员，用两个范围在 \(0…1000\) 的整数表示该救生员班次的开始和结束时间。所有端点都是唯一的。不同救生员的班次可能会重叠。
【输出】
请输出一个数字，表示如果 Farmer John 解雇 \(1\) 名救生员后，剩下的救生员的班次能够覆盖的最长时间。
【输入样例】
3
5 9
1 4
3 7
【输出样例】
7
【算法标签】
《洛谷 P1697 Lifeguards》 #模拟# #USACO# #2018# #O2优化#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int n; // 区间数量
int B[1005]; // 记录每个整数点被覆盖的次数
int sum; // 统计被至少覆盖一次的点的总数
int a[105], b[105]; // 存储每个区间的起始和结束点
int ans; // 最终结果（最大覆盖点数）
int cnt; // 临时计数器int main()
{cin >> n; // 输入区间数量// 处理每个区间，统计覆盖情况for (int i = 1; i <= n; i++) {cin >> a[i] >> b[i]; // 输入区间[a[i], b[i])// 标记区间内的所有点（左闭右开）for (int j = a[i]; j < b[i]; j++)B[j]++;}// 计算被至少覆盖一次的点的总数for (int i = 0; i <= 1000; i++)if (B[i]) // 如果该点被覆盖过sum++;// 计算移除每个区间后能保留的最大覆盖点数for (int i = 1; i <= n; i++) {cnt = 0;// 统计当前区间中只被覆盖一次的点数for (int j = a[i]; j < b[i]; j++)if (B[j] == 1) // 只被当前区间覆盖的点cnt++;// 更新最大值：总覆盖点数 - 当前区间独有的覆盖点数ans = max(ans, sum - cnt);}cout << ans << endl; // 输出结果return 0;
}
【运行结果】
3
5 9
1 4
3 7
7