grant's Blog

记录生活中的点点滴滴

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

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

第七周

T1—1443. 拍照

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
农夫约翰在给他编号为 1…N 的 N 头奶牛排队拍照。
约翰一开始计划从左向右数第 i 个位置排编号为 ai 的奶牛，他在一张纸上写下了排列 a1,a2,…,aN。
不幸的是，这张纸刚刚被小偷偷走了！
幸好约翰仍然有机会恢复他之前写下的排列。
在这张纸被偷走之前，奶牛贝茜记录了序列 b1,b2,…,bN−1，对于每一个 1≤i<N 满足 bi=ai+ai+1。
基于贝茜的信息，帮助约翰恢复可以产生序列 b 的“字典序最小”的排列 a。
排列 x 字典序小于排列 y，如果对于某个 j，对于所有 i<j 均有 xi=yi，且有 xj<yj（换句话说，这两个排列到某个位置之前都相同，在这个位置上 x 小于 y）。
保证存在至少一个满足条件的 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。

爆搜枚举a[1]，然后后面的排列可以根据b数组推导出来，验证求得的a数组的合法性。

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 = 1005;
int b[N],a[N];

int main(){
    int n;
    cin >> n;
    
    for (int i = 1;i <= n-1;i ++) cin >> b[i];
    
    for (int i = 1;i <= b[1]-1 && i <= n;i ++){
        unordered_set<int> hash;
        bool flag = true;
        a[1] = i;
        for (int j = 2;j <= n;j ++){
            a[j] = b[j-1] - a[j-1];
            if (a[j] >= 1 && a[j] <= n && !hash.count(a[j])){
                hash.insert(a[j]);
            }
            else{
                flag = false;break;
            }
        }
        
        if (flag){
        for (int i = 1;i <= n;i ++) cout << a[i] << ' ';
        }
    }
    return 0;
}

T2—1672. 疯狂的科学家

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
Farmer John 的远房亲戚 Ben 是一个疯狂的科学家。
通常这会在家庭聚会时造成不小的摩擦，但这偶尔也会带来些好处，尤其是当 Farmer John 发现他正面对一些有关他的奶牛们的独特而不寻常的问题时。
Farmer John 当前正面对一个有关她的奶牛们的独特而不寻常的问题。
他最近订购了 N 头奶牛，包含两种不同品种：荷斯坦牛和更赛牛。
他在订单中用一个长为 N 的字符串来指定奶牛，其中的字符为 H（表示荷斯坦牛）或 G（表示更赛牛）。
不幸的是，当这些奶牛到达他的农场，他给她们排队时，她们的品种组成的字符串与原先的不同。
我们将这两个字符串称为 A 和 B，其中 A 是 Farmer John 原先想要的品种字符组成的字符串，B 是他的奶牛们到达时组成的字符串。
Farmer John 并没有简单地检查重新排列 B 中的奶牛是否能得到 A，而是请他的远房亲戚 Ben 利用他的科学才华来解决这一问题。
经过数月的研究，Ben 发明了一台不同寻常的机器：奶牛品种转换机3000，能够选择任意奶牛组成的子串并反转她们的品种：在这个子串中的所有 H 变为 G，所有 G 变为 H。
Farmer John 想要求出将他当前的序列 B 变为他本来订购时想要的 A 需要使用这台机器的最小次数。
然而，Ben 的疯狂的科学家技能并不会处理开发奇异机器以外的事，所以你需要帮助 Farmer John 解决这个计算难题。

输入格式
输入的第一行包含 N，以下两行包含字符串 A 和 B。每个字符串均包含 N 个字符，字符均为 H 和 G 之一。

输出格式
输出将 B 变为 A 需要使用机器的最小次数。

数据范围
1≤N≤1000
输入样例：
7
GHHHGHH
HHGGGHH
输出样例：
2
    
样例解释
首先，FJ 可以仅改变第一个字符组成的子串，将 B 变为 GHGGGHH。
然后，他可以改变由第三和第四个字符组成的子串，得到 A。
当然，还存在其他有效的执行两次操作的方案。

题解一：

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

逐个判断A和B对应位置字符是否不同，注意处理连续的相反子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
const int N = 1005;
char a[N],b[N];

int main(){
    int n;
    cin >> n;
    
    for (int i = 0;i < n;i ++) cin >> a[i];
    for (int i = 0;i < n;i ++) cin >> b[i];
    
    int ans = 0;
    for (int i = 0;i < n - 1;i ++){
        if (a[i] != b[i] && a[i+1] == b[i+1]) ans ++;
    }
    // 特判最后一个位置
    if (a[n-1] != b[n-1]) ans ++;
    cout << ans;
    return 0;
}

题解二：y总的双指针写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
const int N = 1005;
char a[N],b[N];

int main(){
    int n;
    cin >> n;
    
    for (int i = 0;i < n;i ++) cin >> a[i];
    for (int i = 0;i < n;i ++) cin >> b[i];
    
    int ans = 0;
    for (int i = 0;i < n;i ++){
        if (a[i] != b[i]){
            int j = i + 1;
            while (j < n && a[j] != b[j]) j ++;
            ans ++;
            i = j;
         }
    }
    cout << ans;
    return 0;
}

T3—1660. 社交距离 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
27
28
29
30
31
32
由于高传染性的牛传染病 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≤10^6
输入样例：
6
7 1
1 1
15 1
3 1
10 0
6 1
输出样例：
3
    
样例解释
在这个例子中，我们知道 R<3，否则位于位置 7 的奶牛会传染给位于位置 10 的奶牛。
所以，至少 3 头奶牛初始时已被感染：位于位置 1 和 3 的两头奶牛中的一头，位于位置 6 和 7 的两头奶牛中的一头，以及位于位置 15 的奶牛。

不会。

根据上面的样例解释中的提示，首先求出传播半径的上限，也就是两头感染状态相反的牛间的距离的最小值。

接下来要保证传染母体的数量最少，需要控制传播半径取上限-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 <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define fi first
#define se second
const int N = 1005;
PII q[N];

int main(){
    int n;
    cin >> n;
    
    for (int i = 0;i < n;i ++) cin >> q[i].fi >> q[i].se;
    
    sort(q,q + n);
    
    int r = 1e7;
    for (int i = 0;i < n - 1;i ++){ // 求传播半径上限
        if (q[i].se != q[i+1].se) r = min(r,q[i+1].fi - q[i].fi);
    }
    
    r --;
    
    int ans = 0;
    for (int i = 0;i < n;i ++){ // 双指针求连通块数量
        if (q[i].se){
            int j = i + 1;
            while (j < n && q[j].se && q[j].fi - q[j-1].fi <= r) j ++;
            ans ++;
            i = j - 1;
        }
    }
    cout << ans;
    return 0;
}

T4—3347. 菊花链

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
每天，作为她绕农场行走的一部分，奶牛 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) 所对应的照片也存在平均的花。

只能想到暴力枚举。

根据本题数据量，O(n^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
28
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int q[N];

int main(){
    int n;
    cin >> n;
    
    for (int i = 0;i < n;i ++) cin >> q[i];
    
    int ans = 0;
    for (int i = 0;i < n;i ++)
        for (int j = i,s = 0;j < n;j ++){
            s += q[j];
            int cnt = j - i + 1;
            if (s % cnt == 0){
                for (int k = i;k <= j;k ++){
                    if (q[k] == s / cnt){
                        ans ++;break;
                    }
                }
            }
        }
    
    cout << ans;
    return 0;
}

哈希表优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int q[N];

int main(){
    int n;
    cin >> n;
    
    for (int i = 0;i < n;i ++) cin >> q[i];
    
    int ans = 0;
    for (int i = 0;i < n;i ++){
        unordered_set<int> hash;
        for (int j = i,s = 0;j < n;j ++){
            s += q[j];
            hash.insert(q[j]);
            int cnt = j - i + 1;
            if (s % cnt == 0 && hash.count(s / cnt)) ans ++;
        }
    }
    cout << ans;
    return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！