Martian148's blog
martian148
2024-08-02
目录

AtCoder Beginner Contest 346 A-G 题解

AtCoder Beginner Contest 346 (opens new window)

# A - Adjacent Product

# Question

给你 NN 个整数 A1,A2,⋯,ANA_1, A_2, \cdots, A_N 。同时，定义 Bi=Ai×Ai+1(1≤i≤N−1)B_i = A_i \times A_{i+1}\ (1 \leq i \leq N-1)

按此顺序打印 B1,B2,⋯,BN−1B_1, B_2, \cdots, B_{N-1}

# Solution

按照题意模拟

# Code

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i < n; i++)
        cout << a[i] * a[i + 1] << " ";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

# B - Piano

# Question

有一个无限长的钢琴键盘。在这个键盘中，是否存在一个由 WW 个白键和 BB 个黑键组成的连续部分？

假设 SS 是由无限重复的字符串 wbwbwwbwbwbw 构成的字符串。

在 SS 中，是否存在一个由 WW 次出现的 w 和 BB 次出现的 b 组成的子串？

# Solution

暴力把 SS 复制多次，然后 n2n^2 找子串验证

应该还有更优的解法，只是串长实在太短，怎么写都行

# Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    int W, B; cin >> W >> B;
    string s, p = "wbwbwwbwbwbw";
    while (s.size() < 2000) s += p;
    int n = s.size(); s = " " + s; 
    vector<int> sumb(n + 1), sumw(n + 1);
    for (int i = 1; i <= n; i++) {
        sumb[i] = sumb[i - 1] + (s[i] == 'b');
        sumw[i] = sumw[i - 1] + (s[i] == 'w');
    }
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++) {
            int nw = sumw[j] - sumw[i - 1], nb = sumb[j] - sumb[i - 1];
            if (W == nw && B == nb) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    cout << "No" << endl;
    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

# C - Σ

# Question

给你一个长度为 NN 的正整数序列 AA 和一个正整数 KK

求在 11 与 KK 之间，未出现在序列 AA 中的整数之和

# Solution

先算 1∼K1\sim K 中所有数的和，然后把在 AA 中的减去

注意 AA 中的 AiA_i 可能不在 1∼K1\sim K 这个范围内

# Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k; cin >> n >> k;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    int ans = k * (k + 1) / 2;
    for (int &x : a) {
        if (x <= k)
            ans -= x;
    }
    cout << ans << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# D - Gomamayo Sequence

# Question

给你一个长度为 NN 的字符串 SS ，它由 0 和 1 组成

长度为 NN 的字符串 TT 由 0 和 1 组成，当且仅当它满足以下条件时，它是一个好字符串：

  • 恰好有一个整数 ii 使得 1≤i≤N−11 \leq i \leq N - 1 和 TT 的第 ii 个字母 和第 (i+1)(i + 1) 个字符相同

对于每个 i=1,2,…,Ni = 1,2,\ldots, N ，您可以选择是否执行一次下面的操作：

  • 如果 SS 的 ii 个字符是 0，则将其替换为 1，反之亦然。如果执行此操作，代价是 CiCi

求使 SS 成为一个好字符串所需的最小总成本

# Solution

考虑到有且仅有一个 ii ，满足 Ti=Ti+1T_i = T_{i+1}，不妨假设 Ti=Ti+1=1T_i=T_{i+1}=1，那么可知 Ti−1=0,Ti+2=0T_{i-1}=0,T_{i+2}=0

ii 前面和 i+1i+1 后面都是 0101 交替的，我们就可以记录一个交错的前缀和

定义 pre[i][0]pre[i][0] 表示第 ii 个字母，前面都是 0101 交替的，且第 ii 个字母为 0 花费的最小代价，pre[i][1]pre[i][1] 表示第 ii 个字母，前面都是 0101 交替的，且第 ii 个字母为 1 花费的最小代价

同理，suf[i][0]suf[i][0] 表示第 ii 个字母，后面都是 0101 交替的，且第 ii 个字母为 0 花费的最小代价

如何计算 prepre ？交错着刷前缀和就好了

for (int i = 1; i <= n; i++) {
    pre[i][0] = pre[i - 1][1] + c[i] * (s[i] != '0');
    pre[i][1] = pre[i - 1][0] + c[i] * (s[i] != '1');
}
1
2
3
4

最后，关于 Ti=Ti+1T_i=T_{i+1} 只有 00，11 两种情况，分别枚举一次即可

# Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    string s; cin >> s; s = " " + s;
    vector<ll> c(n + 1, 0);
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    
    vector<vector<ll> > pre(n + 2 , vector<ll>(2, 0)); auto lst = pre;
    for (int i = 1; i <= n; i++) {
        pre[i][0] = pre[i - 1][1] + c[i] * (s[i] != '0');
        pre[i][1] = pre[i - 1][0] + c[i] * (s[i] != '1');
    }
    for (int i = n; i > 0; i--) {
        lst[i][0] = lst[i + 1][1] + c[i] * (s[i] != '0');
        lst[i][1] = lst[i + 1][0] + c[i] * (s[i] != '1');
    }

    ll ans = INF;

    //00
    for (int i = 1; i < n; i++) {
        ll now = c[i] * (s[i] != '0') + c[i + 1] * (s[i + 1] != '0');
        now += pre[i - 1][1] + lst[i + 2][1];
        ans = min(ans, now);
    }
    //11
    for (int i = 1; i < n; i++) {
        ll now = c[i] * (s[i] != '1') + c[i + 1] * (s[i + 1] != '1');
        now += pre[i - 1][0] + lst[i + 2][0];
        ans = min(ans, now);
    }
    cout << ans << '\n';
    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

# E - Paint

# Question

有一个行数为 HH 列数为 WW 的网格。初始时，所有单元格都涂有颜色 00

您将按照 i=1,2,…,Mi = 1, 2, \ldots, M 的顺序执行以下操作。

  • 如果是 Ti=1T_i = 1 ，则使用颜色 XiX_i 重新绘制 AiA_i 行中的所有单元格。

  • 如果是 Ti=2T_i = 2 ，则使用颜色 XiX_i 重新绘制 AiA_i 列中的所有单元格

完成所有操作后，针对网格中存在的每种颜色 ii ，找出被涂上颜色 ii 的单元格数量

# Solution

显然，最后一次刷在墙上的颜色肯定存在，第二次如果和第一次方向不同，那么中间会有一个格子是第一次刷的颜色

按照这个想法，我们用 map 记录有多少行被刷了颜色，以及有多少列刷了颜色

倒叙处理，这一行/列 在这一次刷中保留了多少颜色，取决与有多少 列/行 还没有刷过

# Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
signed main() {
    freopen ("E.in","r",stdin);
    ios::sync_with_stdio(0); cin.tie(0);
    int H, W, N; cin >> H >> W >> N;
    vector<int> A(N + H), X(N + H), T(N + H); 
    N = N + H;
    for (int i = 0; i < H; i++) {
        T[i] = 1; A[i] = i + 1; X[i] = 0;
    }
    for (int i = H; i < N; i++)
        cin >> T[i] >> A[i] >> X[i];
    map<int,pii> col, row;
    for (int i = N - 1; i>= 0; i--) {
        if (T[i] == 1) {
            if (row.count(A[i])) continue;
            row[A[i]] = {W - col.size(), X[i]};
        }
        else {
            if (col.count(A[i])) continue;
            col[A[i]] = {H - row.size(), X[i]};
        }
    }
    map<int,int> mp;
    for (auto &r : row) {
        int num = r.second.first, c = r.second.second;
        if (!mp.count(c))
            mp[c] = 0;
        mp[c] += num; 
    }
    for (auto &r : col) {
        int num = r.second.first, c = r.second.second;
        if (!mp.count(c))
            mp[c] = 0;
        mp[c] += num; 
    }

    int ans = 0;
    for (auto &x : mp) 
        ans += x.second != 0;
    cout << ans << '\n';
    for (auto &x : mp) {
        if (x.second == 0) continue;
        cout << x.first << " " << x.second << '\n';
    }
    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
46
47
48
49
50

# F - SSttrriinngg in StringString

# Question

对于长度为 nn 的字符串 XX

  • 让 f(X,k)f(X,k) 表示重复 kk 次字符串 XX 得到的字符串
  • g(X,k)g(X,k) 表示依次重复 kk 次第一个字符、第二个字符、 …\dots 、 XX 的 nn 个字符得到的字符串

给你一个正整数 NN 和字符串 SS 和 TT 。求最大的非负整数 kk ，使得 g(T,k)g(T,k) 是 f(S,N)f(S,N) 的子序列

注意，根据定义， g(T,0)g(T,0) 总是 f(S,N)f(S,N) 的子序列

# Solution

答案满足单调性，也就是说，如果 g(T,k)g(T,k) 是 f(S,N)f(S,N) 的子序列的话，对于所有的 k′≤kk'\le k ，g(T,k′)g(T,k') 也是 f(S,N)f(S,N) 的子序列

所以我们二分最后的答案 kk，考虑如何 check

提前预处理出 SS 字符出现的次数 以及 每个字符的第 ii 次出现的位置

记录此时枚举 g(S,N)g(S,N) 的第 iteriter 个字母

对于 TT 上的每个字母，都需要重复 kk 次，那么看需要多少整块的 SS 以及最后一块 SS 上的几个字母

按照题意模拟即可

# Code

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

int main() {
    ll n;
    string S, T;
    cin >> n >> S >> T;
    int s = S.size(), t = T.size();
    vector<vector<int> > pos(26);
    for (int i = 0; i < s * 2; i++) 
        pos[S[i % s] - 'a'].push_back(i);
    vector<vector<int> >  pre(s + 1, vector<int>(26));
    for (int i = 0; i < s; i++) {
        pre[i + 1] = pre[i];
        pre[i + 1][S[i] - 'a']++;
    }
    vector<int> cnt(26, 0);
    for (int i = 0; i < s; i++)
        cnt[S[i] - 'a']++;
    ll le = 0, ri = INF;
    auto check = [&] (ll x) -> bool {
        ll iter = 0; // 表示s的长度
        for (int i = 0; i < t; i++) {
            int c = T[i] - 'a';
            if (cnt[c] == 0) return false;
            ll r = (x - 1) % cnt[c] + 1;
            ll q = (x - r) / cnt[c];
            if (q > INF / s) return false;
            iter += q * s;
            int nx = pos[c][pre[iter % s][c] + r - 1]; // 从iter % s开始的第r个c 的位置
            iter += nx - iter % s + 1;
            if (iter > n * s) return false;
        }
        return true;
    };

    while (le + 1 < ri) {
        ll mid = (le + ri) >> 1;
        if (check(mid)) le = mid;
        else ri = mid;
    }
    cout << le << endl;
    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
46

# G - Alone

# Question

给你一个整数序列 AA 。

求满足以下条件的整数对 (L,R)(L, R) 的个数：

  • 1≤L≤R≤N1 \leq L \leq R \leq N
  • 有一个数字在 AL,AL+1,…,ARA_L, A_{L + 1}, \ldots, A_R 中恰好出现一次。更确切地说，有一个整数 xx 恰好有一个整数 ii 满足 Ai=xA_i = x 和 L≤i≤RL \leq i \leq R

# Solution

对于一个 ii，提前预处理出 pre[i]pre[i] 和 nxt[i]nxt[i]，分别表示与 a[i]a[i] 相同的前一个和后一个出现的位置

显然，一个区间的左端点可以在 (pre[i],i](pre[i],i] ，一个区间的右端点可以是 [i,nxt[i])[i,nxt[i])

例如 2 2 1 2 1 ，当 i=3,a[i]=1i = 3,a[i]=1

那么此时的 pre[i]=0,nxt[i]=5pre[i]=0,nxt[i]=5

(1,3),(1,4),(2,3),(2,4),(3,3),(3,4)(1,3),(1,4),(2,3),(2,4),(3,3),(3,4) 都是合法的区间

对于一个 ii 可以生成这么多区间，显然最后的答案是对每个 ii 找区间，然后去重

关键是如何去重？ 我们发现一个 ii 生成的区间都是连续的，也就是说，如果把二元组看成二维平面上的一个坐标，那么一个 ii 生成的区间对应的是二维平面上的一个矩形

而矩形的左下角是 (pre[i]+1,i)(pre[i]+1,i) 右上角是 (i,nxt[i]−1)(i,nxt[i]-1)

显然，这个问题就转化为二维平面上 nn 个矩形的交集面积

利用扫描线算法就可以解决

# Code

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

struct Segment_Tree {
    int n;
    vector<int> sum, tag;
    Segment_Tree (int n) {
        this->n = n;
        tag.assign(n << 4, 0);
        sum.assign(n << 4, 0);
    }


    void update (int x, int l, int r, int ql, int qr, int val) {
        if (ql <= l && r <= qr) {
            tag[x] += val;
            if (tag[x]) sum[x] = r - l + 1;
            else sum[x] = sum[x << 1] + sum[x << 1 | 1];
            return ;
        }
        int mid = (l + r) >> 1;
        if (ql <= mid) update(x << 1, l, mid, ql, qr, val);
        if (qr > mid) update(x << 1 | 1, mid + 1, r, ql, qr, val);
        if (!tag[x]) sum[x] = sum[x << 1] + sum[x << 1 | 1];
    }

};

struct Line {
    int l, r, x, op;
    Line (int l, int r, int x, int op) : l(l), r(r), x(x), op(op) {}
    bool operator < (const Line &rhs) {
        if (x == rhs.x) return op < rhs.op;
        return x < rhs.x;
    }
};

int main() {
    freopen ("G.in", "r", stdin);
    int n; cin >> n;
    vector<int> a(n + 1);

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    vector<int> pre(n + 1, 0), nxt(n + 1, n + 1), pos(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        pre[i] = pos[a[i]];
        pos[a[i]] = i;
    }
    pos.assign(n + 1, n + 1);
    for (int i = n; i; i--) {
        nxt[i] = pos[a[i]];
        pos[a[i]] = i;
    }
    
    vector<Line> lines;
    for (int i = 1; i <= n; i++) {
        lines.emplace_back(i, nxt[i] - 1, pre[i], 1);
        lines.emplace_back(i, nxt[i] - 1, i, -1);
    }
    
    Segment_Tree T(n);
    ll ans = 0;
    sort(lines.begin(), lines.end());
    for (int i = 0; i < lines.size() - 1; i++) {
        T.update(1, 1, n, lines[i].l, lines[i].r, lines[i].op);
        ans += 1ll * T.sum[1] * (lines[i + 1].x - lines[i].x);
    }
    cout << ans << endl;
    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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
上次更新: 2025/04/08, 18:03:31
AtCoder Beginner Contest 345 A-F 题解
AtCoder Beginner Contest 347 A-G 题解

← AtCoder Beginner Contest 347 A-G 题解→

最近更新
01
Java基础语法
05-26
02
开发环境配置
05-26
03
pink 老师 JavaScript 学习笔记
05-26
更多文章>
Theme by Vdoing | Copyright © 2024-2025 Martian148 | MIT License