grant's Blog

记录生活中的点点滴滴

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

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

第二周

2022.1.10—1987. 粉刷栅栏

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
农夫约翰发明了一种绝妙的方法来粉刷牛棚旁边的长栅栏（把栅栏想象成一维的数轴）。
他只需要在他最喜欢的奶牛贝茜身上挂一个刷子，然后在一旁悠闲的喝凉水就行了。
贝茜沿着栅栏来回走动时，会将她走过的栅栏部分涂上油漆。
贝茜从栅栏上的位置 0 处开始，共进行 N 次移动。
移动可能形如 10 L，表示向左移动 10 单位距离，也可能形如 15 R，表示向右移动 15 单位距离。
给定贝茜的 N 次移动列表，约翰想知道至少被涂抹了 2 层油漆的区域的总长度。
整个行进过程中，贝茜距离出发地的距离不会超过 10^9。

输入格式
第一行包含一个整数 N。
接下来 N 行，每一行包含一个行动指令，诸如 10 L 或 15 R。

输出格式
输出至少被涂抹了 2 层油漆的区域的总长度。

数据范围
1≤N≤10^5
整个行进过程中，贝茜距离出发地的距离不会超过 10^9。
每次指令移动距离的取值范围是 [1,2×10^9]。

输入样例：
6
2 R
6 L
1 R
8 L
1 R
2 R
输出样例：
6
样例解释
共有 6 单位长度的区域至少被涂抹 2 层油漆。
这些区域为 (−11,−8),(−4,−3),(0,2)。

一看题目就能大概推测出是差分问题。

没有离散化之前能过一半数据。数据太大就过不了。

代码参考： https://www.acwing.com/problem/content/submission/code_detail/9849690/。

数据范围太大，所以正解是：差分+离散化，或者差分+map。

经典的差分算法是维护每个整数点的值，本题需要维护每个单位长度区间的值。

image-20220111111947141

y总代码：差分+map。

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 <cstdio>
#include <algorithm>
#include <map>
using namespace std;
int n;

int main(){
    map<int,int> m;
    scanf("%d",&n);
    
    int cur = 0,num;char op;
    while (n--){
        scanf("%d %c",&num,&op);
        if (op == 'R'){
            m[cur] ++;
            m[cur+num-1+1] --;
            cur += num;
        }
        else{
            m[cur-num] ++;
            m[cur] --;
            cur -= num;
        }
    }
    
    int res = 0,sum = 0,last;
    for (auto &[k,v] : m){ // 离散化的前缀和
        if (sum > 1) res += k-last;
        sum += v;
        last = k;
    }
    cout << res;
    return 0;
}

我的代码：差分+离散化。代码要长不少，还是STL香。但是STL可能卡常数。

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 2e5+5;
#define pu push_back
#define fi first
#define se second
typedef pair<int,int> PII;
int b[N]; // 差分数组
vector<int> alls;
vector<PII> adds;

// 二分求出输入的坐标x的离散化下标
int find(int x){// 找到第一个大于等于x的位置
    int l = 0,r = alls.size()-1;
    while (l < r){
        int mid = l+r>>1;
        if (alls[mid] < x) l = mid+1;
        else r = mid;
    }
    return r + 1;// 映射到1, 2, ...n，+1避免前缀和的下标问题
}

int main(){
    int n;
    scanf("%d",&n);
    
    int cur = 0,num;char op;
    while (n--){
        scanf("%d %c",&num,&op);
        if (op == 'R'){
            adds.pu({cur,cur+num});
            alls.pu(cur);
            alls.pu(cur+num); // 注意alls存的是差分数组需要修改的下标，不要加1减1
            cur += num;
        }
        else{
            adds.pu({cur-num,cur});
            alls.pu(cur-num);
            alls.pu(cur);
            cur -= num;
        }
    }
    
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());
    
    // 处理差分
    for (auto &it : adds){
        int x = find(it.fi),y = find(it.se);
        b[x] ++,b[y] --;
    }
    
    int sum = 0,res = 0,last;
    for (auto &it : alls){
        int k = find(it);
        if (sum > 1) res += it - last;
        sum += b[k];
        last = it;
    }
    
    cout << res;
    return 0;
}

2022.1.11—1978. 奶牛过马路

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
每天，农夫约翰的 N 头奶牛都会穿过农场中间的马路。
考虑约翰的农场在二维平面的地图，马路沿水平方向延伸，马路的一侧由直线 y=0 描述，另一侧由直线 y=1 描述。
奶牛 i 从马路一侧的位置 (ai,0) 沿直线过马路到达另一侧的位置 (bi,1)。
所有 ai 互不相同，所有 bi 互不相同。
尽管他的奶牛们行动敏捷，他还是担心行动路径交叉的两头奶牛在过马路时发生碰撞。
约翰认为，如果一头奶牛的行动路径没有跟其他任何奶牛的行动路径相交，则该奶牛是安全的。
请帮助约翰计算安全奶牛的数量。

输入格式
第一行包含整数 N。
接下来 N 行，每行包含两个整数 ai,bi，用来描述一头牛的行动路径。

输出格式
输出安全奶牛的数量。

数据范围
1≤N≤10^5,
−10^6≤ai,bi≤10^6
输入样例：
4
-3 4
7 8
10 16
3 9
输出样例：
2
样例解释
第一头牛和第三头牛的行动路线不与其他奶牛的路线相交。
第二头牛和第四头牛的行动路线相交。

和提高课一道题《友好城市》题目背景相同，但考察点不一样。

本题难度其实并不大，关键是能想到前缀最大值和后缀最小值这两个不等式关系。

image-20220114210644957

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
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e5+5;
int n;
PII a[N];
int smax[N],smin[N];

int main(){
    cin >> n;
    
    int x,y;
    for (int i = 1;i <= n;i ++){
        cin >> x >> y;
        a[i] = {x,y};
    }
    
    sort(a+1,a+n+1);
    
    // 类似前缀和的预处理
    smax[0] = -1e8,smin[n+1] = 1e8;
    for (int i = 1;i <= n;i ++){
        smax[i] = max(smax[i-1],a[i].second);
    }
    for (int i = n;i >= 1;i --){
        smin[i] = min(smin[i+1],a[i].second);
    }
    
    int res = 0;
    for (int i = 1;i <= n;i ++){
        if (smax[i-1] < a[i].second && smin[i+1] > a[i].second)
            res ++;
    }
    
    cout << res;
    return 0;
}

2022.1.12—1969. 品种邻近

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
农夫约翰的 N 头奶牛排成一排，每头奶牛都用其品种 ID 进行描述。
如果两头相同品种的牛靠得太近，它们就会吵架。
具体的说，如果同一品种的两头奶牛在队列中的位置相差不超过 K，我们就称这是一对拥挤的牛。
请计算品种 ID 最大的拥挤奶牛对的品种 ID。

输入格式
第一行包含两个整数 N 和 K。
接下来 N 行，每行包含一个整数表示队列中一头奶牛的品种 ID。

输出格式
输出品种 ID 最大的拥挤奶牛对的品种 ID。
如果不存在拥挤奶牛队，则输出 −1。

数据范围
1≤N≤50000,
1≤K<N,
品种 ID 范围 [0,10^6]。

输入样例：
6 3
7
3
4
2
3
4
输出样例：
4
样例解释
一对品种 ID 为 3 的奶牛以及一对品种 ID 为 4 的奶牛属于拥挤奶牛对。
所以，最大拥挤奶牛对的品种 ID 为 4。

简单题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6+5;
int n,k;
int st[N];

int main(){
    cin >> n >> k;
    
    int a,res = -1;
    for (int i = 1;i <= n;i ++){
        cin >> a;
        if (st[a] && i - st[a] <= k) res = max(res,a);
        st[a] = i;
    }
    
    cout << res;
    return 0;
}

2022.1.13—1960. 闪烁

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 个灯泡围成一圈，编号为 0∼N−1。
奶牛对这个新吊灯非常着迷，并且喜欢玩以下游戏：
对于第 i 个灯泡，如果在 T−1 时刻，它左侧的灯泡（当 i>0 时，为第 i−1 个灯泡；当 i=0 时，为第 N−1 个灯泡）是开着，那么在 T 时刻，就切换这个灯泡的状态。
这个游戏将持续 B 单位时间。
给定灯泡的初始状态，请确定在 B 单位时间后，它们的最终状态。

输入格式
第一行包含两个整数 N 和 B。
接下来 N 行，按顺序描述每个灯泡的初始状态，每行包含一个整数 1 （表示开）或 0（表示关）。

输出格式
共 N 行，按顺序每行输出一个灯泡的最终状态。

数据范围
3≤N≤16,
1≤B≤10^15
输入样例：
5 6
1
0
0
0
0
输出样例：
1
1
1
0
1
样例解释
灯泡状态如下：
时刻 T=0: 1 0 0 0 0
时刻 T=1: 1 1 0 0 0
时刻 T=2: 1 0 1 0 0
时刻 T=3: 1 1 1 1 0
时刻 T=4: 1 0 0 0 1
时刻 T=5: 0 1 0 0 1
时刻 T=6: 1 1 1 0 1

需要用到二进制的状态压缩，用十进制数来存二进制数。

以S1和S2为例，假设S1在S2的左边，那么T时刻S2的状态应该是S2^S1。（1^x = !x，0^x = x）

我们发现 B 的范围远远大于灯泡的所有状态数量（2^N），所以当状态转移 B 次时，必然会形成一个环。

image-20220114213829732

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
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1 << 16;
int n;
LL m; // 注意开LL
int p[N]; // 维护当前状态到初始状态的距离

int update(int state){ // 灯泡更新操作
    int res = 0;
    for (int i = 0;i < n;i ++){
        // 修改第i位灯泡的状态，取决于第i-1位灯泡的状态
        int x = state >> i & 1; // 取第i位数字，对应编号i的灯泡
        int y = state >> ((i-1+n) % n) & 1;
        res |= (x^y) << i;
    }
    return res;
}

void print(int state){ // 输出状态
    for (int i = 0;i < n;i ++){ // 不要搞反顺序
        cout << (state >> i & 1) << '\n'; // 最早进来的最早出去
    }
}

int main(){
    cin >> n >> m;
    
    int state = 0,x; // state记录灯泡状态，状态压缩
    for (int i = 0;i < n;i ++){
        cin >> x;
        state |= (x << i); // 最早输入的灯泡记录在个位，对应二进制第0位
    }
    
    memset(p,-1,sizeof p);
    p[state] = 0;
    
    for (int i = 1; ;i ++){
        state = update(state); // 每走一步更新状态
        if (i == m){
            print(state);break;
        }
        else if (p[state] == -1) p[state] = i; // 记录距离
        else{
            int len = i - p[state]; // 找到循环节的长度
            int r = (m - i) % len; // 剩余距离
            while (r--) state = update(state);
            print(state);
            break;
        }
    }
    
    return 0;
}

2022.1.14—1952. 金发姑娘和 N 头牛

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
你可能听过关于金发姑娘和三只熊的经典故事。
然而，鲜为人知的是，金发姑娘最终成了一个农民。
在她的农场中，她的牛棚里有 N 头奶牛。
不幸的是，她的奶牛对温度相当敏感。
对于奶牛 i，使其感到舒适的温度为 Ai…Bi。
如果金发姑娘将牛棚的恒温器的温度 T 设置为 T<Ai，奶牛就会觉得冷，并会产出 X 单位的牛奶。
如果她将恒温器的温度 T 设置在 Ai≤T≤Bi，奶牛就会感到舒适，并会产出 Y 单位的牛奶。
如果她将恒温器的温度 T 设置为 T>Bi，奶牛就会觉得热，并会产出 Z 单位的牛奶。
正如所期望的那样，Y 的值始终大于 X 和 Z。
给定 X,Y,Z 以及每头奶牛感到舒适的温度范围，请计算通过合理设定恒温器温度，金发姑娘可获得的最大产奶量。
恒温器温度可设置为任何整数。

输入格式
第一行包含四个整数 N,X,Y,Z。
接下来 N 行，每行包含两个整数 Ai 和 Bi。

输出格式
输出可获得的最大产奶量。

数据范围
1≤N≤20000,
0≤X,Y,Z≤1000,
0≤Ai≤Bi≤10^9
输入样例：
4 7 9 6
5 8
3 4
13 20
7 10
输出样例：
31
样例解释
金发姑娘可以将恒温器温度设置为 7 或 8，这样会让奶牛 1 和 4 感到舒适，奶牛 2 感到热，奶牛 3 感到冷。
共可获得 31 单位牛奶。

考察差分和离散化，思路没想到。和本周第一题一样的知识点。

算法抽象建模能力还要锻炼。

看看数据范围，发现坐标个数远小于坐标范围，需要离散化处理。

image-20220115140918970

对于每个温度区间，(-INF,L)对答案的贡献是X， [L,R]对答案的贡献是Y，(R,+INF)对答案的贡献是Z。

差分+map：

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
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
const int INF = 1e10;
int n,x,y,z;

int main(){
    map<int,int> b;
    b[-INF] = 0,b[INF] = 0;
    
    cin >> n >> x >> y >> z;
    
    int l,r;
    while (n--){
        cin >> l >> r;
        b[-INF] += x;
        b[l] += y - x;
        b[r+1] += z - y;
        b[INF] -= z;
    }
    
    int res = 0,sum = 0;
    for (auto &[k,v] : b){
        sum += v;
        res = max(res,sum);
    }
    cout << res;
    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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define pu push_back
const int INF = 2e9,N = 20005;
int n,x,y,z;
int b[2*N],l[N],r[N];
vector<int> alls;

int find(int x){
    int l = 0,r = alls.size()-1;
    while (l < r){
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r;
}

int main(){
    cin >> n >> x >> y >> z;
    
    alls.pu(-INF),alls.pu(INF);
    for (int i = 0;i < n;i ++){
        cin >> l[i] >> r[i];
        alls.pu(l[i]),alls.pu(r[i]+1); // 注意细节
    }
    
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());
    
    for (int i = 0;i < n;i ++){
        int L = find(l[i]),R = find(r[i]+1); // 注意细节
        b[0] += x,b[L] += y - x,b[R] += z - y,b[alls.size()-1] -= z;
    }
    
    int res = 0,sum = 0;
    for (int i = 0;i < alls.size();i ++){
        sum += b[i];
        res = max(res,sum);
    }
    cout << res;
    return 0;
}

2022.1.15—1945. 奶牛棒球

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 头奶牛排成一排，每头奶牛都位于数轴中的不同位置上。
它们正在练习投掷棒球。
农夫约翰观看时，观察到一组三头牛 (X,Y,Z) 完成了两次成功的投掷。
牛 X 把球扔给她右边的牛 Y，然后牛 Y 把球扔给她右边的牛 Z。
约翰指出，第二次投掷的距离不少于第一次投掷的距离，也不超过第一次投掷的距离的两倍。
请计算共有多少组牛 (X,Y,Z) 可能是约翰所看到的。

输入格式
第一行包含整数 N。
接下来 N 行，每行描述一头牛的位置。

输出格式
输出奶牛三元组 (X,Y,Z) 的数量。
(X,Y,Z) 需满足，Y 在 X 的右边，Z 在 Y 的右边，并且从 Y 到 Z 的距离在 [XY,2XY] 之间，其中 XY 表示从 X 到 Y 的距离。

数据范围
3≤N≤1000,
奶牛所在的位置坐标范围 [0,10^8]。

输入样例：
5
3
1
10
7
4
输出样例：
4
样例解释
四个可能的奶牛三元组为：1−3−7,1−4−7,4−7−10,1−4−10。

不会。

n≤1000 => O(n$^2$)，O($n^2logn$)。数据范围反推时间复杂度。

想法：可以枚举两个数，第三个数用二分处理。

双指针的适用条件：当一个指针往一个方向移动时，另一指针也单调往一个方向移动。

image-20220117220104406

上图中<= 3*y-2*x的最大数也就是> 3*y-2*x的最小数的前一个数。

算法一：枚举+手写二分。

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>
using namespace std;
const int N = 1e3+5;
int n,q[N];

int main(){
    cin >> n;
    
    for (int i = 0;i < n;i ++) cin >> q[i];
    
    sort(q,q + n);
    
    int res = 0;
    for (int i = 0;i + 2 < n;i ++)
        for (int j = i + 1;j + 1 < n;j ++){
            int x = q[i],y = q[j];
            int a = 2*y-x,b = 3*y-2*x;

            int l = j+1,r = n-1;
            while (l < r){
                int mid = l+r >> 1;
                if (q[mid] < a) l = mid + 1;
                else r = mid;
            }
            a = l;
            if (q[a] < 2*y-x) continue; // 注意一定加上判断条件，否则不存在的答案也计算了
            
            l = j+1,r = n-1;
            while (l < r){
                int mid = (l+r+1) >> 1;
                if (q[mid] > b) r = mid - 1;
                else l = mid;
            }
            b = l;
            if (q[b] > 3*y-2*x) continue;
            
            res += b-a+1;
        }
    
    cout << res;
    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 <iostream>
#include <algorithm>
using namespace std;
const int N = 1e3+5;
int n,q[N];

int main(){
    cin >> n;
    
    for (int i = 0;i < n;i ++) cin >> q[i];
    
    sort(q,q + n);
    
    int res = 0;
    for (int i = 0;i + 2 < n;i ++)
        for (int j = i + 1,l = j + 1,r = j + 1;j + 1 < n;j ++){
            while (l < n && q[j]-q[i] > q[l]-q[j]) l ++; // 双指针注意单调性
            while (r < n && q[r]-q[j] <= 2*(q[j]-q[i])) r ++;
            res += r-l;
        }
    
    cout << res;
    return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！