这些题均来自于USACO 2021，比较简单的题。
你知道你的ABC吗
$Farmer John$ 的奶牛正在 mooZ 视频会议平台上举行每日集会。
她们发明了一个简单的数字游戏，为会议增添一些乐趣。
$Elsie$ 有三个正整数$ A、BA、B 和 C (A≤B≤C）$。
这些数字是保密的，她不会直接透露给她的姐妹$ Bessie$。
她告诉 $Bessie$ 七个范围在 $1…109$ 之间的整数（不一定各不相同），并宣称这是 $A、B、C、A+B、B+C、C+A和 A+B+CA+B+C$ 的某种排列。
给定这七个整数，请帮助 $Bessie$ 求出$ A、B 和 C$。
可以证明，答案是唯一的。
输入格式
输入一行，包含七个空格分隔的整数。
输出格式
输出 $A、B$和 $C$，用空格分隔。
数据范围
$1≤所有输入的整数≤10^9$
输入样例：
2 2 11 4 9 7 9输出样例：
2 2 7题解：
一道非常简单的数学思维题，因为都是正整数，相加只会比原来的数字更大，排个序。最小的两个就是$A$，$B$，最大的一个必然是$A+B+C$，相减就得到了$C$
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
LL arr[7];
int main()
{
LL a,b,c;
for(int i = 0;i<7;i++)
{
cin>>arr[i];
}
sort(arr,arr+7);
c = arr[6]-arr[0]-arr[1];
cout<<arr[0]<<" "<<arr[1]<<" "<<c;
}放养但没有完全放养
一个鲜为人知的事实是，奶牛拥有自己的文字：「牛文」。
牛文由 $26$ 个字母 a 到 z 组成，但是当奶牛说牛文时，可能与我们所熟悉的 abcdefghijklmnopqrstuvwxyz 不同，她会按某种特定的顺序排列字母。
为了打发时间，奶牛 $Bessie$ 在反复哼唱牛文字母歌，而 $Farmer John$ 好奇她唱了多少遍。
给定一个小写字母组成的字符串，为 $Farmer John $听到 $Bessie$ 唱的字母，计算 $Bessie$ 至少唱了几遍完整的牛文字母歌，使得 $Farmer John$ 能够听到给定的字符串。
$Farmer John$ 并不始终注意 $Bessie$ 所唱的内容，所以他可能会漏听 $Bessie$ 唱过的一些字母。
给定的字符串仅包含他记得他所听到的字母。
输入格式
输入的第一行包含 $26$ 个小写字母，为a到z的牛文字母表顺序。
下一行包含一个小写字母组成的字符串，为 $Farmer John$ 听到 $Bessie$ 唱的字母。
输出格式
输出 $Bessie$ 所唱的完整的牛文字母歌的最小次数。
数据范围
字符串的长度不小于 $1$ 且不大于 $1000$。
输入样例：
abcdefghijklmnopqrstuvwxyz
mood输出样例：
3样例解释
在这个样例中，牛文字母表与日常的字母表的排列一致。
$Bessie$ 至少唱了三遍牛文字母歌。
有可能 $Bessie$ 只唱了三遍牛文字母歌，而 $Farmer John$ 听到了以下被标记为大写的字母。
abcdefghijklMnOpqrstuvwxyz
abcdefghijklmnOpqrstuvwxyz
abcDefghijklmnopqrstuvwxyz题解：
也是一道思维题，想明白就行了。其实，只要我后面的字符比前面的字符在牛文字母表的顺序中靠前或者相等，就得再听一遍牛文字母歌。
#include<iostream>
#include<cstring>
using namespace std;
string b,c;
int a[26];
int ans;
int main()
{
cin>>b;
for(int i = 0;i<26;i++)
{
a[b[i]-'a'] = i;
}
cin>>c;
for(int i = 1;i<c.size();i++)
{
if(a[c[i]-'a']<=a[c[i-1]-'a']) ans++;
}
cout<<ans+1;
} 牛年
$Farmer John$ 的奶牛们得知最近正在庆祝牛年的到来时十分兴奋。
牛年总是奶牛们的最爱。
我们知道，中国历法中每一年所对应的生肖遵循 $12$ 年的周期：Ox, Tiger, Rabbit, Dragon, Snake, Horse, Goat, Monkey, Rooster, Dog, Pig, Rat（牛、虎、兔、龙、蛇、马、羊、猴、鸡、狗、猪、鼠），然后回到牛。
奶牛 $Bessie$ 自豪地说她是在许多年前的一个牛年出生的。
她的朋友 $Elsie$ 想要知道她与 $Bessie$ 出生相差多少年，并且希望你能够通过查看农场上若干奶牛出生年份之间的关系来帮助她推算。
输入格式
输入的第一行包含一个整数 $N$。
以下 $N$ 行每行包含一个 $8 $个单词的短语，指定了两头奶牛的出生年份之间的关系，格式为 Mildred born in previous Dragon year from Bessie（Mildred 在 $Bessie$ 出生的前一个龙年出生），或 Mildred born in next Dragon year from Bessie（$Mildred$ 在 $Bessie$ 出生的后一个龙年出生）。
最后一个单词是农场上某一头奶牛的名字，为 “$Bessie$” 或一头已经在之前的输入中出现过的奶牛。
第一个单词是农场上某一头奶牛的名字，不为 “$Bessie$” 且未在之前的输入中出现过。
所有的奶牛名字不超过 $10$ 个字符，且仅包含字符 $a..z$ 或 $A..Z$。
第$5$ 个单词是上述十二生肖之一。
第 $4 $个单词是 previous（之前）或 next（之后）之一。
例如，如果短语为 Mildred born in previous Dragon year from Bessie，则 Mildred 的出生年份为最为接近且严格处于 $Bessie$ 的出生年份之前（不等于）的龙年。
输出格式
输出 $Bessie$ 和 $Elsie$ 的出生年份之间相差的年数。输入保证可以通过给定的信息求出结果。
数据范围
$1≤N≤100$
输入样例：
4
Mildred born in previous Dragon year from Bessie
Gretta born in previous Monkey year from Mildred
Elsie born in next Ox year from Gretta
Paulina born in next Dog year from Bessie输出样例：
12样例解释
在以上的输入中，
- $Elsie$ 在 $Bessie$ 之前 $12$ 年出生。
- $Mildred$ 在 $Bessie$ 之前 $9$ 年出生。
- $Gretta$ 在 $Bessie$ 之前 $17$ 年出生。
- $Paulina$ 在 $Bessie$ 之后 $9$ 年出生。
题解：
用map模拟（类似一个字典）用unordered_map不用排序可能会更快，记录每头牛相差$Bessie$的年龄，把$Bessie$设置为元年（$0$年）。模拟题就是注意面面俱到。
C++对于负数取余还是负数，所以余数要加上一个除数再模，这是一个技巧：int r = ((x - y) % 12 + 12) % 12;
#include<iostream>
#include<unordered_map>
#include<cstring>
#include<cmath>
using namespace std;
unordered_map<string,int> id={
{"Ox", 0}, {"Tiger", 1}, {"Rabbit", 2},
{"Dragon", 3}, {"Snake", 4}, {"Horse", 5},
{"Goat", 6}, {"Monkey", 7}, {"Rooster", 8},
{"Dog", 9}, {"Pig", 10}, {"Rat", 11}
};
int main()
{
unordered_map<string,int> p;
p["Bessie"] = 0;
int n;
cin>>n;
while(n--)
{
string s[8];
for(int i = 0;i<8;i++) cin>>s[i];
if(s[3]=="previous")
{
int x = p[s[7]],y = id[s[4]];
int r = ((x - y) % 12 + 12) % 12;
if(!r) r = 12;
p[s[0]] = x - r;
}
else{
int x = p[s[7]],y = id[s[4]];
int r = ((y-x) % 12 + 12) % 12;
if(!r) r = 12;
p[s[0]] = x + r;
}
}
cout<<abs(p["Elsie"])<<endl;
return 0;
} 牛的学术圈 I
由于对计算机科学的热爱，以及有朝一日成为 「$Bessie$ 博士」的诱惑，奶牛 $Bessie$ 开始攻读计算机科学博士学位。
经过一段时间的学术研究，她已经发表了 $N $篇论文，并且她的第$ i $篇论文得到了来自其他研究文献的 $ci $次引用。
$Bessie$ 听说学术成就可以用 $h $指数来衡量。
$h$ 指数等于使得研究员有至少 $h$ 篇引用次数不少于 $h$ 的论文的最大整数 $h$。
例如，如果一名研究员有 $4$篇论文，引用次数分别为$ (1,100,2,3)$，则$ h$ 指数为$ 2$，然而若引用次数为 $(1,100,3,3)$ 则 $h$ 指数将会是$ 3$。
为了提升她的 $h$指数，$Bessie$ 计划写一篇综述，并引用一些她曾经写过的论文。
由于页数限制，她至多可以在这篇综述中引用 $L$ 篇论文，并且她只能引用每篇她的论文至多一次。
请帮助 $Bessie$ 求出在写完这篇综述后她可以达到的最大$ h$ 指数。
注意$ Bessie$ 的导师可能会告知她纯粹为了提升$h$ 指数而写综述存在违反学术道德的嫌疑；我们不建议其他学者模仿 $Bessie$ 的行为。
输入格式
输入的第一行包含$ N$ 和 $L$。
第二行包含 $N $个空格分隔的整数 $c1,…,cN$。
输出格式
输出写完综述后 $Bessie$ 可以达到的最大 $h$ 指数。
数据范围
$1≤N≤10^5$,
$0≤ci≤10^5$,
$0≤L≤10^5$
输入样例1：
4 0
1 100 2 3输出样例1：
2样例1解释
$Bessie$ 不能引用任何她曾经写过的论文。上文中提到，$(1,100,2,3)$ 的 $h$ 指数为 $2$。
输入样例2：
4 1
1 100 2 3输出样例2：
3如果 $Bessie$ 引用她的第三篇论文，引用数会变为 $(1,100,3,3)$。上文中提到，这一引用数的$ h$ 指数为 $3$。
题解：
略微有点难度，不再是简单的模拟，是灵能传输的弱化版。
将文章从大到小排序，然后从小到大枚举$h$，这个$h$要成立要满足下面两个条件：
- 由于我们选择的是前$h$篇文章，这$h$篇文章是所有文章里最大的$h$篇，因此这h篇中的最小值要大于等于$h−1$。
- 这$h$篇文章中，引用次数为$h−1$的文章数量应该小于等于$L$。
方法一：贪心
选择部分数，然后让他们加$1$后使得$a[h+1]=h+1$,首先就是要选择$a[h+1]$这个点，在这里进行判断
，如果$a[h+1]<h$的话，就不可能变成$h+1$了(因为一个数最多加$1$)，所以最大指数就是$h$,如果$a[h+1]=h$的话，要找逆序排
列中在$1$~$h+1$，这个范围中有多少个点等于$h$($cnt$个)，这些点都需要加$1$，因为这些点都需要大于等于$h+1$,所以，至少需要
$cnt$个点，当$cnt<=L$的时候满足条件，指数是$h+1$,否则是$h$。
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 1e5+10;
int a[N];
bool cmp(int x,int y)
{
return x > y;
}
int main()
{
int n,l;
cin>>n>>l;
int h = 0;
for(int i = 1;i <= n;i++) cin>>a[i];
sort(a+1,a+n+1,cmp);
for(int i = 1;i <= n;i++)
{
if(a[i]>=i) h = i;
else break;
}
if(a[h+1]<h)
{
cout<<h<<endl;
return 0;
}
int cnt = 0;
for(int i = 1;i<=h+1;i++)
{
if(a[i]==h) cnt++;
}
if(l>=cnt) cout<<h+1<<endl;
else cout<<h<<endl;
}方法二：二分
因为排完序后，有单调性，可以二分。只有$h$成立时，$0$~$h$都成立，$h$+$1$~$n$不成立
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1e5+10;
int a[N];
int n,l;
bool cmp(int a,int b)
{
return a>b;
}
bool check(int x)
{
//sum是满足条件的的次数,cnt是+1的次数
int sum=0,cnt=l;
for(int i=1;i<=x;i++)
{
if(a[i]>=x-1) sum++;
if(a[i]<=x-1) cnt--;
}
return sum==x&&cnt>=0;
}
int main()
{
cin>>n>>l;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n,cmp);
int res=0;
int l=0,r=n;
while(l<r)
{
int mid = l+r+1>>1;
if(check(mid))
l=mid;
else r=mid-1;
}
cout<<l;
return 0;
}奶牛体操
为了提高健康水平，奶牛们开始进行体操训练了！
农夫约翰选定了他最喜爱的奶牛$ Bessie$ 来执教其他 $N$ 头奶牛，同时评估她们学习不同的体操技术的进度。
$K$ 次训练课的每一次，$Bessie$ 都会根据$N$ 头奶牛的表现给她们进行排名。
之后，她对这些排名的一致性产生了好奇。
称一对不同的奶牛是一致的，当且仅当其中一头奶牛在每次训练课中都表现得都比另一头要好。
请帮助 $Bessie$ 计算一致的奶牛的对数。
输入格式
输入的第一行包含两个正整数 $K$ 和 $N$。
以下 $K$ 行每行包含整数 $1…N$ 的某种排列，表示奶牛们的排名（奶牛们用编号 $1…N$ 进行区分）。
如果在某一行中 $A$ 出现在 $B $之前，表示奶牛$A$ 表现得比奶牛 $B$ 要好。
输出格式
输出一行，包含一致的奶牛的对数。
数据范围
$1≤K≤10$,
$1≤N≤20$
输入样例：
3 4
4 1 2 3
4 1 3 2
4 2 1 3输出样例：
4样例解释
一致的奶牛对为 $(1,4)、(2,4)、(3,4)、(1,3)$。
题解：
暴力枚举
用f[][]标记每节课符合要求（一头奶牛表现得都比另一头要好）的奶牛对数，最后循环遍历，找到$n$次课都满足，答案加$1$。
#include<bits/stdc++.h>
using namespace std;
int a[25];
int f[25][25];
int main()
{
int n,m;
cin >> n>>m;
for(int i=1;i<=n;i++){
for(int i=1;i<=m;i++)
cin>>a[i];
for(int i=1;i<m;i++)
for(int j=i+1;j<=m;j++)f[a[i]][a[j]]++;
}
int ans=0;
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
if(f[i][j]==n)ans++;
cout<<ans;
}
