这些题均取自于USACO。
单词处理器
奶牛 Bessie 正在完成她的写作课的一篇作文。
由于她写字很难看，她决定用一个单词处理器来输入这篇作文。
这篇作文共有 $N$ 个单词，用空格分隔。
每个单词的长度在 $1$ 到 $15$ 之间，仅由大写和小写字母组成。
根据作业的要求，这篇作文需要用一种特别的方式排版：
每一行包含的字符不超过 $K$ 个，空格不计。
幸好 Bessie 的单词处理器能够处理这样的要求，它会按照如下的方式：
- 如果 Bessie 输入了一个单词，这个单词能够放进当前行，就放在当前行。
- 否则，将这个单词放到下一行，然后继续向下一行添加单词。
当然，同一行中的单词之间仍然用一个空格分隔。每一行的结尾都不应当有空格。
很不幸，Bessie 的单词处理器刚好坏了。
请帮助她正确地排版她的作文！
输入格式
输入的第一行包含两个空格分隔的整数 $N$ 和 $K$。
下一行包含 $N$ 个单词，单词之间用单个空格分隔。
所有单词的长度都不超过一行中的字符上限数 $K$。
输出格式
输出正确排版的 Bessie 的作文。
数据范围
$1≤N≤100$,
$1≤K≤80$
输入样例：
10 7
hello my name is Bessie and this is my essay输出样例：
hello my
name is
Bessie
and this
is my
essay样例解释
第一行包含 $7$ 个非空格字符，包括 “hello” 以及 “my”。
再加入 “name” 会使得第一行包含 $11>7$ 个非空格字符，所以这个单词会被放到下一行。
题解：
简单的模拟。字符串$b$类似于一个计数器，将输入的字符串赋值给$b$，$b$的$size$大于$k$时就换行，并将没被上一行输出的字符赋值给$b$。
寻求方便能直接输出就直接输出，不需要另开字符串数组。
#include<iostream>
#include<cstring>
using namespace std;
string a;
string b;
int main()
{
int n,k;
cin>>n>>k;
for(int i = 1;i <=n; i++) {
cin>>a;
b += a;
if(b.size() > k){
cout<<endl;
b = a;
}
cout<<a<<' ';
}
} 三角形
Farmer John 想要给他的奶牛们建造一个三角形牧场。
有 $N$ 个栅栏柱子分别位于农场的二维平面上不同的点 $(X_1,Y_1)…(X_N,Y_N)$。
他可以选择其中三个点组成三角形牧场，只要三角形有一条边与 $x$ 轴平行，且有另一条边与 $y$ 轴平行。
Farmer John 可以围成的牧场的最大面积是多少？
保证存在至少一个合法的三角形牧场。
输入格式
输入的第一行包含整数 $N$。
以下 $N$ 行每行包含两个整数 $X_i$ 和 $Y_i$，均在范围 $−10^4…10^4$ 之内，描述一个栅栏柱子的位置。
输出格式
由于面积不一定为整数，输出栅栏柱子可以围成的合法三角形的最大面积的两倍。
数据范围
$3 \le N \le 100$
输入样例：
4
0 0
0 1
1 0
1 2输出样例：
2样例解释
位于点 $(0,0)、(1,0)$ 和 $(1,2)$ 的木桩组成了一个面积为 $1$ 的三角形。所以，答案为 $2⋅1=2$。
只有一个其他的三角形，面积为 $0.5$。
题解：
简单模拟，三重循环找到最长边，直接底$×$高。
可以用数组存，用vetcor为了复习一下vector的语法。
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
using namespace std;
int n, ans = 0;
vector<pair<int, int> >a;
int main()
{
cin>>n;
for (int i = 1; i <= n; i++)
{
int c,d;
cin>>c>>d;
a.push_back(make_pair(c,d));
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
{
if (i == j || i == k || j == k) continue; //相同的点直接continue
if (a[i].first == a[j].first && a[j].second == a[k].second)
{
ans = max(ans, abs(a[i].second - a[j].second) * abs(a[i].first - a[k].first));
}
}
cout<<ans;
return 0;
}
社交距离 I
一种新型疾病，COWVID-19，开始在全世界的奶牛之间传播。
Farmer John 正在采取尽可能多的预防措施来防止他的牛群被感染。
Farmer John 的牛棚是一个狭长的建筑物，有一排共 $N$ 个牛栏。
有些牛栏里目前有奶牛，有些目前空着。
得知“社交距离”的重要性，Farmer John 希望使得 $D$ 尽可能大，其中 $D$ 为最近的两个有奶牛的牛栏的距离。
例如，如果牛栏 $3$ 和 $8$ 是最近的有奶牛的牛栏，那么 $D=5$。
最近两头奶牛新来到 Farmer John 的牛群，他需要决定将她们分配到哪两个之前空着的牛栏。
请求出他如何放置这两头新来的奶牛，使得 $D$ 仍然尽可能大。
Farmer John 不能移动任何已有的奶牛；他只想要给新来的奶牛分配牛栏。
输入格式
输入的第一行包含 $N$。
下一行包含一个长为 $N$ 的字符串，由 $0$ 和 $1$ 组成，描述牛棚里的牛栏。
$0$ 表示空着的牛栏，$1$ 表示有奶牛的牛栏。
字符串中包含至少两个 $0$，所以有足够的空间安置两头新来的奶牛。
输出格式
输出 Farmer John 以最优方案在加入两头新来的奶牛后可以达到的最大 $D$ 值（最近的有奶牛的牛栏之间的距离）。
数据范围
$2 \le N \le 10^5$
输入样例：
14
10001001000010输出样例：
2样例解释
在这个例子中，Farmer John 可以以这样的方式加入奶牛，使得牛栏分配变为 $10x010010x0010$，其中 $x$ 表示新来的奶牛。
此时 $D=2$。
不可能在加入奶牛之后取到更大的 $D$ 值。
题解：
用到了贪心+二分，经典组合，和每日一题（一）的牛的学术圈差不多。
重点是这个位置-上个奶牛位置 >= x 且 下个奶牛位置-这个位置 >= x
上个奶牛位置可以顺序扫描时存储，而下个奶牛位置可以逆序预处理nxt数组。
最大正整数用0x3f3f3f3f表示，不要写个1e7会有问题
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int N = 1e5+10,INF = 0x3f3f3f3f;
int a[N],nxt[N];
int n;
string s;
bool check(int x)
{
int cnt = 0, lst = -INF; //cnt计数，等于2就说明方案可行,lst表示上个牛所在的位置
for(int i = 1;i <= n;i++)
{
if(a[i] == 0 && nxt[i] - i >= x && i - lst >= x) //牛应该放在0处且放置位置-上个奶牛位置 >= x且下个奶牛位置-这个位置 >= x
{
cnt++;
lst = i;
}
if(a[i] == 1) lst = i;
if(cnt == 2) return 1;
}
return 0;
}
int main()
{
memset(nxt, INF, sizeof(nxt));
cin>>n>>s;
int temp = -1e6;
int d = n;
for(int i = 1;i <= n;i++)
{
a[i] = s[i-1] - '0';
if(a[i] == 1) d = min(d,i - temp), temp = i; //找到最大的D值，答案会小于等于这个d值
}
for(int i = n;i >= 1;i--)
{
if(a[i] == 0)
{
if(a[i+1] == 1) nxt[i] = i+1;
else nxt[i] = nxt[i+1];
}
}
int l = 0, r = d;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid -1;
}
cout<<l<<endl;
}混合牛奶
农业，尤其是生产牛奶，是一个竞争激烈的行业。
Farmer John 发现如果他不在牛奶生产工艺上有所创新，他的乳制品生意可能就会受到重创！
幸运的是，Farmer John 想出了一个好主意。
他的三头获奖的乳牛，Bessie、Elsie 和 Mildred，各自产奶的口味有些许不同，他打算混合这三种牛奶调制出完美的口味。
为了混合这三种不同的牛奶，他拿来三个桶，其中分别装有三头奶牛所产的奶。
这些桶可能有不同的容积，也可能并没有完全装满。
然后他将桶 $1$ 的牛奶倒入桶 $2$，然后将桶 $2$ 中的牛奶倒入桶 $3$，然后将桶 $3$ 中的牛奶倒入桶 $1$，然后再将桶 $1$ 的牛奶倒入桶 $2$，如此周期性地操作，共计进行 $100$ 次（所以第 $100$ 次操作会是桶 $1$ 倒入桶 $2$）。
当 Farmer John 将桶 $a$ 中的牛奶倒入桶 $b$ 时，他会倒出尽可能多的牛奶，直到桶 $a$ 被倒空或是桶 $b$ 被倒满。
请告诉 Farmer John 当他倒了 $100$ 次之后每个桶里将会有多少牛奶。
输入格式
输入文件的第一行包含两个空格分隔的整数：第一个桶的容积 $c_1$，以及第一个桶里的牛奶量 $m_1$。
第二和第三行类似地包含第二和第三个桶的容积和牛奶量。
输出格式
输出三行，给出倒了 $100$ 次之后每个桶里的牛奶量。
数据范围
$1 \le c_1,m_1 \le 10^9$
输入样例：
10 3
11 4
12 5输出样例：
0
10
2样例解释
在这个例子中，每倒一次之后每个桶里的牛奶量如下：
初始状态： 3 4 5
1. 桶1->2： 0 7 5
2. 桶2->3： 0 0 12
3. 桶3->1： 10 0 2
4. 桶1->2： 0 10 2
5. 桶2->3： 0 0 12
（之后最后三个状态循环出现……）题解：
简单模拟，三次操作写在一起成一次循环。
每次对其中一个桶的当前牛奶量和另一个桶的剩余容量比较大小。
c[]为桶容量，w[]为当前桶中有多少牛奶。
$a$桶倒入$b$桶时，$a$桶增加，$b$桶减少。
minv = min(w[i], c[i + 1] - w[i + 1]) when i = 0, 1;
minv = min(w[3], c[1] - w[1]) when i = 2;#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int c[3],w[4];
int main()
{
for(int i = 0;i<3;i++) cin>>c[i]>>w[i];
int time = 100;
while(1)
{
if(time)
{
int a = min(w[0], c[1] - w[1]);
w[0] -= a;
w[1] += a;
time --;
}
if(time)
{
int a = min(w[1], c[2] - w[2]);
w[1] -= a;
w[2] += a;
time --;
}
if(time)
{
int a = min(w[2], c[0] - w[0]);
w[2] -= a;
w[0] += a;
time --;
}
if(!time) break;
}
cout<<w[0]<<endl;
cout<<w[1]<<endl;
cout<<w[2]<<endl;
} 果壳游戏
为了消磨时光，奶牛 Bessie 和她的朋友 Elsie 喜欢玩一种她们在农业展览会上看到的游戏。
游戏准备阶段，Bessie 在桌子上放置三个倒置的坚果壳，1号坚果壳放在位置1，2号坚果壳放在位置2，3号坚果壳放在位置3。并在其中一个坚果壳下面藏了一块小的鹅卵石（至少她希望这是一块鹅卵石——她在一块牧场的地上找到的）。
随后 Bessie 会两两调换坚果壳，鹅卵石会随着坚果壳一起移动，同时 Elsie 试着去猜鹅卵石的位置。
奶牛们在农业展览会上看到的这个游戏的标准形式是玩家可以看到鹅卵石初始的位置，然后要求玩家猜所有交换完成之后鹅卵石最终的位置。
然而，现在奶牛们想要去进行这样一种玩法，Elsie 不知道鹅卵石的初始位置，同时她可以在每一次交换之后猜一下鹅卵石的位置。
Bessie 知道正确答案，在游戏结束后会给 Elsie 一个分数，等于她猜对的次数。
给定所有的交换和 Elsie 的猜测，但是不给出鹅卵石的初始位置，请求出 Elsie 最高可能获得的分数。
输入格式
输入的第一行包含一个整数 $N$，为交换的次数。
以下 $N$ 行每行描述了游戏的一个回合，包含三个整数 $a、b$ 和 $g$，表示 Bessie 交换了位置 $a$ 和 $b$ 的坚果壳，然后 Elsie 猜的是位置 $g$。
所有这三个数均为 $1、2、3$ 之一，并且 $a≠b$。
输出格式
输出 Elsie 可以得到的最高分数。
数据范围
$1 \le N \le 100$
输入样例：
3
1 2 1
3 2 1
1 3 1输出样例：
2样例解释
在这个例子中，Elsie 最多可以获得 $2$ 分。
如果鹅卵石开始时位于坚果壳 $1$ 下面，那么她猜中了一次（最后一次）。
如果鹅卵石开始时位于坚果壳 $2$ 下面，那么她猜中了两次（开始两次）。
如果鹅卵石开始时位于坚果壳 $3$ 下面，那么她没有猜对任何一次。
题解：
还是模拟枚举，比较绕。😢
如果某次交换后，猜石头在编号为 x 的坚果壳下面，只有石子位置在编号坚果为 x 的壳所在位置上的时候，才得分。
如果用 f[i] 保存编号为 i 的坚果壳的位置。猜编号为 x 的坚果壳，只有石子位置在 f[x] 的时候才得分。
#include<iostream>
using namespace std;
int f[4];
int cnt[4];
int main()
{
int n;
cin>>n;
for(int i = 1;i <= 3;i++) f[i] = i; //编号为i的坚果壳在f[i]
for(int i = 0;i < 0;i++)
{
int a,b,c;
cin>>a>>b>>c;
swap(f[a],f[b]);
cnt[f[c]]++; //猜在c坚果壳中，所以只有石子位置为 f[c] 的情况下，猜 c 坚果壳才得分
}
int ans = max(cnt[1],max(cnt[b],cnt[c]));
cout<<ans;
} 
