分类讨论专题
困牛放牧
Farmer John 的三头获奖奶牛 Bessie、Elsie 和 Mildred，总是会迷路走到农场上遥远的地方去！
他需要你帮助将她们一起赶回来。
农场的草地大体是一块狭长的区域——我们可以将其想象成一条数轴，奶牛可以占据数轴上的任意整数位置。
这 $3$ 头奶牛现在正位于不同的整数位置，Farmer John 想要移动她们，使得她们占据三个相邻的位置（例如，位置 $6、7、8$）。
不幸的是，奶牛们现在很困，Farmer John 要让她们集中精力听从命令移动并不容易。
任意时刻，他只能使得一头处在“端点”（在所有奶牛中位置最小或最大）位置的奶牛移动。
当他移动奶牛时，他可以命令她走到任意一个未被占用的整数位置，只要在新的位置上她不再是一个端点。
可以看到随着时间的推移，这样的移动可以使奶牛们趋向越来越近。
请求出使得奶牛们集中到相邻位置所进行的移动次数的最小和最大可能值。
输入格式
输入包含一行，包括三个空格分隔的整数，为 Bessie、Elsie 和 Mildred 的位置。
输出格式
输出的第一行包含 Farmer John 需要将奶牛们聚集起来所需进行的最小移动次数。
第二行包含他将奶牛聚集起来能够进行的最大移动次数。
数据范围
每个位置均为一个范围 $1…10^9$ 内的整数。
输入样例：
4 7 9输出样例：
1
2样例解释
最小移动次数为 $1$——如果 Farmer John 将位置 $4$ 的奶牛移动到位置 $8$，那么奶牛们就处在连续的位置 $7、8、9$。
最大移动次数为 $2$。例如，位置 $9$ 的奶牛可以被移动到位置 $6$，然后位置 $7$ 的奶牛可以被移动到位置 $5$。
题解
贪心+分类讨论
最少次数:
情况1: $3$ 头牛已经连续， 即----abc-----, 直接输出 $0$
情况2: a, b两头牛间隔 $1$， 即---a-b----c-----, 此时只要把c移动到a、b中间即可，输出 $1$
情况3: b, c两头牛间隔 $1$， 即---a-----b-c-----, 此时只要把a移动到b、c中间即可，输出 $1$
情况4: a,b,c 任意两头牛间隔都不为 $1$，即---a------b----c---,
(1)此时只要把c移动到b前面 $2$ 位，得到---a-----c-b-----，
(2)然后再把a移到c,b中间,得到--------cab-----
一共两次操作，输出 $2$
最多次数:
举例，对于—a——b—-c—这种情况
我们可以贪心地把c移到b前面，再把b移到c前面，接着把c移到b前面，这样往复操作
1.—a—–cb——–
2.—a—-bc———
3.—a—cb———-
4.—a–bc———–
5.—a-cb————
6.—abc————-
所以我们只需找出b-a和c-b的两个间隔谁更大再减1即可
代码实例：
#include<iostream>
using namespace std;
int main()
{
int a, b, c; cin >> a >> b >> c;
// 先输出最少次数
if ((b==a+1)&&(c==b+1)) cout<<0<<endl; // 上述情况1
else if (b == a + 2 || c == b + 2) cout<<1<<endl; // 上述情况2和3
else cout<<2<<endl; // 上述情况4
// 然后输出最多次数
cout << max(b - a, c - b) - 1 << endl;
return 0;
}水桶传递队列
农场上起火了，奶牛们正在紧急赶去灭火！
农场可以用一个像这样的 $10 \times 10$ 的字符方阵来描述：
..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........字符’B’表示正着火的牛棚，字符’L’表示一个湖，而字符’R’表示农场上的一块巨大岩石。
奶牛们想要沿着一条湖到牛棚之间的路径组成一条“水桶传递队列”，这样她们就可以沿着这条路径传递水桶来帮助灭火。
当两头奶牛在东南西北四个方向上相邻时水桶可以在她们之间传递。
湖边的奶牛也是如此——奶牛只能在紧挨着湖的时候才能用水桶从湖里取水。
类似地，奶牛只能在紧挨着牛棚的时候才能用水去灭牛棚的火。
请帮助求出奶牛们为了组成这样的“水桶传递队列”需要占据的’.’格子的最小数量。
奶牛不能站在岩石所在的方格之内，此外保证牛棚和湖不是相邻的。
输入格式
输入包含 $10$ 行，每行 $10$ 个字符，描述这个农场的布局。
输入保证图案中恰有一个字符’B’、一个字符’L’以及一个字符’R’。
输出格式
输出一个整数，为组成一条可行的水桶传递队列所需要的奶牛的最小数量。
输入样例：
..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........输出样例：
7样例解释
在这个例子中，以下是一个可行的方案，使用了最小数量的奶牛（7）：
..........
..........
..........
..B.......
..C.......
..CC.R....
...CCC....
.....C....
.....L....
..........题解
解法一：
地图中求最短距离，标准的广度优先遍历。
#include<iostream>
#include<queue>
using namespace std;
const int N = 10;
char map[N][N];
bool st[N][N];
int dist[N][N];
queue<pair<int,int> > q;
int lx,ly;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int main()
{
for(int i = 0;i<10;i++)
{
for(int j = 0;j<10;j++)
{
cin>>map[i][j];
if(map[i][j]=='L')
{
lx = i;
ly = j;
}
}
}
q.push({lx,ly});
dist[lx][ly] = 0;
st[lx][ly] = true;
while(!q.empty())
{
auto temp = q.front();
q.pop();
int a = temp.first;
int b = temp.second;
for(int i = 0;i < 4;i++)
{
int x = a + dx[i];
int y = b + dy[i];
if(x >= 0 && y >= 0 && x < 10 && y < 10 && !st[x][y] && map[x][y] != 'R')
{
if(map[x][y] == 'B')
{
cout<<dist[a][b];
return 0;
}
else
{
st[x][y] = true;
dist[x][y] = dist[a][b] + 1;
q.push({x,y});
}
}
}
}
}解法二：
输入保证图案中恰有一个字符’ $B$ ’、一个字符’L’以及一个字符’ $R$ ’。
关键是只有一个 $R$ ，即只有一个障碍物，所以可以不用BFS，直接分类讨论完事。
两点之间的最短路是曼哈顿距离，当起点与终点的行与列均不同时，一定能走曼哈顿距离
比如：
.....
.B...
.R...
...L.
.....能走的路为：
.....
.BCC.
.R.C.
...L.
.....此时，无论R在哪里，都不会影响行走方法，所以就是两点的曼哈顿距离。
需要的奶牛数量就是曼哈顿距离 $−1$
那什么时候不是曼哈顿距离呢？我们来看一下下面这种情况：
.......
.L.R.B.
.......当L、B、R在同一行，并且R在L和B中间时，由于路上被R挡住，所以无法直接走曼哈顿距离，只能绕路走。
..CCC..
.LCRCB.
.......同理，当L、B、R在同一列，并且R在L和B中间时，也不得不绕路走。
此时，需要的奶牛数量为曼哈顿距离 $+1$
所以，我们得出如下结论：
当L、B、R在同一行或者同一列，并且R在L和B中间时，需要的奶牛数量为两点的曼哈顿距离 $+1$，其余均为曼哈顿距离 $−1$
#include<iostream>
using namespace std;
char g[10][10];
int main()
{
int x1, y1, x2, y2, x3, y3;
for (int i=0; i<10; i++)
{
scanf("%s", g[i]);
for (int j=0; j<10; j++)
if (g[i][j]=='L')
x1=i, y1=j;
else if (g[i][j]=='R')
x2=i, y2=j;
else if (g[i][j]=='B')
x3=i, y3=j;
}
int ans;
if (x1==x2&&x2==x3&&(y1<y2&&y2<y3||y1>y2&&y2>y3))
ans=abs(x1-x3)+abs(y1-y3)+1;
else if (y1==y2&&y2==y3&&(x1<x2&&x2<x3||x1>x2&&x2>x3))
ans=abs(x1-x3)+abs(y1-y3)+1;
else
ans=abs(x1-x3)+abs(y1-y3)-1;
printf("%d\n", ans);
return 0;
}
阻挡广告牌
在漫长的产奶期间，奶牛贝茜喜欢透过窗户盯着马路对面的两个巨大的矩形广告牌，上面写着“农夫亚历克斯的惊人开胃苜蓿”和“农夫格雷格的大粒谷物”。
广告牌上这两种精美的牛饲料看上去比农场里的草美味的多。
有一天，当贝茜凝视着窗外时，她惊异地看到一辆巨大的矩形卡车停在马路对面。
卡车的侧面有一个广告，上面写着“农夫史密斯的精湛牛排”。
贝茜对此不太感兴趣，但她非常担心卡车可能会阻挡她观看最喜欢的两个广告牌的视野。
给定两个广告牌的位置和卡车的位置，请计算两个广告牌的仍然可见的总面积。
卡车可能挡到两个广告牌或只挡到其中一个，或都挡不到。
输入格式
第一行包含四个整数 $x_1,y_1,x_2,y_2$，其中 $(x_1,y_1)$ 和 $(x_2,y_2)$ 表示在贝茜的二维视野中，第一个广告牌的左下角和右上角坐标。
第二行按照如上形式，包含四个整数，表示第二个广告牌的左下角和右上角坐标。
第三行按照如上形式，包含四个整数，表示卡车侧面的左下角和右上角坐标。
输出格式
输出两个广告牌的仍然可见的总面积。
数据范围
$-1000 \le x_1,y_1,x_2,y_2 \le 1000$,
保证两个广告牌之间重叠面积为 $0$。
输入样例：
1 2 3 5
6 0 10 4
2 1 8 3输出样例：
17样例解释
第一块广告牌的可见面积为 $5$，第二块广告牌的可见面积为 $12$。
题解
数据量不大，简单的模拟，将两个广告牌的位置标为 $1$，卡车的位置标为 $0$，我们只需要遍历一片数组，找出 $1$ 的个数即可
类似于这个样子：
#include <iostream>
using namespace std;
const int N = 2010;
int g[N][N];
int x1, y1, x2, y2;
int a1, b1, a2, b2;
int u1, v1, u2, v2;
int main(){
cin >> x1 >> y1 >> x2 >> y2;
x1 += 1000;//数据中有负数，全部转换成整数
x2 += 1000;
y1 += 1000;
y2 += 1000;
cin >> a1 >> b1 >> a2 >> b2;
a1 += 1000;//数据中有负数，全部转换成整数
a2 += 1000;
b1 += 1000;
b2 += 1000;
cin >> u1 >> v1 >> u2 >> v2;
u1 += 1000;//数据中有负数，全部转换成整数
u2 += 1000;
v1 += 1000;
v2 += 1000;
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(i > x1 && i <= x2 && j > y1 && j <= y2) //放第一个广告牌
g[i][j] = 1;
if(i > a1 && i <= a2 && j > b1 && j <= b2)//放第二个广告牌
g[i][j] = 1;
if(i > u1 && i <= u2 && j > v1 && j <= v2)//放卡车
g[i][j] = 0;
}
}
int res = 0;
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
res += g[i][j];
}
}
cout << res;
return 0;
}正规的做法就是一道数学题
#include <iostream>
using namespace std;
struct Rect {
int x1, y1, x2, y2;
int area() {
return (y2 - y1) * (x2 - x1);
}
};
int intersect(Rect p, Rect q) {
int xOverlap = max(0, min(p.x2, q.x2) - max(p.x1, q.x1));
int yOverlap = max(0, min(p.y2, q.y2) - max(p.y1, q.y1));
return xOverlap * yOverlap;
}
int main() {
Rect a, b, t;
cin >> a.x1 >> a.y1 >> a.x2 >> a.y2;
cin >> b.x1 >> b.y1 >> b.x2 >> b.y2;
cin >> t.x1 >> t.y1 >> t.x2 >> t.y2;
cout << a.area() + b.area() - intersect(a, t) - intersect(b, t) << endl;
}阻挡广告牌 II
奶牛贝茜曾经从农场中向外看去，可以看到两个刊登着美味的牛饲料广告的广告牌，这令她非常满意。
不幸的是，其中一个广告牌最近已更新，现在刊登着广告“农民拉里的割草机”。
但是贝茜可不喜欢割草机，这些割草机只会把她爱吃的草割的一干二净。
幸运的是，剩下的牛饲料广告牌位于割草机广告牌的前面，有可能将其遮挡住。
贝茜希望这个讨厌的割草机广告牌能够完全从自己的视线中消失，并为此制定了一个冒险计划。
她计划从谷仓里偷一个大的矩形防水布，并在深夜偷偷溜走，用它覆盖割草机广告牌的其余部分，使得她能完全看不到割草机广告牌。
给定两个广告牌的位置，请帮助贝茜计算她所需要的防水布的最小面积。
由于谷仓中只有矩形的防水布，因此贝茜发现为了将割草机广告牌完全遮盖，所需的防水布面积可能会大于割草机广告牌的裸露面积，如下例所示。
防水布在放置时，其边必须与广告牌的边平行，即不能倾斜放置。
输入格式
第一行包含四个整数 $x_1,y_1,x_2,y_2$，其中 $(x_1,y_1)$ 和 $(x_2,y_2)$ 表示割草机广告牌的左下角和右上角坐标。
第二行按照如上形式，包含四个整数，表示牛饲料广告牌的左下角和右上角坐标。
牛饲料广告牌可能完全遮盖了割草机广告牌，或部分遮盖了割草机广告牌，也可能完全没有遮盖割草机广告牌。
输出格式
输出用来遮盖割草机广告牌的防水布的最小面积。
数据范围
$-1000 \le x_1,y_1,x_2,y_2 \le 1000$
输入样例：
2 1 7 4
5 -1 10 3输出样例：
15样例解释
虽然牛饲料广告牌遮盖住了割草机广告牌的右下角的一部分，但这并没有起到作用。
想要完全遮盖割草机广告牌，仍然需要一块和它尺寸相同的防水布。
题解
可以和上一题用模拟，代码略
也可以分类讨论
#include <iostream>
using namespace std;
int main()
{
int x[5], y[5];
for(int i=1; i<=4; i++)
cin>>x[i]>>y[i];
//分类讨论
if(x[4]>=x[2] && x[3]<=x[1] && y[4]>=y[2] && y[3]<=y[1])
cout<<0;//完全覆盖
else if(x[3]<=x[1] && y[3]<=y[1] && y[4]>y[1] && x[4]>=x[2])
cout<<(x[2]-x[1])*(y[2]-y[4]);//上方未覆盖
else if(y[3]<y[2] && x[3]<=x[1] && y[4]>=y[2] && x[4]>=x[2])
cout<<(x[2]-x[1])*(y[3]-y[1]);//下方未覆盖
else if(x[4]>x[1] && x[3]<=x[1] && y[4]>=y[2] && y[3]<=y[1])
cout<<(x[2]-x[4])*(y[2]-y[1]);//右侧未覆盖
else if(x[3]<x[2] && x[4]>=x[2] && y[4]>=y[2] && y[3]<=y[1])
cout<<(x[3]-x[1])*(y[2]-y[1]);//左侧未覆盖
else cout<<(x[2]-x[1])*(y[2]-y[1]);//完全未覆盖 以及只覆盖边角
return 0;
}传送
Farmer John 最讨厌的农活是运输牛粪。
为了精简这个过程，他制造了一个伟大的发明：便便传送门！
与使用拖拉机拖着装满牛粪的大车从一个地点到另一个地点相比，他可以使用便便传送门将牛粪从一个地点瞬间传送到另一个地点。
Farmer John 的农场沿着一条长直道路而建，所以他农场上的每个地点都可以简单地用该地点在道路上的位置来表示（相当于数轴上的一个点）。
一个传送门可以用两个数 $x$ 和 $y$ 表示，被拖到地点 $x$ 的牛粪可以瞬间传送到地点 $y$，反之亦然。
Farmer John 想要将牛粪从地点 $a$ 运输到地点 $b$，他建造了一个可能对这一过程有所帮助的传送门（当然，如果没有帮助，他也可以不用）。
请帮助他求出他需要使用拖拉机运输牛粪的总距离的最小值。
输入格式
输入仅包含一行，为四个用空格分隔的整数：$a$ 和 $b$，表示起始地点和结束地点，后面是 $x$ 和 $y$，表示传送门。
所有的位置都是范围为 $0…100$ 的整数，不一定各不相同。
输出格式
输出一个整数，为 Farmer John 需要用拖拉机运输牛粪的最小距离。
输入样例：
3 10 8 2输出样例：
3样例解释
在这个样例中，最佳策略是将牛粪从位置 $3$ 运到位置 $2$，传送到位置 $8$，再运到位置 $10$。
所以需要用拖拉机的总距离为 $1 + 2 = 3$。
题解
还是分类讨论
起点 a, 终点 b，传送门：c, d.
情况一：不使用传送门，abs(b - a)
情况二： a -> c 然后通过c传送到d, 再从d->b。总距离为abs(a - c) + abs(b - d)。
情况三： a -> d 然后通过d传送到c, 再从c->b。总距离为abs(a - d) + abs(b - c)。
三者取最小
#include <iostream>
using namespace std;
int a, b, c, d;
int main(){
cin >> a >> b >> c >> d;
//3 种情况取最小值即可
cout << min({abs(b - a), abs(a - c) + abs(d - b), abs(a - d) + abs(b - c)});
return 0;
}组队井字游戏
Farmer John 有 $26$ 头奶牛，恰好她们名字都以不同的字母开头，所以 Farmer John 用每头奶牛的名字的首字母来指代她——一个 $A…Z$ 之间的字母。
这些奶牛最近沉迷于井字游戏，但是由于她们并不满足只有两头奶牛可以一起玩，她们改编了这个游戏，可以让许多奶牛可以一块儿玩！
就像常规的井字游戏一样，这个游戏是在一块 $3×3$ 的棋盘上进行的，只是与仅用 $X$ 和 $O$ 不同，每个格子用一个 $A…Z$ 之间的字母标记，表示占有这个格子的奶牛名字的首字母。
以下是一个棋盘的例子：
COW
XXO
ABC这些奶牛会在她们迷惑于如何判断胜负之前就占满这九个格子。
显然，就像常规的井字游戏一样，如果任何一头奶牛占有了一整行、一整列，或是一整条对角线，那么这头奶牛就获胜了。
然而，由于奶牛认为多牛游戏中这并不容易出现，所以她们决定允许奶牛组成两牛一队，如果某一行、一列，或是一条对角线仅包含一队的两头奶牛的字母，并且同时包含了这两头奶牛（不仅仅是一头）的字母，那么这一队就获胜。
请帮助奶牛们判断有多少头奶牛或是两头奶牛组成的队伍可以获胜。
注意棋盘上的同一个格子可能在不同奶牛或队伍的获胜中均被用到。
输入格式
输入包含三行，每行三个 $A…Z$ 之间的字符。
输出格式
输出包含两行。
第一行，输出能够获胜的单独的奶牛的数量。
第二行，输出能够获胜的两头奶牛组成的队伍的数量。
输入样例：
COW
XXO
ABC输出样例：
0
2样例解释
在这个例子中，没有单独的奶牛可以获得胜利。
但是，如果奶牛 $C$ 和奶牛 $X$ 组队，她们可以通过 $C-X-C$ 对角线获胜。
同样地，如果奶牛 $X$ 和 $O$ 组队，她们可以通过中间一行取胜。
题解
官方题解：
#include <iostream>
using namespace std;
char B[3][3];
// Does 1 cow win?
int cow_wins(char ch)
{
// Check diagonals
if (B[0][0] == ch && B[1][1] == ch && B[2][2] == ch) return 1;
if (B[0][2] == ch && B[1][1] == ch && B[2][0] == ch) return 1;
// Check rows and columns
for (int i=0; i<3; i++) {
if (B[0][i] == ch && B[1][i] == ch && B[2][i] == ch) return 1;
if (B[i][0] == ch && B[i][1] == ch && B[i][2] == ch) return 1;
}
return 0;
}
// Test if a team wins based on 3 characters in a row, column, or diagonal
bool check3(char ch1, char ch2, char a, char b, char c)
{
// All 3 characters have to be either ch1 or ch2
if (a != ch1 && a != ch2) return false;
if (b != ch1 && b != ch2) return false;
if (c != ch1 && c != ch2) return false;
// ch1 and ch2 have to appear at least once each
if (a != ch1 && b != ch1 && c != ch1) return false;
if (a != ch2 && b != ch2 && c != ch2) return false;
return true;
}
// Does a team win?
int team_wins(char ch1, char ch2)
{
// Check diagonals
if (check3(ch1, ch2, B[0][0], B[1][1], B[2][2])) return 1;
if (check3(ch1, ch2, B[0][2], B[1][1], B[2][0])) return 1;
// Check rows and columns
for (int i=0; i<3; i++) {
if (check3(ch1, ch2, B[0][i], B[1][i], B[2][i])) return 1;
if (check3(ch1, ch2, B[i][0], B[i][1], B[i][2])) return 1;
}
return 0;
}
int main()
{
for (int i=0; i<3; i++)
for (int j=0; j<3; j++)
cin >> B[i][j];
int answer1 = 0, answer2 = 0;
for (char ch = 'A'; ch <= 'Z'; ch++)
answer1 += cow_wins(ch);
for (char ch1 = 'A'; ch1 <= 'Z'; ch1++)
for (char ch2 = ch1+1; ch2 <= 'Z'; ch2++)
answer2 += team_wins(ch1, ch2);
cout << answer1 << "\n" << answer2 << "\n";
return 0;
}
