grant's Blog

记录生活中的点点滴滴

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

发表于 更新于 分类于 ，   阅读次数： Valine：
本文字数： 6.5k 阅读时长 ≈ 6 分钟

第二周

T1—1442. 单词处理器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
奶牛 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 个非空格字符，所以这个单词会被放到下一行。

模拟题，模拟就行。空格问题，评测机不处理。（Acwing特色）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int N =105;
int n,k;
string str[N];

int main(){
    cin >> n >> k;
    
    for (int i = 0;i < n;i ++) cin >> str[i];
    
    int a = k;
    for (int i = 0;i < n;){
        int t = str[i].size(); // 注意str.size()返回值是unsigned
        if (a - t < 0){
            cout << '\n';
            a = k;
        }else{
            a -= t;
            cout << str[i] << ' ';
            i ++;
        }
    }
    return 0;
}

T2—1671. 三角形

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Farmer John 想要给他的奶牛们建造一个三角形牧场。
有 N 个栅栏柱子分别位于农场的二维平面上不同的点 (X1,Y1)…(XN,YN)。
他可以选择其中三个点组成三角形牧场，只要三角形有一条边与 x 轴平行，且有另一条边与 y 轴平行。
Farmer John 可以围成的牧场的最大面积是多少？
保证存在至少一个合法的三角形牧场。

输入格式
输入的第一行包含整数 N。
以下 N 行每行包含两个整数 Xi 和 Yi，均在范围 −10^4…10^4 之内，描述一个栅栏柱子的位置。

输出格式
由于面积不一定为整数，输出栅栏柱子可以围成的合法三角形的最大面积的两倍。

数据范围
3≤N≤100
输入样例：
4
0 0
0 1
1 0
1 2
输出样例：
2
样例解释
位于点 (0,0)、(1,0) 和 (1,2) 的木桩组成了一个面积为 1 的三角形。所以，答案为 2⋅1=2。
只有一个其他的三角形，面积为 0.5。

数据量较小，暴力枚举，参考 AcWing2AK 大佬。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 105;
int n;
struct Node{
    int x,y;
}q[N];

int main(){
    cin >> n;
    
    for (int i = 0;i < n;i ++) cin >> q[i].x >> q[i].y;
    
    int res = 0;
    for (int i = 0;i < n;i ++)
        for (int j = 0;j < n;j ++)
            for (int k = 0;k < n;k ++){
                if (i == j || j == k || i == k) continue;
                if (q[i].x == q[j].x && q[j].y == q[k].y)
                    res = max(res,abs((q[i].y-q[j].y)*(q[j].x-q[k].x)));
            }
            
    cout << res << '\n';
    return 0;
}

T3—1659. 社交距离 I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
一种新型疾病，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≤N≤10^5
输入样例：
14
10001001000010
输出样例：
2
样例解释
在这个例子中，Farmer John 可以以这样的方式加入奶牛，使得牛栏分配变为 10x010010x0010，其中 x 表示新来的奶牛。

此时 D=2。
不可能在加入奶牛之后取到更大的 D 值。

不会了。思维题。

分类讨论，情况可以分为两种：

  1. 两头牛放在一个区间里；
  2. 两头牛分别放在两个区间里。

对于情况1，简单画个草图：

image-20220326194304177

以红色竖线标记原来的奶牛，黑色竖线表示牛栏的两个端点（可能有牛），绿色竖线表示新加入的两头牛。

对于两边的端点，新加的牛将小区间分为两半是最优解，如果不能被2整除，一个下取整，一个上取整；对于中间的小区间，则平均分为三份。

对于情况2，两端同样特殊处理，中间类似，最优解是一头牛放最大距离区间，另一头放次大距离区间。

还是看代码吧。

拓展关于维护序列最大值和次大值的方法：假设最大值和次大值分别为y_1和y_2，对于每个新加入的d，分三种情况讨论，d >= y_1，y_1 > d > y_2，y_2 >= d。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int N = 1e5;
int p[N]; // p数组记录原来每头牛出现的位置

int main(){
    int n;
    string str;
    cin >> n >> str;
    
    int m = 0;
    for (int i = 0;i < str.size();i ++){
        if (str[i] == '1') p[m ++] = i + 1;
    }
    
    // 特判没有牛的情况
    if (!m){
        cout << n - 1 << '\n';
    }else{
        // 情况1：两头牛放在一个区间里
        int xmin = N; // 记录原来每两头牛间距离的最小值
        for (int i = 1;i < m;i ++)
            xmin = min(xmin,p[i] - p[i-1]);
        // y维护划分的最大值
        int y = max((p[0] - 1)/2,(n - p[m-1])/2);
        for (int i = 1;i < m;i ++)
            y = max(y,(p[i] - p[i-1])/3);
        
        // 情况2：两头牛分别放在两个区间里
        int y1 = p[0] - 1,y2 = n - p[m-1];
        if (y1 < y2) swap(y1,y2); // y1维护划分的最大值，y2维护次大值
        for (int i = 1;i < m;i ++){
            int d = (p[i] - p[i-1])/2;
            if (d >= y1) y2 = y1,y1 = d;
            else if (d > y2) y2 = d;
        }
        // 要使得D尽可能地大，必须使得y和y2尽可能地大
        cout << min(xmin,max(y,y2)) << '\n';    
    }
    return 0;
}

T4—1714. 混合牛奶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
农业，尤其是生产牛奶，是一个竞争激烈的行业。
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 次之后每个桶里将会有多少牛奶。

输入格式
输入文件的第一行包含两个空格分隔的整数：第一个桶的容积 c1，以及第一个桶里的牛奶量 m1。
第二和第三行类似地包含第二和第三个桶的容积和牛奶量。

输出格式
输出三行，给出倒了 100 次之后每个桶里的牛奶量。

数据范围
1≤c1,m1≤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
（之后最后三个状态循环出现……）

没什么说的，纯模拟题。

参考大佬题解： https://www.acwing.com/solution/content/103857/。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <algorithm>
using namespace std;
int q[3],c[3];

int main(){
    for (int i = 0;i < 3;i ++) cin >> q[i] >> c[i];
    
    int n = 100;
    while (n){
        if (n){
            int xmin = min(c[0],q[1] - c[1]);
            c[0] -= xmin,c[1] += xmin;
            n --;
        }
        if (n){
            int xmin = min(c[1],q[2] - c[2]);
            c[1] -= xmin,c[2] += xmin;
            n --;
        }
        if (n){
            int xmin = min(c[2],q[0] - c[0]);
            c[2] -= xmin,c[0] += xmin;
            n --;
        }
        if (!n) break;
    }
    
    cout << c[0] << '\n' << c[1] << '\n' << c[2] << '\n';
    return 0;
}

T5—1695. 果壳游戏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
为了消磨时光，奶牛 Bessie 和她的朋友 Elsie 喜欢玩一种她们在农业展览会上看到的游戏。
游戏准备阶段，Bessie 在桌子上放置三个倒置的坚果壳，并在其中一个坚果壳下面藏了一块小的鹅卵石（至少她希望这是一块鹅卵石——她在一块牧场的地上找到的）。
随后 Bessie 会两两调换坚果壳，同时 Elsie 试着去猜鹅卵石的位置。
奶牛们在农业展览会上看到的这个游戏的标准形式是玩家可以看到鹅卵石初始的位置，然后要求玩家猜所有交换完成之后鹅卵石最终的位置。
然而，现在奶牛们想要去进行这样一种玩法，Elsie 不知道鹅卵石的初始位置，同时她可以在每一次交换之后猜一下鹅卵石的位置。
Bessie 知道正确答案，在游戏结束后会给 Elsie 一个分数，等于她猜对的次数。
给定所有的交换和 Elsie 的猜测，但是不给出鹅卵石的初始位置，请求出 Elsie 最高可能获得的分数。

输入格式
输入的第一行包含一个整数 N，为交换的次数。
以下 N 行每行描述了游戏的一个回合，包含三个整数 a、b 和 g，表示 Bessie 交换了坚果壳 a 和 b，然后 Elsie 猜的是坚果壳 g。
所有这三个数均为 1、2、3 之一，并且 a≠b。

输出格式
输出 Elsie 可以得到的最高分数。

数据范围
1≤N≤100
输入样例：
3
1 2 1
3 2 1
1 3 1
输出样例：
2
样例解释
在这个例子中，Elsie 最多可以获得 2 分。
如果鹅卵石开始时位于坚果壳 1 下面，那么她猜中了一次（最后一次）。
如果鹅卵石开始时位于坚果壳 2 下面，那么她猜中了两次（开始两次）。
如果鹅卵石开始时位于坚果壳 3 下面，那么她没有猜对任何一次。

水题，直接暴力。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N =105;
int n,a[N],b[N],g[N];
bool st[4];

int main(){
    cin >> n;
    
    for (int i = 0;i < n;i ++) cin >> a[i] >> b[i] >> g[i];
    
    int res = 0;
    for (int i = 1;i <= 3;i ++){
        memset(st,0,sizeof st);
        st[i] = true;
        int cnt = 0;
        for (int j = 0;j < n;j ++){
            swap(st[a[j]],st[b[j]]);
            cnt += st[g[j]];
        }
        res = max(res,cnt);
    }
    cout << res << '\n';
    return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！