2022寒假每日一题笔记（四）

第四周

2022.1.22—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]
输入样例：
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)，虽然计算结果相同，但是赋值方式不同，所以要分别计数。

答案就是求整个式子mod 2的结果，整体mod 2同余于先mod 2再相加相乘，所以计算量为2^7。

可以爆搜枚举。（有DFS和二进制两种方法）

y总这里采用二进制写法。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    
    unordered_map<char,int> cnt[2];
    char c;int x;
    while (n--){
        cin >> c >> x;
        cnt[abs(x) % 2][c] ++; // 特别注意负余数！记录每个变量值的奇偶数的数量
    }
    
    int res = 0;
    unordered_map<char,int> v;
    string str = "BESIGOM";
    for (int i = 0;i < 1 << 7;i ++){ // 0~2^7表示7个变量取奇偶数的所有情况
        for (int j = 0;j < 7;j ++) // 
            v[str[j]] = i >> j & 1;
        // E + E 在mod 2中相当于0
        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;
    return 0;
}

仿写的DFS写法。

#include <bits/stdc++.h>
using namespace std;

int res = 0;
string str = "BESIGOM";
unordered_map<char,int> cnt[2];
unordered_map<char,int> v;

void dfs(int u,int s){ // dfs枚举状态
    if (u == 8){
        for (int i = 0;i < 7;i ++)
            v[str[i]] = s >> i & 1;
        
        if ((v['B']+v['I'])*(v['G']+v['O']+v['E']+v['S'])*(v['M']) % 2 == 0){
            int sum = 1;
            for (int i = 0;i < 7;i ++){
                sum *= cnt[s >> i & 1][str[i]];
            }
            res += sum;
        }
        return;
    }
    
    s += 0 << (u-1); // 每个变量有0和1两种状态
    dfs(u + 1,s);
    
    s += 1 << (u-1);
    dfs(u + 1,s);
}

int main(){
    int n;
    cin >> n;
    
    char c;int x;
    while (n--){
        cin >> c >> x;
        cnt[abs(x) % 2][c] ++; // 特别注意负余数！记录每个变量值的奇偶数的数量
    }
    
    dfs(1,0);
    cout << res;
    return 0;
}

2022.1.23—1855. 愤怒的奶牛

奶牛贝茜设计了一款她认为必火的游戏：愤怒的奶牛。
游戏设定（她坚信这是她的原创）是玩家用一个弹弓将一头奶牛射向一个数轴，数轴的不同位置上分布着一些干草捆。
奶牛以足够的力量砸向某个干草捆，并使得该干草捆发生爆炸，爆炸可能会不断引起连锁反应，导致更多的干草捆发生爆炸。
目标是用一头奶牛引起的连锁反应引爆尽可能多的干草捆。
共有 N 个干草捆位于数轴中的不同整数位置，其坐标依次为 x1,x2,…,xN。
如果将奶牛射向位于位置 x 的干草捆，则该干草捆发生爆炸，爆炸半径为 1，爆炸将吞噬 1 单位距离内的所有干草捆。
然后这些干草捆（全部同时）发生爆炸，每个干草捆的爆炸半径为 2。
二次爆炸中吞噬的所有尚未爆炸的干草捆也（全部同时）发生爆炸，爆炸半径为 3。
也就是说，在 t 时刻爆炸的干草捆的爆炸半径为 t，其爆炸波及的干草捆在 t+1 时刻也会爆炸，爆炸半径为 t+1，以此类推。
请确定，通过合理选择奶牛射向的干草捆，能够引爆的干草捆最大数量。

输入格式
第一行包含整数 N。

接下来 N 行包含 x1,…,xN。

输出格式
输出能够引爆的干草捆的最大数量。

数据范围
1≤N≤100,
0≤xi≤10^9
输入样例：
6
8
5
6
13
3
4
输出样例：
5
样例解释
将奶牛射向位于位置 5 的干草捆，产生半径为 1 的爆炸。
爆炸吞噬位置 4 和 6 处的干草捆，引发半径为 2 的二次爆炸。
二次爆炸吞噬位置 3 和 8 处的干草捆，引发半径为 3 的三次爆炸。
位置 13 的干草捆无法被引爆。

又不会。本题比较考验读题能力。

可以发现爆炸的一个性质：爆炸范围是连续的一段区间。

#include <bits/stdc++.h>
using namespace std;
const int N = 105,INF = 2e9;
int q[N];

int main(){
    int n;
    cin >> n;
    
    q[0] = -INF,q[n + 1] = INF; // 设置两个左右哨兵
    for (int i = 1;i <= n;i ++) cin >> q[i];
    sort(q + 1,q + n + 1);
    
    int res = 0;
    for (int i = 1;i <= n;i ++){
        int l = 1,r = 1,a = i,b = i; // l,r表示爆炸的波数，也就是爆炸半径
        // a,b表示最左，右侧爆炸块的下标
        
        while (q[a] - q[a-1] <= l){ // 求第l波爆炸最左侧爆炸块的下标
            int k = a-1;
            while (q[a] - q[k-1] <= l) k --; // 直到第l波爆炸不能再向左扩展
            a = k; 
            l ++; // 第l波爆炸结束
        }
        
        while (q[b+1] - q[b] <= r){
            int k = b+1;
            while (q[k+1] - q[b] <= r) k ++;
            b = k;
            r ++;
        }
        
        res = max(res,b-a+1);
    }
    
    cout << res;
    return 0;
}

2022.1.24—1843. 圆形牛棚

作为当代建筑的爱好者，农夫约翰建造了一个完美圆环形状的新牛棚。
牛棚内部有 n 个房间，围成一个环形，按顺时针编号为 1∼n。
每个房间都既有通向相邻两个房间的门，也有通向牛棚外部的门。
约翰想让第 i 个房间内恰好有 ri 头牛。
为了让奶牛们有序的进入牛棚，他计划打开一个外门，让牛从该门进入。
然后，每头牛顺时针穿过房间，直到到达合适的房间为止。
约翰希望通过合理选择打开的门，使得所有奶牛的行走距离之和尽可能小（这里只考虑每头牛进入牛棚以后的行走距离）。
请确定他的奶牛需要行走的最小总距离。

输入格式
第一行包含整数 n。
接下来 n 行，包含 r1,…,rn。

输出格式
输出所有奶牛需要行走的最小总距离。

数据范围
3≤n≤1000,
1≤ri≤100
输入样例：
5
4
7
8
6
4
输出样例：
48
样例解释
最佳方案是让奶牛们从第二个房间进入。

本题比较简单。

我们遍历所有的 n 个牛棚，以每个牛棚位置为开门位置，分别求出所有奶牛到达位置的总距离，并取所有情况最小值，即为结果。

对于每个起始位置 i，根据题意，该牛棚的奶牛移动距离为 0，其右侧第 j 个牛棚（也即编号为第 (i+j)%n 个牛棚）奶牛移动距离为 j，以此类推。只需要一次遍历即可。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {

    int n;
    cin >> n;
    vector<int> r(n);
    for(int i = 0; i < n; ++i) cin >> r[i];

    int ret = INT_MAX; // 记录结果最小值，所以初始值设为超级大

    for(int i = 0; i < n; ++i) {
        // 从第 i 个门进入
        int cur = 0;
        for(int j = 1; j < n; ++j) {
            cur += j * r[(i + j) % n];
        }
        ret = min(ret, cur);
    } 

    cout << ret << endl;
    return 0;
}

我的代码，比较啰嗦。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1005;
int n;
int q[N],s[N];

int main(){
    cin >> n;
    
    for (int i = 1;i <= n;i ++){
        cin >> q[i];
        s[i] = q[i] + s[i-1];
    }
    
    int res = 0x3f3f3f3f;
    for (int i = 1;i <= n;i ++){
        int cnt = 0,t = s[n];
        for (int j = i, k = 1;k == 1 || j != i;j ++,k ++){
            if (j == n+1) j = 1;
            if (k != 1 && i == j) break;
            t -= q[j];
            cnt += t;
        }
        res = min(res,cnt);
    }
    
    cout << res;
    return 0;
}

2022.1.25—1826. 农田缩减

农夫约翰的 N 头奶牛分布在其二维农场的不同位置。
约翰想用一个长方形的围栏把所有的奶牛围起来，围栏的边需要平行于 x 轴和 y 轴。
在能够包含所有奶牛的情况下（处于围栏边界的奶牛也算包含在内），约翰希望围栏围起的面积尽可能小。
不幸的是，由于上个季度的牛奶产量很低，约翰的预算十分紧张。
因此，他希望建立一个更小的围栏，甚至为了实现这一目标，他愿意卖掉农场中的一头奶牛。
请帮助约翰计算，卖掉牛群中的一头奶牛以后，他可以用围栏围起来的最小面积（为剩下的奶牛建造尽可能小的围栏）。
对于这个问题，请将奶牛视为点，将围栏视为四个线段的集合。
注意，答案可以是零，例如，所有剩余的奶牛最终都站在同一条垂直或水平线上。

输入格式
第一行包含整数 N。
接下来 N 行，每行包含两个整数 x,y，表示一头牛所在的位置坐标为 (x,y)。

输出格式
输出卖掉牛群中的一头奶牛以后，约翰可以用围栏围起来的最小面积。

数据范围
3≤N≤50000,
1≤x,y≤40000
输入样例：
4
2 4
1 1
5 2
17 25
输出样例：
12

思路：影响围栏面积的就是横坐标和纵坐标的最大、最小值。

该卖掉那哪头牛呢？枚举四条边界上的牛。

然后求删掉这头牛之后的四个方向的最值就行。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50005;
int n,x[N],y[N],a[N],b[N];

int main(){
    cin >> n;
    
    for (int i = 0;i < n;i ++){
        cin >> x[i] >> y[i];
        a[i] = x[i],b[i] = y[i];
    }
    
    sort(a,a + n),sort(b,b + n); // 分别排序横纵坐标
    
    int res = 2e9;
    for (int i = 0;i < n;i ++){ // 枚举删掉x[i],y[i]坐标奶牛的情况
        int x1,x2,y1,y2;
        
        x1 = x[i] == a[0] ? a[1] : a[0]; // 如果枚举的是边界点就删掉然后取次最值
        x2 = x[i] == a[n-1] ? a[n-2] : a[n-1];
        y1 = y[i] == b[0] ? b[1] : b[0];
        y2 = y[i] == b[n-1] ? b[n-2] : b[n-1];
        res = min(res,(x2-x1)*(y2-y1));
    }
    
    cout << res;
    return 0;
}

2022.1.26—1813. 方块游戏

农夫约翰试图通过给奶牛一套通常用于学龄前儿童的 N 个拼写板来教他的奶牛阅读。
每个拼写板的每一侧都有一个单词和一个图画。
例如，一侧可能有单词 cat 和一只小猫，另一侧可能有单词 dog 和一只小狗。
因此，当所有拼写板放置到地面上时，会显示一组 N 个单词。
通过翻转其中一部分板子，就可以得到另一组 N 个单词。
为了帮助奶牛练习单词拼写，约翰想要制作一些木块，在每个木块上都印上一个字母，使得奶牛可以使用这些木块拼出看到的单词。
为了使得无论哪一组 N 个单词朝上显示，奶牛都能将其全部拼出，就需要印有各种字母的木块都足够的多。
例如，如果 N=3 且单词 box,cat,car 朝上显示，则奶牛至少需要一个 b 块，一个 o 块，一个 x 块，两个 c 块，两个 a 块，一个 t 块和一个 r 块。
请帮助约翰确定，印有每种字母的木块至少需要提供多少块，才能使得不管每个板子的哪一侧朝上显示，奶牛都可以拼出所有 N 个可见的单词。

输入格式
第一行包含整数 N。
接下来 N 行，每行包含两个单词，这两个单词分别位于一块木板的两侧，每个单词都是长度不超过 10 的小写字母构成的字符串。

输出格式
共 26 行。
第一行输出印有字母 a 的木块所需的块数。
第二行输出印有字母 b 的木块所需的块数，以此类推。

数据范围
1≤N≤100
输入样例：
3
fox box
dog cat
car bus
输出样例：
2
2
2
1
0
1
1
0
0
0
0
0
0
0
2
0
0
1
1
1
1
0
0
1
0
0
样例解释
在此样例中，共有 N=3 块拼写板，共有 8 种单词组合：
fox dog car
fox dog bus
fox cat car
fox cat bus
box dog car
box dog bus
box cat car
box cat bus

简单题。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int cnt[2][27],ans[27];

int main(){
    int n;
    string str1,str2;
    cin >> n;
    
    for (int i = 0;i < n;i ++){
        memset(cnt,0,sizeof cnt);
        cin >> str1 >> str2;
        for (auto c:str1) cnt[0][c-'a'] ++;
        for (auto c:str2) cnt[1][c-'a'] ++;
        
        for (int i = 0;i < 26;i ++){
            int x = max(cnt[0][i],cnt[1][i]); // 累加每张卡正反面中每个字母出现的最多次数
            ans[i] = ans[i] + x;
        }
    }
    
    for (int i = 0;i < 26;i ++) cout << ans[i] << '\n';
    return 0;
}

2022.1.27—1801. 蹄子剪刀布

你可能听说过“石头剪刀布”的游戏。
这个游戏在牛当中同样流行，它们称之为“蹄子剪刀布”。
游戏的规则非常简单，两头牛相互对抗，数到三之后各出一个表示蹄子，剪刀或布的手势。
蹄子赢剪刀，剪刀赢布，布赢蹄子。
例如，第一头牛出“蹄子”手势，第二头牛出“布”手势，则第二头牛获胜。
如果两头牛出相同的手势，则算平局。
农夫约翰的两头奶牛正在进行 N 轮“蹄子剪刀布”对抗，他看的十分入迷。
不幸的是，虽然他可以看到奶牛正在做出三种不同类型的手势，但他却无法分辨出哪一个代表“蹄子”，哪一个代表“布”以及哪一个代表“剪刀”。
不知道这三种手势的具体含义的情况下，农夫约翰给这三种手势分配了编号 1,2,3。
手势 1 可能代表“蹄子”，可能代表“剪刀”，也可能代表“布”，反正他傻傻分不清楚。
给出两头奶牛在 N 场比赛中所做出的具体手势对应的编号，请你判断第一头奶牛最多可能赢多少盘对抗。

输入格式
第一行包含整数 N。
接下来 N 行，每行包含两个整数（1 或 2 或 3），表示两头奶牛在一轮对抗中所出的手势对应的编号。

输出格式
输出第一头奶牛可能获胜的最大场次数。

数据范围
1≤N≤100
输入样例：
5
1 2
2 2
1 3
1 1
3 2
输出样例：
2
样例解释
此样例的一种解决方案是，1 表示剪刀，2 表示蹄子，3 表示布。
这样，第一头奶牛可以赢得 (1,3) 和 (3,2) 两场比赛。

简单题。

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

int c1(int x,int y){ // 总共只有两种胜负关系：1-->2-->3-->1,还有反过来
    if ((x+1) % 3 == y) return 1; // 将它们减1得到0,1,2，利用取模
    else return 0;
}

int c2(int x,int y){
    if (x == (y+1) % 3) return 1;
    else return 0;
}

int main(){
    int n;
    cin >> n;
    
    int x,y,t1 = 0,t2 = 0;
    while (n--){
        cin >> x >> y;
        x --,y --;
        t1 += c1(x,y);
        t2 += c2(x,y);
    }
    
    cout << max(t1,t2);
    return 0;
}