2022春季每日一题笔记（四）

第四周

T1—1812. 方形牧场

农夫约翰决定翻修他的农场以简化其几何形状。
以前，他的牛在两个栅栏围起来的长方形牧场上吃草。
现在，约翰想要用栅栏修建一个新的正方形牧场。
正方形牧场需要覆盖之前两个长方形牧场所包围的全部区域。
请你确定，新修建的正方形牧场的面积最小是多少。
正方形牧场的边应与 x 轴和 y 轴平行。

输入格式
第一行包含四个整数 x1,y1,x2,y2，表示第一个长方形牧场的左下角坐标 (x1,y1) 和右上角坐标 (x2,y2)。
第二行同样包含四个整数 x1,y1,x2,y2，表示第二个长方形牧场的左下角坐标 (x1,y1) 和右上角坐标 (x2,y2)。
两个牧场之间不会发生重叠或接触。

输出格式
输出能够覆盖之前两个长方形牧场所包围的全部区域的正方形牧场的最小面积。

数据范围
0≤x1<x2≤10,
0≤y1<y2≤10
输入样例：
6 6 8 8
1 8 4 9
输出样例：
49
样例解释
在此样例中，想要将两个原始长方形覆盖，一种可行方法是建立左下角坐标为 (1,6) 右上角坐标为 (8,13) 的边长为 7 的正方形。

水题。

#include <iostream>
#include <algorithm>
using namespace std;
int x[2][2],y[2][2];

int main(){
    int Mx = -1,mx = 11,My = -1,my = 11;
    for (int i = 0;i < 2;i ++){
        cin >> x[i][0] >> y[i][0] >> x[i][1] >> y[i][1];
        Mx = max(Mx,max(x[i][0],x[i][1]));
        My = max(My,max(y[i][0],y[i][1]));
        mx = min(mx,min(x[i][0],x[i][1]));
        my = min(my,min(y[i][0],y[i][1]));
    }
    
    int len = max(Mx - mx,My - my);
    cout << len*len << '\n';
    return 0;
}

T2—1800. 不做最后一个！

农夫约翰有 7 头奶牛：Bessie，Elsie，Daisy，Gertie，Annabelle，Maggie，Henrietta。
他每天都给它们挤奶，并详细记录每次挤奶过程中每头牛的产奶量。
毫无疑问，产奶量大的奶牛会受到约翰的高度赞扬。
牛是一种懒惰的动物，并不愿意产出过多的牛奶。
对于它们来说，每头牛都十分乐意成为牛群中产奶量最低的奶牛。
然而，他们不断听到约翰和他的人类朋友提到“从农场到餐桌”这句话，虽然不知道是什么意思，但他们怀疑，实际上，奶牛产奶量最低并不是最好的主意。
取代这一想法的是，它们认为在牛群中产奶量第二低的位置相对来说更为安全。
请帮助奶牛们搞清楚哪头奶牛目前处在这个相对理想的位置。

输入格式
第一行包含整数 N，表示共有 N 条挤奶记录。
接下来的 N 行，每行都包含一头奶牛的名字（上述七头之一），后跟一个正整数（不超过 100），表示该头奶牛在一次挤奶过程中产生的奶量。
完全没有在记录中出现过的奶牛的产奶量视为 0。

输出格式
在一行中输出产奶量第二低的奶牛的名字。
更准确的说，假设 M 是所有奶牛中产奶量的最小值，那么请输出所有产奶量超过 M 的奶牛中产奶量最小的那头奶牛的名字。
如果有很多头奶牛满足这一条件，或者没有奶牛满足这一条件（即所有奶牛的产奶量都为 M），请输出 Tie。
如果某头奶牛完全没有在挤奶记录中出现过，则 M=0，因为那头奶牛根本就没有产奶。

数据范围
1≤N≤100
输入样例：
10
Bessie 1
Maggie 13
Elsie 3
Elsie 4
Henrietta 4
Gertie 12
Daisy 7
Annabelle 10
Bessie 6
Henrietta 5
输出样例：
Henrietta
样例解释
在此样例中，Bessie，Elsie，Daisy 的产奶量为 7，并列产奶量最低，除了它们三个以外，产奶量最低的是 Henrietta，其产奶量为 9。

比较简单。

题解一：我的处理麻烦了。

#include <iostream>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;
    
    map<string,int> m = {{"Bessie",0},{"Elsie",0},{"Daisy",0},{"Gertie",0},
    {"Annabelle",0},{"Maggie",0},{"Henrietta",0}};
    string s;
    int d;
    for (int i = 0;i < n;i ++){
        cin >> s >> d;
        m[s] += d;
    }
    
    int p1 = 1e7;
    for (map<string,int>::iterator it = m.begin();it != m.end();it ++){
        p1 = min(p1,it->second);
    }
    
    int p2 = 1e7;string ans;
    for (map<string,int>::iterator it = m.begin();it != m.end();it ++){
        if (it->second > p1 && it->second < p2){
            p2 = it->second,ans = it->first;
        }
    }
    
    int cnt = 0;
    for (map<string,int>::iterator it = m.begin();it != m.end();it ++){
        if (it->second == p2) cnt ++;
    }
    //cout << p1 << ' ' << p2 << ' ' << cnt << '\n';
    if (p2 == 1e7 || cnt > 1) cout << "Tie\n";
    else cout << ans << '\n';
    return 0;
}

题解二：巧用sort和erase，unique函数。

#include <algorithm>
#include <vector>
#include <iostream>
#include <unordered_map>
using namespace std;

int main(){
    unordered_map<string,int> hash = {
        {"Bessie",0},
        {"Elsie",0},
        {"Daisy",0},
        {"Gertie",0},
        {"Annabelle",0},
        {"Maggie",0},
        {"Henrietta",0}
    };
    
    int n;
    cin >> n;
    
    string str;int x;
    while (n--){
        cin >> str >> x;
        hash[str] += x;
    }
    
    vector<int> q;
    for (auto &[k , v] : hash) q.push_back(v); // 复习一下怎么遍历map
    sort(q.begin(),q.end());
    q.erase(unique(q.begin(),q.end()),q.end());
    
    if (q.size() == 1) cout << "Tie\n";
    else{
        int cnt = 0;string name;
        for (auto &[k , v] : hash){
            if (v == q[1]){
                name = k;
                cnt ++;
            }
            
            if (cnt > 1){
                cout << "Tie\n";
                break;
            }
        }
        if (cnt == 1) cout << name << '\n';
    }
    
    return 0;
}

T3—1788. 牛为什么过马路

尽管科学界已经深入探究了鸡为什么过马路这一问题，令人惊讶的是，关于牛过马路的的研究文献却很少发表。
农夫约翰很清楚这一问题的重要性，当一所当地的大学联系他，要求他协助进行一项关于奶牛为什么要过马路的科学研究时，他非常激动并热心的表示愿意帮忙。
作为研究的一部分，约翰被要求记录下他的每头奶牛穿过马路的次数。
他仔细记录了奶牛的位置数据，在一天时间里，他进行了 N 次观察，每次观察都会记录一头牛的 ID （约翰共有 10 头牛，ID 从 1 到 10）以及牛在路的哪一边。
根据约翰记录的数据，请帮助他计算可以确定的奶牛穿过马路的次数。
当连续观察到一头奶牛在道路的两侧时，就可以确定它穿过了一次马路。

输入格式
第一行包含整数 N。
接下来 N 行，用来描述观察结果，首先包含一个整数表示观察奶牛的 ID，然后包含一个整数 0 或 1，0 表示它在马路一边，1 表示它在马路另一边。

输出格式
输出可以确认发生的穿过马路的次数。

数据范围
1≤N≤100,

输入样例：
8
3 1
3 0
6 0
2 1
4 1
3 0
4 0
3 1
输出样例：
3
样例解释
在此样例中，3 号奶牛穿过马路两次，先 1→0，然后 0→1。
4 号奶牛穿过马路一次 1→0。
2 号和 6 号奶牛没有穿过马路。

水题。

#include <iostream>
#include <algorithm>
using namespace std;
int p[11];

int main(){
    int n;
    cin >> n;
    
    for (int i = 1;i <= 10;i ++) p[i] = -1;
    
    int x,y,res = 0;
    while (n--){
        cin >> x >> y;
        if (p[x] != -1 && p[x] ^ y) res ++;
        p[x] = y;
    }
    cout << res << '\n';
    return 0;
}

T4—1775. 丢失的牛

农夫约翰丢掉了他最宝贵的奶牛贝茜，他需要找到她！
幸运的是，农场只有一条长长的小路，约翰知道贝茜一定在这条小路上的某个地方。
如果我们将这条路看作一个数轴，那么约翰当前位于位置 x，贝茜当前位于位置 y（约翰不知道其具体位置）。
如果约翰知道贝茜所处的具体位置，那么只需直接朝她走去，找到她只需行进 |x−y| 的距离。
不幸的是，外面很黑，农夫约翰什么也看不见。
他找到贝茜的唯一办法就是来回走动，直到他最终到达她的位置。
为了找出在搜索过程中来回走动的最佳策略，约翰查阅了计算机科学研究文献，发现这个确切的问题不仅在过去被计算机科学家研究过，而且它实际上被称为“丢失的奶牛问题”（这是真的！）。
农民约翰找到贝茜的推荐行动方式是首先移动到位置 x+1，然后反向移动到位置 x−2，然后移动到位置 x+4，依此类推，以“之字形”模式，每一次移动到的位置与初始位置之间的距离都是上一次移动到的位置与初始位置之间的距离的两倍。
正如他在研究解决丢失奶牛问题的算法时了解到的那样，这种方法保证了在最坏的情况下，找到贝茜之前，他需要行进 9 倍于他与贝茜之间的直接距离的路程。（事实上，相比于其他策略的最坏情况，9 倍于实际距离已经是最好的了）
农夫约翰很想验证这个结果。
给定 x 和 y，请根据上面的“之字形”搜索策略计算直到找到贝茜为止，他将要行进的总距离是多少。

输入格式
共一行，包含两个整数 x,y。

输出格式
输出一个整数，表示总行进距离。

数据范围
0≤x,y≤1000
输入样例：
3 6
输出样例：
9

模拟题。

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int x,y;
    cin >> x >> y;
    
    int res = 0,c = x,i = 1;
    while (true){
        if (c < y && x + i >= y || c > y && x + i <= y){
            res += abs(c - y);
            break;
        }
        res += abs(c - x - i);
        c = x + i;
        i *= -2;
    }
    
    cout << res << '\n';
    return 0;
}

T5—1866. 围栏刷漆

几经酷暑严冬，农夫约翰的围栏已经破旧不堪。
他觉得是时候重新粉刷围栏了。
他最喜欢的奶牛贝茜也会帮助他完成这一工作。
不幸的是，尽管贝茜非常擅长刷漆，但她并不擅长理解农夫约翰的指示。
如果我们将围栏看作一条一维数轴，约翰会负责粉刷 x=a 到 x=b 之间的围栏。
例如，如果 a=3,b=5，则约翰将粉刷的围栏长度为 2。
贝茜误解了约翰的指示，因此，她将粉刷 x=c 到 x=d 之间的围栏。
这段区域可能会与约翰需要粉刷的区域部分或完全重叠。
现在，请你确定被粉刷围栏的总长度。

输入格式
第一行包含两个整数 a,b。
第二行包含两个整数 c,d。

输出格式
输出被粉刷围栏的总长度。

数据范围
0≤a<b≤100,
0≤c<d≤100
输入样例：
7 10
4 8
输出样例：
6
样例解释
从 x=4 到 x=10 的总计长度为 6 的围栏被粉刷。

究极水题。

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    
    cout << d - c + b - a - max(min(b,d)-max(a,c),0) << '\n';
    return 0;
}

T6—1854. 晋升计数

奶牛贝茜正在帮助农夫约翰举办全美奶牛奥林匹克竞赛(USACO)。
这是一个线上比赛，参赛者通过回答具有挑战性的问题，来展示自己对牛的琐事的掌握。
为了迎合更大范围的参与者，约翰最近扩大了比赛范围，将比赛按难度分为四个组：铜、银、金和白金。
所有新的参赛者都从铜组开始，只要他们在比赛中取得完美的成绩，他们就会被提升到下一个更高的组。
一个参赛者甚至有可能在同一场比赛中被多次提升。
农夫约翰会记录所有参赛者的名单和他们当前所在的分组。
这样就可以在举办比赛时，让每个人都在属于自己水平的分组开始。
在公布最近一次比赛的结果时，约翰希望包含铜组晋升银组、银组晋升金组、金组晋升白金组的人员数量信息。
然而，在比赛中他却忘记统计每组的晋升人数了。
贝茜是一头聪明的奶牛，她发现可以仅根据比赛前后处于各个组别的人员数量来推断晋升的次数。
请帮她做出这个计算。

输入格式
共四行，每行两个整数。
第一行表示比赛前后铜组人员数量。
第二行表示比赛前后银组人员数量。
第三行表示比赛前后金组人员数量。
第四行表示比赛前后白金组人员数量。

输出格式
共三行，每行输出一个整数。
第一行整数表示铜组晋升银组的人数。
第二行整数表示银组晋升金组的人数。
第三行整数表示金组晋升白金组的人数。

数据范围
输入整数范围 [0,10^6]。

输入样例：
1 2
1 1
1 1
1 2
输出样例：
1
1
1
样例解释
在此样例中，比赛前各组都只有 1 人，比赛后铜组和白金组各增加 1 人。
一种可能的情况是，赛后出现了两个新报名人员，加入铜组，赛前处于铜组的人员一路升入白金组。

数学推理。

#include <iostream>
#include <algorithm>
using namespace std;
int q[4][2];

int main(){
    for (int i = 0;i < 4;i ++){
        cin >> q[i][0] >> q[i][1];
    }
    
    int a = q[3][1] - q[3][0]; // 白金增加的人数只能全部由金晋升而来
    int b = q[2][1] - q[2][0] + a; // 金的变化人数 = 新来的 - 往上升的
    int c = q[1][1] - q[1][0] + b;
    cout << c << '\n' << b << '\n' << a << '\n';
    return 0;
}