grant's Blog

记录生活中的点点滴滴

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

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

第五周

T1—1789. 牛为什么过马路 II

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 头奶牛，依次命名为 A∼Z。
因此，道路上共有 52 个不同的进出位置。
约翰沿着环形道路按顺时针方向扫描了每个位置，并记录了每个位置处经过的奶牛的名字，最终形成了一个包含 52 个字母的序列，A∼Z 中的每个字母恰好出现两次。
他并没有记录哪些位置是入口，哪些位置是出口。
看着地图上记录的这些位置，约翰想要知道一天当中，有多少对奶牛之间的从入口穿过田地到达出口的路径可能会存在交叉。
如果奶牛 a 从入口穿过田地到达出口的路径必须穿过奶牛 b 从入口穿过田地到达出口的路径，那么称这对牛 (a,b) 是“交叉”对。
请帮助约翰计算“交叉”对的总数。

输入格式
共一行，包含一个长度为 52 的只包含大写字母的字符串，其中每个字母恰好出现两次。

输出格式
输出交叉对的总数。

输入样例：
ABCCABDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ
输出样例：
1
样例解释
在此样例中，只有 A 和 B 一对交叉对。

思维题，枚举就行，不考察算法。

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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int> PII;
int a[27],b[27];
vector<PII> p;

int main(){
    string str;
    
    cin >> str;
    
    int res = 0;
    for (int i = 0;i < 52;i ++){
        int x = str[i] - 'A';
        if (!a[x]) a[x] = i + 1;
        else b[x] = i + 1;
        
        if (a[x] && b[x]){ // 找到一对出入口，记录位置
            if (p.size()){
                for (int j = p.size()-1;j >= 0;j --){// 满足交叉大小关系res ++
                    if (a[x] > p[j].first && b[x] > p[j].second && a[x] < p[j].second)
                        res ++;
                }
            }
            
            p.push_back({a[x],b[x]});
        }
    }
    
    cout << res;
    return 0;
}

T2—1776. 牛的基因组学

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
农夫约翰拥有 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

思维题，枚举就行，不考察算法。

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
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 105;
int n,m;
string a[N],b[N];
bool fa[N][4],fb[N][4];

int main(){
    cin >> n >> m;
    unordered_map<char,int> p = {{'A',0},{'C',1},{'G',2},{'T',3}};
    
    
    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 j = 0;j < m;j ++){
        for (int i = 0;i < n;i ++){
            fa[j][p[a[i][j]]] = true; // 第j个位置（从0开始）是否有'A','C',...等基因
            fb[j][p[b[i][j]]] = true;
        }
        
        bool flag = true;
        for (int i = 0;i < 4;i ++){
            if (fa[j][i] && fb[j][i]){ // 斑点牛和无斑点牛该位置有相同基因，说明没用
                flag = false;break;
            }
        }
        if (flag) res ++;
    }
    
    cout << res;
    return 0;
}

T3—1762. 牛的洗牌

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
农夫约翰坚信快乐的奶牛会产出更多的牛奶，因此他在谷仓中安装了一个巨大的迪斯科球，并计划教他的奶牛跳舞！
在查阅了一些牛的流行舞蹈后，约翰决定教他的奶牛“洗牌舞”。
洗牌舞是由他的 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

模拟题，不考察算法。

本题给定了洗牌后的排列顺序，要求还原洗牌前的位置。所以我们可以将给定的洗牌反转，得到“逆洗牌”顺序，然后直接根据最终位置进行三次逆洗牌即可。

参考题解： https://www.acwing.com/solution/content/88882/。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n,a[N],b[N],c[N];

int main(){
    cin >> n;
    
    int x; // 洗牌过程；i位置-->x位置；逆洗牌过程；x位置-->i位置
    for (int i = 1;i <= n;i ++) cin >> x,a[x] = i; // 记录逆洗牌过程
    // 记录三次洗牌过程后的位置
    for (int i = 1;i <= n;i ++) cin >> b[i];
    // 经过三次逆洗牌过程后，i位置（洗牌后位置）-->a[a[a[i]]]位置（洗牌前位置）
    for (int i = 1;i <= n;i ++) c[a[a[a[i]]]] = b[i];
    
    for (int i= 1;i <= n;i ++) cout << c[i] << '\n';
    
    return 0;
}

T4—1750. 救生员

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

输入格式
第一行包含整数 N。
接下来 N 行，每行描述一个救生员的工作班次，包含两个整数，表示一个救生员的开始工作时刻和结束工作时刻。
所有时刻各不相同，不同救生员的工作班次可能有覆盖。

输出格式
输出一个整数，表示解雇掉一头奶牛后，剩余救生员的工作班次仍然可以覆盖的最长时间。

数据范围
1≤N≤100
0≤开始时刻≤结束时刻≤1000
输入样例：
3
5 9
1 4
3 7
输出样例：
7

注意读题，求的是能够覆盖的总时间，而不是一个最长覆盖的子区间。

还有，时间和时刻是两个不同的概念。

题解一：枚举+区间合并。（经典的区间覆盖问题）

参考题解： https://www.acwing.com/solution/content/89052/。

求区间覆盖是比较经典的问题，本题代码中，每次遍历到一个奶牛，就将其有效工作时间计入当前总时间 sum 中。这里利用 last 变量记录上一个奶牛工作的结束时间。如果当前奶牛的开始时间大于 last，那么其有效工作时间就是完整的 [start, end] 中的时间；否则若结束时间大于 last，那么 [last, end] 区间就是其有效工作时间。

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
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 105;
int n;
PII p[N];

int main(){
    cin >> n;
    
    for (int i = 0;i < n;i ++){
        cin >> p[i].first >> p[i].second;
    }
    
    sort(p,p + n);
    
    int ans = 0;
    for (int i = 0;i < n;i ++){ // 枚举需要解雇的奶牛编号
        int last = -1,sum = 0; // last和sum必须放在两层循环之间！
        for (int j = 0;j < n;j ++){
            if (i != j){ // 解雇第i头奶牛，计算解雇后的最大覆盖长度
                int start = p[j].first,end = p[j].second;
                if (start > last){
                    sum += end - start;
                    last = end;
                }else if (last < end){
                    sum += end - last;
                    last = end;
                }
            }
        }
        ans = max(ans,sum);
    }
    
    cout << ans;
    return 0;
}

题解二：差分数组。

本题也可以转化为差分来处理，求每个单位区间的被覆盖次数。

参考代码： https://www.acwing.com/solution/content/89061/。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n,l[105],r[105],d[N],b[N];

int main(){
    cin >> n;
    
    for (int i = 1;i <= n;i ++){
        cin >> l[i] >> r[i]; // 记录时刻
        d[l[i]] ++,d[r[i]] --; // 差分处理时间段
    }
    
    int ans = 0;
    for (int i = 1;i <= n;i ++){
        d[l[i]] --,d[r[i]] ++; // 开除第i头奶牛
        
        int res = 0;
        for (int i = 1;i < N;i ++){ // 前缀和处理
            b[i] = d[i] + b[i-1];
            if (b[i] > 0) res ++; // 覆盖的区间res ++
        }
        ans = max(ans,res);
        d[l[i]] ++,d[r[i]] --; // 恢复现场，第i头奶牛回来上班
    }
    
    cout << ans;
    return 0;
}

T5—1738. 蹄球

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
为了准备即将到来的蹄球锦标赛，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 可以将球传给她之后所有奶牛最终都能被传到球。

不太会。

对于一个n点n边的图，图中只存在一个环。被称为基环树。

也就是一个环上的节点挂着一堆树。

基环树，也是环套树，简单地讲就是树上在加一条边。它形如一个环，环上每个点都有一棵子树的形式。因此，对基环树的处理大部分就是对树处理和对环处理。显然，难度在于后者。

参考博客。（总结很不错！）

回到题目，我们构建一个图，传球双方作为图中的节点，传球路线表示一条边。

这个图中的节点入度 <= 2，出度 = 1，也就是一棵基环树。

将奶牛从小到大按位置在数轴排列，无论从左走或者从右走都会出现一个长度为2的环，是个特殊的基环图。

图解：

一共只有两种情况：环或者基环树。

image-20220209210524529

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 <bits/stdc++.h>
using namespace std;
const int N = 105,INF = 1e4;
int q[N],p[N],d[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);
    
    for (int i = 1;i <= n;i ++){ // p[i] = k表示i连向k的一条边，d[i]表示i的入度
        if (q[i] - q[i-1] <= q[i+1] - q[i]) p[i] = i-1,d[i-1] ++;
        else p[i] = i+1,d[i+1] ++;
    }
    
    int res = 0;
    for (int i = 1;i <= n;i ++){
        // 树上入度为0的点的权为2，若环上两点都没挂树，则两点权共为2，答案减半
        if (!d[i]) res += 2; 
        else if (p[p[i]] == i && d[i] == 1 && d[p[i]] == 1) res ++;
    }
    
    cout << res/2;
    return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！