寒假春季每日1题

1443. 拍照

农夫约翰在给他编号为 1…N 的 N 头奶牛排队拍照。
约翰一开始计划从左向右数第 i 个位置排编号为 ai 的奶牛，他在一张纸上写下了排列 a1,a2,…,aN。
不幸的是，这张纸刚刚被小偷偷走了！
幸好约翰仍然有机会恢复他之前写下的排列。
在这张纸被偷走之前，奶牛贝茜记录了序列 b1,b2,…,bN−1，对于每一个 1≤i基于贝茜的信息，帮助约翰恢复可以产生序列 b 的“字典序最小”的排列 a。
排列 x 字典序小于排列 y：如果对于某个 j，对于所有 i保证存在至少一个满足条件的 a。
输入格式
输入的第一行包含一个整数 N。
第二行包含 N−1 个空格分隔的整数 b1,b2,…,bN−1。
输出格式
输出一行，包含 N 个空格分隔的整数 a1,a2,…,aN。
数据范围
2≤N≤10^3
输入样例：
5
4 6 7 6
输出样例：
3 1 5 2 4
样例解释
a 能够产生 b，因为 3+1=4，1+5=6，5+2=7，2+4=6。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n;
bool st[N];
int a[N],b[N];
bool check(int x){
    memset(st, 0, sizeof st);
    a[0] = x;
    st[x] = true;
    for (int i = 1; i <= n-1; i ++ ){
        a[i] = b[i]-a[i-1];
        if(a[i]<1||a[i]>n){ // 超出范围
            return false;
        }
        if(st[a[i]]){ // 出现重复元素
            return false;
        }
        st[a[i]] = true;
    }
    for (int i = 0; i < n; i ++ ){
        cout << a[i]<<" ";
    }
    return true;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n-1; i ++ ){
        cin >> b[i];
    }
    for (int i = 1; i <= n; i ++ ){
        if(check(i)){
            break;
        }
    }
}

1672. 疯狂的科学家

我们将这两个字符串称为 A 和 B，其中 A 是 Farmer John 原先想要的品种字符组成的字符串，B 是他的奶牛们到达时组成的字符串。
Farmer John 并没有简单地检查重新排列 B 中的奶牛是否能得到 A，
Ben 发明了一台不同寻常的机器：奶牛品种转换机3000，能够选择任意奶牛组成的子串并反转她们的品种：在这个子串中的所有 H 变为 G，所有 G 变为 H。
Farmer John 想要求出将他当前的序列 B 变为他本来订购时想要的 A 需要使用这台机器的最小次数。
输入格式
输入的第一行包含 N，以下两行包含字符串 A 和 B。每个字符串均包含 N 个字符，字符均为 H 和 G 之一。
输出格式
输出将 B 变为 A 需要使用机器的最小次数。
数据范围
1≤N≤1000
输入样例：
7
GHHHGHH
HHGGGHH
输出样例：
2
样例解释
首先，FJ 可以仅改变第一个字符组成的子串，将 B 变为 GHGGGHH。
然后，他可以改变由第三和第四个字符组成的子串，得到 A。
当然，还存在其他有效的执行两次操作的方案。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
string s1;
string s2;
int n,last,res;
int main()
{
    cin >> n ;
    cin >> s1;
    cin >> s2;
    for (int i = 0; i < n; i ++ ){
        if(last==0){  // 上次没变换
            if(s1[i]!=s2[i]){  // 但这次不一样了，那就得变换
                res++;
                last = 1;
            }
        }else{  // 上次变换了
            if(s1[i]==s2[i]){
                last=0;
            }
        }
    }
    cout << res;
}

3346. 你知道你的ABC吗

Farmer John 的奶牛正在 mooZ 视频会议平台上举行每日集会。
她们发明了一个简单的数字游戏，为会议增添一些乐趣。
Elsie 有三个正整数 A、B 和 C (A≤B≤C）。
这些数字是保密的，她不会直接透露给她的姐妹 Bessie。
她告诉 Bessie 七个范围在 1…109 之间的整数（不一定各不相同），并宣称这是 A、B、C、A+B、B+C、C+A 和 A+B+C 的某种排列。
给定这七个整数，请帮助 Bessie 求出 A、B 和 C。
可以证明，答案是唯一的。
输入格式
输入一行，包含七个空格分隔的整数。
输出格式
输出 A、B 和 C，用空格分隔。
输入样例：
2 2 11 4 9 7 9
输出样例：
2 2 7

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10;
int a[N];
int res[N];
int main()
{
    for (int i = 0; i < 7; i ++ ){
        cin >> a[i];
    }
    sort(a,a+7);
    res[0] = a[0];
    res[1] = a[1];
    res[2] = a[6]-a[0]-a[1];
    for (int i = 0; i < 3; i ++ ){
        cout << res[i] <<" ";
    }
}

3358. 放养但没有完全放养

一个鲜为人知的事实是，奶牛拥有自己的文字：「牛文」。
牛文由 26 个字母 a 到 z 组成，但是当奶牛说牛文时，可能与我们所熟悉的 abcdefghijklmnopqrstuvwxyz 不同，她会按某种特定的顺序排列字母。
为了打发时间，奶牛 Bessie 在反复哼唱牛文字母歌，而 Farmer John 好奇她唱了多少遍。
给定一个小写字母组成的字符串，为 Farmer John 听到 Bessie 唱的字母，计算 Bessie 至少唱了几遍完整的牛文字母歌，使得 Farmer John 能够听到给定的字符串。
Farmer John 并不始终注意 Bessie 所唱的内容，所以他可能会漏听 Bessie 唱过的一些字母。
给定的字符串仅包含他记得他所听到的字母。
输入格式
输入的第一行包含 26 个小写字母，为a到z的牛文字母表顺序。
下一行包含一个小写字母组成的字符串，为 Farmer John 听到 Bessie 唱的字母。
输出格式
输出 Bessie 所唱的完整的牛文字母歌的最小次数。
输入样例：
abcdefghijklmnopqrstuvwxyz
mood
输出样例：
3
样例解释
在这个样例中，牛文字母表与日常的字母表的排列一致。
Bessie 至少唱了三遍牛文字母歌。
有可能 Bessie 只唱了三遍牛文字母歌，而 Farmer John 听到了以下被标记为大写的字母。
abcdefghijklMnOpqrstuvwxyz
abcdefghijklmnOpqrstuvwxyz
abcDefghijklmnopqrstuvwxyz

贪心，只要后一个字母出现的顺序在前一个前面，res++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
string str;
string s;
map<char,int>mat;
void init(){
    for (int i = 0; i < str.size(); i ++ ){
        mat[str[i]] = i;
    }
}
int main()
{
    cin >> str;
    cin >> s;
    init();
    int res=1;
    for (int i = 1; i < s.size(); i ++ ){
        if(mat[s[i]]<=mat[s[i-1]]){
            res++;
        }
    }
    cout << res;
}

1660. 社交距离 II

由于高传染性的牛传染病 COWVID-19 的爆发，Farmer John 非常担忧他的奶牛们的健康。
尽管他尽了最大努力使他的 N 头奶牛们践行“社交距离”，还是有许多奶牛不幸染上了疾病。
编号为 1…N 的奶牛们分别位于一条长直道路上的不同位置（相当于一维数轴），奶牛 i 位于位置 xi。
Farmer John 知道存在一个半径 R，任何与一头被感染的奶牛距离不超过 R 单位的奶牛也会被感染（然后会传染给与其距离 R 单位内的奶牛，以此类推）。
不幸的是，Farmer John 并不确切知道 R 的值。
他只知道他的哪些奶牛被感染了。
给定这个数据，求出起初感染疾病的奶牛的最小数量。
输入格式
输入的第一行包含 N。
以下 N 行每行用两个整数 x 和 s 描述一头奶牛，其中 x 为位置，s 为 0 表示健康的奶牛，1 表示染病的奶牛，并且所有可能因传播而染病的奶牛均已染病。
输出格式
输出在疾病开始传播之前已经得病的奶牛的最小数量。
数据范围
1≤N≤1000,
0≤x≤106
输入样例：
6
7 1
1 1
15 1
3 1
10 0
6 1
输出样例：
3
样例解释
在这个例子中，我们知道 R<3，否则位于位置 7 的奶牛会传染给位于位置 10 的奶牛。
所以，至少 3 头奶牛初始时已被感染：位于位置 1 和 3 的两头奶牛中的一头，位于位置 6 和 7 的两头奶牛中的一头，以及位于位置 15 的奶牛。

#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int n,res;
PII a[N];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ){
        cin >> a[i].x >> a[i].y;
    }
    sort(a+1,a+n+1);
    // 寻找半径
    int R = 1e6+10;
    for (int i = 1; i <= n; i ++ ){
        if(a[i].y==0){ // 找到没感染病的
            if(i-1>=1&&a[i-1].y==1){ // 左边感染
                R = min(R,a[i].x - a[i-1].x-1);
            }
            if(i+1<=n&&a[i+1].y==1){
                R = min(R,a[i+1].x -a[i].x -1);
            }
        }
    }
    // 计算最初最少感染量
    for (int i = 1; i <= n; i ++ ){  // 双指针算法
        if(a[i].y==1){
            int j = i+1;
            while(j<=n&&a[j].y==1&&a[j].x-a[j-1].x<=R){
                j++;
            }
            res++;
            i = j-1;
        }
    }
    cout << res;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int n;
PII q[N];
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> q[i].x >> q[i].y;
    sort(q, q + n);
    int R = 1e8;
    for (int i = 1; i < n; i ++ )
        if (q[i].y != q[i - 1].y) // 只要两个不相等，求最短距离
            R = min(R, q[i].x - q[i - 1].x);
    R -- ;
    int res = 0;
    for (int i = 0; i < n; i ++ )
        if (q[i].y)
        {
            int j = i + 1;
            while (j < n && q[j].y && q[j].x - q[j - 1].x <= R)
                j ++ ;
            res ++ ;
            i = j - 1;
        }
    cout << res << endl;
    return 0;
}

3347. 菊花链

每天，作为她绕农场行走的一部分，奶牛 Bessie 会经过她最喜爱的草地，其中种有 N 朵花（五颜六色的雏菊），编号为 1…N，排列成一行。
花 i 有 pi 朵花瓣。
作为一名崭露头角的摄影家，Bessie 决定给这些花拍些照片。
具体地说，对于每一对满足 1≤i≤j≤N 的花 (i,j)，Bessie 会给从花 i 到花 j 之间的所有花（包括 i 和 j）拍一张照。
后来 Bessie 查看这些照片时注意到有些照片里存在「平均」的花——一朵恰好有 P 朵花瓣的花，其中 P 等于照片中所有花的花瓣数量的平均值。
Bessie 的照片中有几张存在平均的花？
输入格式
输入的第一行包含 N。
第二行包含 N 个空格分隔的整数 p1…pN。
输出格式
输出存在平均的花的照片数量。
数据范围
1≤N≤100,
1≤pi≤1000
输入样例：
4
1 1 2 3
输出样例：
6
样例解释
每张仅包含一朵花的照片均会被计入答案（在这个样例中有 4 张）。
另外，在这个样例中 (i,j) 为 (1,2) 和 (2,4) 所对应的照片也存在平均的花

// 暴力枚举每一个区间
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int a[N];
int s[N];
int res;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ){
        cin >> a[i];
    }
    for (int i = 0; i < n; i ++ ){
        int s=0;
        for (int j = i; j < n; j ++ ){
            s+=a[j];
            int len = j-i+1;
            if(s%len==0){
                int avg = s/len;
                for (int k = i; k <= j; k ++ ){
                    if(a[k]==avg){
                        res++;
                        break;
                    }
                }
            }
        }
    }
    cout << res<<endl;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
using namespace std;
const int N = 110;
int n;
int a[N];
int s[N];
int res;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ){
        cin >> a[i];
    }
    for (int i = 0; i < n; i ++ ){
        int s=0;
        unordered_set<int>hash;  // 用set来hash
        for (int j = i; j < n; j ++ ){
            s+=a[j];
            hash.insert(a[j]);
            int len = j-i+1;
            if(s%len==0&&hash.count(s/len)){
                res++;
            }
        }
    }
    cout << res<<endl;
}

1726. 挤奶顺序

Farmer John 有 N 头奶牛，编号为 1…N。
他每天都要给他的奶牛们挤奶。
奶牛的社会结构非常复杂，其结构有两个关键特性。
首先，有 M 头奶牛的地位等级分明，按照地位越高越早挤奶的规则，这些奶牛的相对挤奶顺序是固定的。
此外，有 K 头奶牛的具体挤奶顺序也是固定的，比如，奶牛 4 必须在所有奶牛中的第二位挤奶。
幸运的是，Farmer John 总是能够以一种满足所有这些情况的顺序给他的奶牛们挤奶。
不幸的是，奶牛 1 最近生病了，所以 Farmer John 想要尽早给这头奶牛挤奶，使得她可以回到牛棚休息。
请帮助 Farmer John 求出奶牛 1 可以在挤奶顺序中出现的最早位置。
输入格式
第一行包含 N，M，K，表示 Farmer John 有 N 头奶牛，其中 M 头形成了社会阶层，K 头需要在挤奶顺序中处于一个特定的位置。
下一行包含 M 个不同的整数 mi。在这一行出现的奶牛必须以与她们在这行出现的顺序相同的顺序进行挤奶。
下面 K 行，每行包含两个整数 ci 和 pi，表示奶牛 ci 一定要在第 pi 位进行挤奶。
输入数据保证：在这些限制之下，Farmer John 能够建立一个符合要求的挤奶顺序。
输出格式
输出奶牛 1 可以在挤奶顺序中出现的最早位置。
数据范围
2≤N≤100,
1≤M,K1≤mi,ci,pi≤N
输入样例：
6 3 2
4 5 6
5 3
3 1
输出样例：
4
样例解释
在这个例子中，Farmer John 有六头奶牛，其中奶牛 1 生病了。
他的挤奶顺序应该为奶牛 4 在奶牛 5 之前，奶牛 5 在奶牛 6 之前。
此外，Farmer John 必须要第一个给奶牛 3 挤奶，第三个给奶牛 5 挤奶。
FJ必须第一个给奶牛 3 挤奶，由于奶牛 4 必须要在奶牛 5 之前，奶牛 4 一定是第二个挤奶的，然后奶牛 5 第三个。
于是，奶牛 1 最早在挤奶顺序中出现的位置是第四个。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n,m,k;
bool st[N];
int q[N],p[N];  // q 是相对位置，p是固定了绝对位置
/*
1. 1号牛在绝对位置上
2. 1号牛在相对位置上
3. 1号牛没限制
*/
int main()
{
    cin >> n >> m >> k;
    bool flag;
    for (int i = 1; i <= m; i ++ ){
        cin >> q[i];
        if(q[i]==1){  // 第2种情况
            flag = true;
        }
    }
    for (int i = 1; i <= k; i ++ ){
        int a,posi;  // 第a头牛必须摆在posi位置上
        cin >> a >> posi;
        p[a] = posi;
        st[posi] = true;
        if(a==1){    // 第1种情况
            cout << posi <<endl;
            return 0;
        }
    }
    if(flag){  // 相对位置定了
        for (int i = 1,j=1; i <= m; i ++ ){
            while(st[j]){
                j++;
            }
            int u = q[i];
            if(p[u]){     // 第u头牛绝对位置定了
                j = p[u];
                j++;
            }else{  // 没固定
                if(u==1){
                    cout << j <<endl;
                    return 0;
                }
                st[j] = true;
                j++;
            }
        }
    }else{  // 1号牛位置没限制
        for (int i = m,j = n; i; i -- ){
            while(st[j]){
                j--;
            }
            int u = q[i];
            if(p[u]){
                j = p[u];
                j--;
            }else{
                st[j] = true;
                j--;
            }
        }
        for (int i = 1; i <= n; i ++ ){
            if(!st[i]){
                cout << i <<endl;
                return 0;
            }
        }
    }
}

4377. 农田灌溉

农夫约翰有 n 片连续的农田，编号依次为 1∼n。
其中有 k 片农田中装有洒水器。
装有洒水器的农田的编号从小到大依次为 x1,x2,…,xk。
在某个炎热的中午，约翰觉得是时候给他的所有农田浇水了。
每个洒水器在打开以后，向两侧方向洒水，并且随着开启时间延长，有效覆盖距离也不断增长。
具体来说，我们将第 xi 片农田中的洒水器打开，经过 1 秒后，第 xi 片农田被其覆盖，经过 2 秒后，第 [xi−1,xi+1] 片农田被其覆盖，经过 j 秒后，第 [xi−(j−1),xi+(j−1)] 片农田被其覆盖。
注意，每个洒水器的有效覆盖距离在每经过整数秒后，才会有所增长。
例如，经过 2.5 秒后，被第 xi 片农田中的洒水器覆盖的农田仍是第 [xi−1,xi+1] 片农田，而不是第 [xi−1.5,xi+1.5] 片农田。
现在，约翰将所有洒水器同时打开，请问经过多少秒后，所有农田均被灌溉。
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
每组数据第一行包含两个整数 n,k。
第二行包含 k 个整数 x1,x2,…,xk。
输出格式
每组数据输出一行答案。
数据范围
前三个测试点满足 1≤n≤5,
所有测试点满足 1≤T≤200，1≤n≤200，1≤k≤n，1≤xi≤n，xi−1输入样例：
3
5 1
3
3 3
1 2 3
4 1
1
输出样例：
3
1
4

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210;
int a[N];
int main()
{
    int T;
    cin >> T;
    while (T -- ){
        int n,k;
        cin >> n >> k;
        for (int i = 1; i <= k; i ++ ){
            cin >> a[i];
        }
        int l = a[1],mid=0,r =n-a[k]+1 ; // 左边，右边，中间
        for (int i = 2; i <= k; i ++ ){
            mid = max(a[i]-a[i-1]-1,mid);
        }
        if(mid%2==1){
            mid = mid/2+2;
        }else{
            mid = mid/2+1;
        }
        cout << max(l,max(mid,r)) <<endl;
    }
}

1715. 桶列表

Farmer John 正在考虑改变他给奶牛分配牛奶桶的方式。
他希望使用尽量少的牛奶桶，请帮助他！
Farmer John 有 N 头奶牛，编号为 1…N。
第 i 头奶牛需要从时刻 si 到时刻 ti 之间挤奶，并且挤奶过程中需要用到 bi 个桶。
多头奶牛可能在同一时刻都在挤奶；每个桶在每个时刻只能供一头奶牛使用。
也就是说，第 i 头奶牛在时刻 si 到时刻 ti 之间挤奶时，如果用到了某个桶，则该桶在这段时间不能被其他奶牛使用。
当然，这个桶在这段时间之外可以被其他奶牛所使用。
为了简化他的工作，FJ 保证在任一时刻，至多只有一头奶牛开始或是结束挤奶（也就是说，所有的 si 和 ti 各不相同）。
FJ 有一个储藏室，里面有编号为 1、2、3、…… 的桶。
在他的挤奶策略中，当某一头奶牛（比如说，奶牛 i）开始挤奶（在时刻 si），FJ 就跑到储藏室取出编号最小的 bi 个桶分配给第 i 头奶牛用来挤奶。
请求出 FJ 需要在储藏室中存放多少个桶才能使得他能够顺利地给所有奶牛挤奶。
输入格式
输入的第一行包含 N。
以下 N 行，每行描述了一头奶牛，包含三个空格分隔的数 si,ti,bi。
其中 si 和 ti 均为 1…1000 之间的整数，bi 为 1…10 之间的整数。
输出格式
输出一个整数，为 FJ 需要的桶的数量。
数据范围
1≤N≤100
输入样例：
3
4 10 1
8 13 3
2 6 2
输出样例：
4
样例解释
在这个例子中，FJ 需要 4 个桶：他用桶 1 和桶 2 来给奶牛 3 挤奶（从时刻 2 开始）。
他用桶 3 给奶牛 1 挤奶（从时刻 4 开始）。
当奶牛 2 在时刻 8 开始挤奶时，桶 1 和桶 2 可以再次利用，然而桶 3 不可以，所以他会使用桶 1、桶 2 和桶 4。

假设一开始桶数是num=0

1. 先对挤奶按开始时间排序
2. 挤奶之前先判断，之前有没已经挤完奶的，如果有的话就让num+=那次挤奶需要的桶
3. num-=这次挤奶需要的桶
4. 对num求最小值，最后取绝对值即可

即,num存的是桶的相对量，是差分

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#define x first
#define y second
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
int n;
struct Node1{
    int st;  // 挤奶开始时刻
    int ed;  // 结束时刻
    int num; // 需要桶的数量
    bool operator<(const Node1 node)const{
        return st<node.st;
    }
}g[N];
priority_queue<PII,vector<PII>,greater<PII>>heap;
int res,num;
void work(int cur){
    while(!heap.empty()&&heap.top().x<cur){
        auto t = heap.top();
        heap.pop();
        num+=t.y;
    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ){
        cin >> g[i].st >> g[i].ed >> g[i].num;
    }
    sort(g,g+n);
    for (int i = 0; i < n; i ++ ){
        work(g[i].st);
        num-=g[i].num;
        res = min(num,res);
        heap.push({g[i].ed,g[i].num});
    }
    cout << abs(res);
}

1696. 困牛排序

Farmer John 正在尝试将他的 N 头奶牛，方便起见编号为 1…N，在她们前往牧草地吃早餐之前排好顺序。
当前，这些奶牛以 p1,p2,p3,…,pN 的顺序排成一行，Farmer John 站在奶牛 p1 前面。
他想要重新排列这些奶牛，使得她们的顺序变为 1,2,3,…,N，奶牛 1 在 Farmer John 旁边。
今天奶牛们有些困倦，所以任何时刻都只有直接面向 Farmer John 的奶牛会注意听 Farmer John 的指令。
每一次他可以命令这头奶牛沿着队伍向后移动 k 步，k 可以是范围 1…N−1 中的任意数。
她经过的 k 头奶牛会向前移动，腾出空间使得她能够插入到队伍中这些奶牛之后的位置。
例如，假设 N=4，奶牛们开始时是这样的顺序：
FJ: 4, 3, 2, 1
唯一注意 FJ 指令的奶牛是奶牛 4。
当他命令她向队伍后移动 2 步之后，队伍的顺序会变成：
FJ: 3, 2, 4, 1
现在唯一注意 FJ 指令的奶牛是奶牛 3，所以第二次他可以给奶牛 3 下命令，如此进行直到奶牛们排好了顺序。
Farmer John 急欲完成排序，这样他就可以回到他的农舍里享用他自己的早餐了。
请帮助他求出将奶牛们排好顺序所需要的最小操作次数。
输入格式
输入的第一行包含 N。
第二行包含 N 个空格分隔的整数，p1,p2,p3,…,pN，表示奶牛们的起始顺序。
输出格式
输出一个整数，为 Farmer John 采用最佳策略可以将这 N 头奶牛排好顺序所需要的操作次数。
输入样例：
4
1 2 4 3
输出样例：
3

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int a[N];
int n;
int main()
{
    cin >> n ;
    for (int i = 1; i <= n; i ++ ){
        cin >> a[i];
    }
    for (int i = n-1; i ; i -- ){
        if(a[i]>a[i+1]){
            cout << i <<endl;
            return 0;
        }
    }
    cout << 0 <<endl;
}

1684. 大型植被恢复

长时间的干旱使得 Farmer John 的 N 块草地上牧草匮乏。
随着雨季即将到来，现在应当是重新种植的时候了。
在 Farmr John 的储物棚里有四个桶，每个桶里装着一种不同的草种。
他想要在每块草地上播种其中一种草。
作为一名奶农，Farmer John 想要确保他的每头奶牛都能得到丰富的食谱。
他的 M 头奶牛每一头都有两块喜爱的草地，他想要确保这两块草地种植不同种类的草，从而每头奶牛都可以选择两种草。
已知每块草地最多被 3 头奶牛喜爱。
请帮助 Farmer John 选择每块草地所种的草的种类，使得所有奶牛的营养需求都得到满足。
输入格式
输入的第一行包含 N 和 M。
以下 M 行，每行包含两个范围为 1…N 的整数，为 Farmer John 的一头奶牛喜欢的两块草地。
输出格式
输出一个 N 位数，每一位均为 1…4 之一，表示每一块草地上所种的草的种类。
第一位对应草地 1 的草的种类，第二位对应草地 2，以此类推。
如果有多种可行的解，只需输出所有解中最小的 N 位数。
数据范围
2≤N≤100
1≤M≤150
输入样例：
5 6
4 1
4 2
4 3
2 5
1 2
1 5
输出样例：
12133

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 110;
int n,m;
vector<int>h[N];
bool st[N][5];
void dfs(int id){ // 草地编号
    if(id>n){
        return ;
    }
    for (int i = 1; i <= 4; i ++ ){
        if(!st[id][i]){
            cout << i;
            // 与其相连的其他草地都不能种第i种草了
            for (int j = 0; j < h[id].size(); j ++ ){
                int u = h[id][j];
                st[u][i] = true;
            }
            dfs(id+1);
            return ;
        }
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i ++ ){
        int a,b;
        cin >> a >> b;
        h[a].push_back(b);
        h[b].push_back(a);
    }
    dfs(1);
}

1471. 牛奶工厂

牛奶生意正红红火火！
农夫约翰的牛奶加工厂内有 N 个加工站，编号为 1…N，以及 N−1 条通道，每条连接某两个加工站。（通道建设很昂贵，所以约翰选择使用了最小数量的通道，使得从每个加工站出发都可以到达所有其他加工站）。
为了创新和提升效率，约翰在每条通道上安装了传送带。
不幸的是，当他意识到传送带是单向的已经太晚了，现在每条通道只能沿着一个方向通行了！
所以现在的情况不再是从每个加工站出发都能够到达其他加工站了。
然而，约翰认为事情可能还不算完全失败，只要至少还存在一个加工站 i 满足从其他每个加工站出发都可以到达加工站 i。
注意从其他任意一个加工站 j 前往加工站 i 可能会经过 i 和 j 之间的一些中间站点。
请帮助约翰求出是否存在这样的加工站 i。
输入格式
输入的第一行包含一个整数 N，为加工站的数量。
以下 N−1行每行包含两个空格分隔的整数 ai 和 bi，满足 1≤ai,bi≤N 以及 ai≠bi。
这表示有一条从加工站 ai 向加工站 bi 移动的传送带，仅允许沿从 ai 到 bi 的方向移动。
输出格式
如果存在加工站 i 满足可以从任意其他加工站出发都可以到达加工站 i，输出最小的满足条件的 i。
否则，输出 −1。
数据范围
1≤N≤100
输入样例：
3
1 2
3 2
输出样例：
2

// O(n^3) floyd算法
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
bool g[N][N];
int n;
int main()
{
    cin >> n;
    // 这个一定要初始化，不然下面判断从i出发能不能走到j的话
    // i出发走不到j，就出问题了
    for (int i = 1; i <= n; i ++ ){
        g[i][i] = true;
    }
    for (int i = 0; i < n-1; i ++ ){
        int a,b;
        cin >> a >> b;
        g[a][b] = true;
    }
    for (int k = 1; k <= n; k ++ ){
        for (int i = 1; i <= n; i ++ ){
            for (int j = 1; j <= n; j ++ ){
                if(g[i][k]&&g[k][j]){
                    g[i][j] = true;
                }
            }
        }
    }
    for (int i = 1; i <= n; i ++ ){
        bool flag = true;
        for (int j = 1; j <= n; j ++ ){
            if(!g[j][i]){
                flag = false;
                break;
            }
        }
        if(flag){
            cout << i <<endl;
            return 0;
        }
    }
    puts("-1");
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int d[N];  // 记录i点的出度
int n;
int main()
{
    cin >> n;
    for (int i = 0; i < n-1; i ++ ){
        int a,b;
        cin >> a >> b;
        d[a]++;
    }
    int cnt=0,res;
    for (int i = 1; i <= n; i ++ ){
        if(!d[i]){
            res = i;
            cnt++;
        }
    }
    if(cnt==1){
        cout << res <<endl;
    }else{
        puts("-1");        
    }
}

#include<iostream>
using namespace std;
int n,x,y,cnt,ans;
int c[105];//记录出度的数量
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        c[x]++;//x点多了一条出度（说实话这里改成bool数组也可以，还省空间）
    }
    for(int i=1;i<=n;i++){
        if(!c[i]){//如果出度为0
            cnt++;//记录一下，万一有多个就不能直接输出
            ans=i;//如果只有这一个点出度为0的话ans的值就不会再变了
        }
    }
    if(cnt==1) printf("%d",ans);//cnt的值为1时才合法
    else printf("-1");
    return 0;
}

1460. 我在哪？

农夫约翰出门沿着马路散步，但是他现在发现自己可能迷路了！
沿路有一排共 N 个农场。
不幸的是农场并没有编号，这使得约翰难以分辨他在这条路上所处的位置。
然而，每个农场都沿路设有一个彩色的邮箱，所以约翰希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。
每个邮箱的颜色用 A..Z 之间的一个字母来指定，所以沿着道路的 N 个邮箱的序列可以用一个长为 N 的由字母 A..Z 组成的字符串来表示。
某些邮箱可能会有相同的颜色。
约翰想要知道最小的 K 的值，使得他查看任意连续 K 个邮箱序列，他都可以唯一确定这一序列在道路上的位置。
例如，假设沿路的邮箱序列为 ABCDABC 。
约翰不能令 K=3，因为如果他看到了 ABC，则沿路有两个这一连续颜色序列可能所在的位置。
最小可行的 K 的值为 K=4，因为如果他查看任意连续 4 个邮箱，那么可得到的连续颜色序列可以唯一确定他在道路上的位置。
输入格式
输入的第一行包含 N，第二行包含一个由 N 个字符组成的字符串，每个字符均在 A..Z 之内。
输出格式
输出一行，包含一个整数，为可以解决农夫约翰的问题的最小 K 值。
数据范围
1≤N≤100
输入样例：
7
ABCDABC
输出样例：
4

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
typedef unsigned long long ULL;
using namespace std;
const int N = 110;
int n,P = 131;
string s;
ULL h[N],p[N];
ULL get(int l, int r)  // 计算子串 str[l ~ r] 的哈希值
{
    return h[r] - h[l - 1] * p[r - l + 1];
}
bool check(int mid){
    // 看看在子串长度为mid的情况下，能不能满足没有重复子串
    map<ULL,bool>mat;
    for (int i = 1; i+mid-1 <= n; i ++ ){
        ULL t = get(i,i+mid-1);
        if(mat[t]){
            return false;
        }
        mat[t] = true;
    }
    return true;
}
int main()
{
    cin >> n ;
    cin >> s;
    // 字符串哈希
    s = " "+s;
    p[0] = 1;
    for (int i = 1; i <= n; i ++ ){
        p[i] = p[i-1]*P;
        h[i] = h[i-1]*P + s[i];
    }
    // 二分答案
    int l=1,r=100;
    while(l<r){
        int mid = l + r >>1;
        if(check(mid)){
            r = mid;
        }else{
            l = mid+1;
        }
    }
    cout << l;
}

1789. 牛为什么过马路 II

农夫约翰的农场布局十分奇特，一条大型的环形道路将奶牛吃草的田地围了起来。
每天早晨，奶牛们穿过这条道路，进入到田地吃草；每天晚上，奶牛们穿过这条道路，离开田地，返回牛棚休息。
众所周知，奶牛是有习性的动物，每头奶牛每天通过道路的方式都相同。
每头奶牛每天固定地从道路的某一位置进入田地，从道路的另一不同位置离开田地。
所有奶牛的所有进出位置之间互不相同。
约翰共有 26 头奶牛，依次命名为 A∼Z。
因此，道路上共有 52 个不同的进出位置。
约翰沿着环形道路按顺时针方向扫描了每个位置，并记录了每个位置处经过的奶牛的名字，最终形成了一个包含 52 个字母的序列，A∼Z 中的每个字母恰好出现两次。
他并没有记录哪些位置是入口，哪些位置是出口。
看着地图上记录的这些位置，约翰想要知道一天当中，有多少对奶牛之间的从入口穿过田地到达出口的路径可能会存在交叉。
如果奶牛 A 从入口穿过田地到达出口的路径必须穿过奶牛 B 从入口穿过田地到达出口的路径，那么称这对牛 (A,B) 是“交叉”对。
请帮助约翰计算“交叉”对（不考虑顺序，即 (A,B) 与 (B,A) 视为同一对 ）的总数。
输入格式
共一行，包含一个长度为 52 的只包含大写字母的字符串，其中每个字母恰好出现两次。
输出格式
输出交叉对的总数。
输入样例：
ABCCABDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ
输出样例：
1
样例解释
在此样例中，只有 A 和 B 一对交叉对。

1. 记录每个元素起始的位置
2. 枚举每一对（a,b）
3. 如果a的起始和结束中间，b只出现了一次，那么存在交叉

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 27;
string s;
vector<int>h[N]; // 记录下每个元素 起始和结束的位置
int main()
{
    cin >> s;
    for (int i = 0; i < s.size(); i ++ ){
        int j = s[i]-'A';
        h[j].push_back(i);
    }
    int res=0;
    // 枚举每一对
    for (int i = 0; i < 26; i ++ ){
        int x = h[i][0], y = h[i][1];
        for (int j = i+1; j < 26; j ++ ){
            int cnt=0;
            for(auto posi:h[j]){
                if(posi>x&&posi<y){
                    cnt++;
                }
            }
            if(cnt&1){
                res++;
            }
        }
    }
    cout << res;
}

1. 牛的基因组学

农夫约翰拥有 N 头有斑点的牛和 N 头没有斑点的牛。
他刚刚完成了牛遗传学课程，他确信奶牛上的斑点是由牛基因组突变引起的。
农夫约翰花了大价钱对他的奶牛的基因组进行了测序。
每个基因组都是一个由四个字符 A,C,G,T 构成的长度为 M 的字符串。
当他统计得到的奶牛的基因组序列时，可以得到一个如下所示的表：（此时，N=3）
位置 : 1 2 3 4 5 6 7 … M
斑点牛 1: A A T C C C A … T
斑点牛 2: G A T T G C A … A
斑点牛 3: G G T C G C A … A
普通牛 1: A C T C C C A … G
普通牛 2: A C T C G C A … T
普通牛 3: A C T T C C A … T
通过仔细观察该表，他发现通过位置 2 的字符足以判断奶牛是否存在斑点。
也就是说，仅通过查看这个位置上的字符，农夫约翰就可以判断他的哪些奶牛有斑点，哪些没有斑点。（在这里，A 和 G 表示有斑点，C 表示无斑点，T 无关紧要，因为没有任何一头牛的第二个位置上的字符是 T）
位置 1 上的字符不足以判断奶牛是否存在斑点，因为 A 既可以表示有斑点也可以表示无斑点。
给定约翰的奶牛的基因组序列列表，请你计算可以单独用来判断奶牛是否存在斑点的位置的数量。
输入格式
第一行包含两个整数 N 和 M。
接下来 N 行，每行包含一个长度为 M 的字符串，用来描述斑点牛的基因组序列。
再接下来 N 行，每行包含一个长度为 M 的字符串，用来描述普通牛的基因组序列。
输出格式
输出可以单独用来判断奶牛是否存在斑点的位置的数量。
数据范围
1≤N,M≤100
输入样例：
3 8
AATCCCAT
GATTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT
输出样例：
1

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n,m;
string a[N],b[N];
bool st[5];
int get(char x){
    if(x == 'A'){
        return 0;
    }
    if(x == 'C'){
        return 1;
    }
    if(x == 'G'){
        return 2;
    }
    return 3;
}
int main(){
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ){
        cin >> a[i];
    }
    for (int i = 0; i < n; i ++ ){
        cin >> b[i];
    }
    int res=0;
    for (int i = 0; i < m; i ++ ){  // 第m位
        memset(st, 0, sizeof st);
        for (int j = 0; j < n; j ++ ){  // 判断a的第i位，并在st数组种标注
            int k = get(a[j][i]);
            st[k] = true;
        }
        bool flag = true;
        for (int j = 0; j < n; j ++ ){ // 如果a种标注的没出现在了b中，则res++
            int k = get(b[j][i]);
            if(st[k]){
                flag = false;
                break;
            }
        }        
        if(flag){
            res++;
        }
    }
    cout << res;
}

1762. 牛的洗牌

农夫约翰坚信快乐的奶牛会产出更多的牛奶，因此他在谷仓中安装了一个巨大的迪斯科球，并计划教他的奶牛跳舞！
在查阅了一些牛的流行舞蹈后，约翰决定教他的奶牛“洗牌舞”。
洗牌舞是由他的 N 只奶牛按一定顺序排成一行，然后连续执行三次“洗牌”，每次“洗牌”都可能会使奶牛重新排序。
为了让奶牛们更容易找到自己所处的位置，约翰用数字 1∼N 对一行中奶牛所在的位置进行了标记，一行中第一头奶牛处于位置 1，第二头奶牛处于位置 2，以此类推，直到位置 N。
每次“洗牌”用 N 个数字 a1,a2,…,aN 来描述，处于位置 i 的奶牛在一次“洗牌”过后，需要移动至位置 ai（因此，每个 ai 在 1…N 范围内）。
幸运的是，所有 ai 都是互不相同的，因此，不会存在多头奶牛在洗牌结束后移动到同一个位置的情况。
约翰的每头奶牛都有一个属于自己的唯一 7 位整数 ID （不含前导 0）。
给定你三轮“洗牌”过后的奶牛排列顺序，请你求出奶牛们的初始排列顺序。
输入格式
第一行包含整数 N。
第二行包含 N 个整数，表示 a1,a2,…,aN。
第三行包含了 N 头奶牛三轮“洗牌”过后的排列顺序，每头奶牛都用其 ID 指代。
输出格式
共 N 行，按照 N 头奶牛的初始排列顺序，每行输出一头奶牛的 ID。
数据范围
1≤N≤100,
1≤ai≤N
输入样例：
5
1 3 4 5 2
1234567 2222222 3333333 4444444 5555555
输出样例：
1234567
5555555
2222222
3333333
4444444

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int t[5][N];
int a[N];
string id[N];
int n;
int main()
{
    cin >> n;
    for (int j = 1; j <= n; j ++ ){
        cin >> a[j];
        t[0][j] = j;
    }
    for (int i = 1; i <= n; i ++ ){
        cin >> id[i];
    }
    for (int i = 1; i <= 3; i ++ ){
        for (int j = 1; j <= n; j ++ ){
            t[i][j] = t[i-1][a[j]]; // 当前第j个元素的值，等于上一次a[i]处的值
        }
    }
    for (int j = 1; j <= n; j ++ ){
        int index = t[3][j];
        cout << id[index]<<endl;
    }
}

1750. 救生员

农夫约翰为他的牛开设了一个游泳池，他认为这将帮助它们放松并产出更多的奶。
为了确保安全，他雇佣了 N 头奶牛作为救生员，每头奶牛的工作班次都是一段连续的时间。
为了简单起见，游泳池每天的开放时间从时刻 0 到时刻 1000。
每个奶牛的工作班次都可以用两个整数来描述，它们分别表示该奶牛工作班次的开始时刻和结束时刻。
例如，从时刻 t=4 开始工作并在时刻 t=7 结束工作的救生员，它的工作时间为三个时间单位（请注意，时间“段”两端的端点是时间轴上的“点”）。
不幸的是，由于资金紧张问题，约翰不得不解雇一头奶牛。
请问通过合理裁员，剩余救生员的工作班次仍然可以覆盖的最大时间有多长？
一个时间间隔内如果存在至少一名救生员当值，那么这个时间间隔就认为是被覆盖的。
输入格式
第一行包含整数 N。
接下来 N 行，每行描述一个救生员的工作班次，包含两个整数，表示一个救生员的开始工作时刻和结束工作时刻。
所有时刻各不相同，不同救生员的工作班次可能有覆盖。
输出格式
输出一个整数，表示解雇掉一头奶牛后，剩余救生员的工作班次仍然可以覆盖的最长时间。
数据范围
1≤N≤100
0≤开始时刻≤结束时刻≤1000
输入样例：
3
5 9
1 4
3 7
输出样例：
7

#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int n;
PII a[N];
int res;
int main()
{
    cin >> n ;
    for (int i = 0; i < n; i ++ ){
        cin >> a[i].x >> a[i].y;
    }
    sort(a,a+n);
    for (int i = 0; i < n; i ++ ){  // 枚举解雇第i头牛
        int len=0;
        int r=0; // 目前已经计算到r位置
        for (int j = 0; j < n; j ++ ){
            if(i==j){
                continue;
            }
            if(a[j].x>=r){
                len+=a[j].y-a[j].x;
                r = a[j].y;
            }else if(a[j].y>r){
                len+=a[j].y-r;
                r = a[j].y;
            }
        }
        res = max(len,res);
    }
    cout << res;
}

1738. 蹄球

为了准备即将到来的蹄球锦标赛，Farmer John 正在训练他的 N 头奶牛（方便起见，编号为 1…N）进行传球。
这些奶牛在牛棚一侧沿直线排列，第 i 号奶牛位于距离牛棚 xi 的地方。
每头奶牛都在不同的位置上。
在训练开始的时候，Farmer John 会将若干个球传给不同的奶牛。
当第 i 号奶牛接到球时，无论是从 Farmer John 或是从另一头奶牛传来的，她会将球传给最近的奶牛（如果有多头奶牛与她距离相同，她会将球传给这些奶牛中最左边的那头奶牛。）。
为了使所有奶牛都有机会练习到传球，Farmer John 想要确保每头奶牛都持球至少一次。
帮助他求出为了达到这一目的他开始时至少要传出的球的数量。
假设他在开始的时候能将球传给最适当的一组奶牛。
输入格式
输入的第一行包含 N。
第二行包含 N 个用空格分隔的整数，其中第 i 个整数为 xi。
输出格式
输出 Farmer John 开始的时候最少需要传出的球的数量，使得所有奶牛至少持球一次。
数据范围
1≤N≤100,
1≤xi≤1000
输入样例：
5
7 1 3 11 4
输出样例：
2
样例解释
在上面的样例中，Farmer John 应该将球传给位于 x=1 的奶牛和位于 x=11 的奶牛。
位于 x=1 的奶牛会将她的球传给位于 x=3 的奶牛，在此之后这个球会在位于 x=3 的奶牛和位于 x=4 的奶牛之间来回传递。
位于 x=11 的奶牛会将她的球传给位于 x=7 的奶牛，然后球会被传给位于 x=4 的奶牛，在此之后这个球也会在位于 x=3 的奶牛和位于 x=4 的奶牛之间来回传递。
这样的话，所有的奶牛都会至少一次接到球（可能从 Farmer John，也可能从另一头奶牛）。
可以看出，不存在这样一头奶牛，Farmer John 可以将球传给她之后所有奶牛最终都能被传到球。

1. 对于第二种情况来说，每个点都会被计算一次，但是只能算1，所以在代码中
   1. 对于第一种情况找到入度为0的点 然后res+=2
   2. 在第二种情况中 每一个点加1
   3. 最后res/2即是答案

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 110,INF = 1e7;
int a[N];
int p[N],d[N];
int n,res;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ){
        cin >> a[i];
    }
    sort(a+1,a+n+1);
    a[0] = -INF,a[n+1]=INF;
    // 一个点要么可以传给左边，要么可以传给右边
    for (int i = 1; i <= n; i ++ ){
        if(a[i]-a[i-1]<=a[i+1]-a[i]){
            p[i] = i-1;
            d[i-1]++;
        }else{
            p[i] = i+1;
            d[i+1]++;
        }
    }
    // 统计那两种情况
    for (int i = 1; i <= n; i ++ ){
        if(!d[i]){
            res+=2;
        }else if(p[p[i]] == i&& d[i]==1 && d[p[i]]==1){
            res++;
        }
    }
    cout << res/2;
}

1875. 贝茜的报复

农夫约翰和奶牛贝茜喜欢在业余时间互相出数学题。
约翰给贝茜出了一道相当难的问题，导致她没能解决。
现在，她希望通过给约翰出一道有挑战性的难题来报复他。
贝茜给了约翰一个表达式 (B+E+S+S+I+E)(G+O+E+S)(M+O+O)，其中包含七个变量 B,E,S,I,G,O,M（O 是变量，不是零）。
对于每个变量，她给约翰一个列表，表中包含该变量可采用的最多 20 个整数值。
她要求约翰计算，共有多少种给变量赋值的方法可以使得表达式的计算结果为偶数。
输入格式
第一行包含一个整数 N。
接下来 N 行，每行包含一个变量和该变量的一个可能值。
每个变量至少出现 1 次，最多出现 20 次。
同一变量不会重复列出同一可能值。
输出格式
输出可以使得表达式的计算结果是偶数的给变量赋值的方法总数。
数据范围
7≤N≤140,
所有变量的可能取值范围 [−300,300]
本题答案不会超出int范围。
输入样例：
10
B 2
E 5
S 7
I 10
O 16
M 19
B 3
G 1
I 9
M 2
输出样例：
6
样例解释
共有 6 种可能的赋值方式：
(B,E,S,I,G,O,M) = (2, 5, 7, 10, 1, 16, 19) -> 53,244
= (2, 5, 7, 10, 1, 16, 2 ) -> 35,496
= (2, 5, 7, 9, 1, 16, 2 ) -> 34,510
= (3, 5, 7, 10, 1, 16, 2 ) -> 36,482
= (3, 5, 7, 9, 1, 16, 19) -> 53,244
= (3, 5, 7, 9, 1, 16, 2 ) -> 35,496
注意，(2, 5, 7, 10, 1, 16, 19) 和 (3, 5, 7, 9, 1, 16, 19)，虽然计算结果相同，但是赋值方式不同，所以要分别计数。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
int n, res;
int main() {
    cin >> n;
    unordered_map<char, int> cnt[2];
    for (int i = 0; i < n; i++) {
        char c;
        int x;
        cin >> c >> x;
        cnt[abs(x) % 2][c]++;
    }
    char str[10] = "BESIGOM";
    for (int i = 0; i < 1 << 7; i++) {  // 枚举每一个字母是偶数或者奇数的情况
        unordered_map<char, int> v;
        for (int j = 0; j < 7; j++) {
            int u = i >> j & 1;
            v[str[j]] = u;   // 第j个字符是奇数还是偶数,0的话是偶数，1的话是奇数
        }
        if (((v['B'] + v['I']) * (v['G'] + v['O'] + v['E'] + v['S']) * v['M']) % 2 == 0) {
            int sum = 1;
            for (int j = 0; j < 7; j++) {
                sum *= cnt[i >> j & 1][str[j]];
            }
            res += sum;
        }
    }
    cout << res;
}

1459. 奶牛体操

为了提高健康水平，奶牛们开始进行体操训练了！
农夫约翰选定了他最喜爱的奶牛 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

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 22;
int st[N][N];  // st[i][j]  i->j出现的次数
int n,m;
int a[N],res;
int main()
{
    int n,m;
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ){
        for (int j = 0; j < m; j ++ ){
            cin >> a[j];
        }
        for (int j = 0; j < m-1; j ++ ){
            for (int k = j+1; k < m; k ++ ){
                st[ a[j] ][ a[k] ]++;
            }
        }
    }
    for (int i = 1; i <= m; i ++ ){
        for (int j = 1; j <= m; j ++ ){
            if(st[i][j]==n){
                res++;
            }
        }
    }
    cout << res;
}