Atcoder Beginner Contest 378 题解

发表于 更新于 分类于 阅读次数： 本文字数： 6.5k
最急着打完看S14决赛的一集。

AtCoder Beginner Contest 378 题解

A

题意

给定四个数，都为1～4，若有两个相同的数就得一分，求得几分。

题解

随便做。

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;
#define int long long

void solve() {
    vector<int> a(4);
    map<int, int> mp;
    for (int i = 0; i < 4; i++) {
        cin >> a[i];
        mp[a[i]]++;
    }
    int ans = 0;
    for (int i = 1; i <= 4; i++) {
        ans += mp[i] / 2;
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B

题意

给定\(n\)种垃圾，对于每种垃圾给定模数\(m_i\)和余数\(r_i\)，要求天数在模掉模数后余数等于给定余数时才可收集。现在给定\(q\)次询问，每次给定垃圾种类和天数，求从这天开始第一次能收集该垃圾的天数。

题解

天数自然等于\(km_i + r_i\),即\(k = \lceil (d-r_i)/m_i\rceil\)找到对应的\(k\)后按公式求即可。\(k\)的具体求法应该为：当前天数减去余数后对模数上取整。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
    }
    int q;
    cin >> q;
    while (q--) {
        int i, d;
        cin >> i >> d;
        i--;
        int k = (d - a[i].second + a[i].first - 1) / a[i].first * a[i].first +
                a[i].second;
        cout << k << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C

题意

给定一个数组，从左到右对于每一个数，找到上一个出现当前数的位置，若不存在为-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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n, -1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        if (mp[a[i]]) {
            b[i] = mp[a[i]];
        }
        mp[a[i]] = i + 1;
    }
    for (int i = 0; i < n; i++) {
        cout << b[i] << " \n"[i == n - 1];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D

题意

给定一个由“.”和“#”组成的矩阵，“.”代表当前位置为空，否则当前位置存在阻碍物。现在给定一个步数\(k\)，求有多少条不同路径可以在该矩阵上从一个点出发移动\(k\)次，要求路径不能有重复的点，且不能走到有阻碍的位置。

题解

考虑到数据范围非常小，既然不能走重复的位置，那么可以考虑暴力搜索并通过vis数组回溯。

时间复杂度：每个位置可以向四个方向走\(k\)次，所以时间复杂度为\(O(nm4^k)\)

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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<string> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int fx[] = {0, 0, 1, -1};
    int fy[] = {1, -1, 0, 0};
    int ans = 0;
    vector<vector<bool>> vis(n, vector<bool>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            auto check = [&](int x, int y) {
                if (0 <= x && x < n && 0 <= y && y < m && !vis[x][y] &&
                    a[x][y] == '.') {
                    return true;
                }
                return false;
            };
            auto dfs = [&](auto self, int x, int y, int cnt) -> void {
                if (cnt == k) {
                    ans++;
                    return;
                }
                for (int d = 0; d < 4; d++) {
                    int dx = x + fx[d];
                    int dy = y + fy[d];
                    if (check(dx, dy)) {
                        vis[dx][dy] = 1;
                        self(self, dx, dy, cnt + 1);
                        vis[dx][dy] = 0;
                    }
                }
            };
            if (a[i][j] == '.') {
                vis[i][j] = 1;
                dfs(dfs, i, j, 0);
                vis[i][j] = 0;
            }
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E

题意

给定一个大小为\(n\)的数组\(A_i\)和模数\(m\)，求： \[ \sum_{1\le l\le r\le n}((\sum_{l\le i\le r}A_i)\mod M) \]

题解

显然使用前缀和维护的话暴力枚举\(l,r\)复杂度是\(O(n^2)\)​，不足以通过，考虑优化（继续推导）。

我们设前缀和数组为\(pre_i = pre_{i-1} + A_i\)（均已经模了\(m\)），但是，由于模了模数\(m\)，所以\(pre[r] - pre[l-1]\)的结果可能为负，因此如果结果为负需要再加上\(m\)。我们设\(X_i\)表示对于从1到\(i\)的\(l-1\)有多少组满足\(pre[i] - pre[l-1] < 0\)，那么推导如下： \[ \begin{align}\sum_{1\le l\le r\le n}((\sum_{l\le i\le r}A_i)\mod m)\\\\ =\sum_{r = 1}^n\sum_{l=1}^r(pre[r] - pre[l-1])\mod m\\\\ =\sum_{r=1}^n(r\times pre[r] - \sum_{l=1}^rpre[l-1] + m\times X_r)\end{align} \] 对于\(r\times pre[r]\)，\(\Sigma_{l=1}^rpre[l-1]\)都是可以直接求出来的，而对于\(X_r\)，我们的求法是通过树状数组求逆序对方案数。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long

struct Fenwick {
    int n;
    vector<int> a;
    Fenwick(int n_ = 0) { init(n_); }
    void init(int n_) {
        n = n_;
        a.assign(n, 0);
    }
    void add(int x, int v) {
        for (int i = x + 1; i < n; i += i & (-i)) {
            a[i - 1] += v;
        }
    }
    int sum(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= i & (-i)) {
            ans += a[i - 1];
        }
        return ans;
    }
    int rangeSum(int l, int r) { return sum(r) - sum(l); }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> pre(n + 1);
    for (int i = 0; i < n; i++) {
        pre[i + 1] = pre[i] + a[i];
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        pre[i] %= m;
        ans += pre[i] * i;
        ans -= pre[i] * (n - i);
    }
    Fenwick bit(n + 1);
    vector<int> p(n + 1);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](int i, int j) {
        if (pre[i] != pre[j]) {
            return pre[i] > pre[j];
        }
        return i > j;
    });
    for (auto i : p) {
        ans += bit.sum(i) * m;
        bit.add(i, 1);
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

F

题意

给定一棵树，现在可以添加一条边形成一个环，要求环里的每个节点度数都是为3，求方案数。

题解

显然连接一条边会给这两个节点的度数各自加1，因此要连接两个节点后每个节点度数都是为3，就需要这个环中只有这两个节点度数为2，其余的节点度数都为3。因此，我们可以考虑dp，设\(dp[u]\)表示以\(u\)为根节点的子树中度数为2的节点数量。那么对于该子树，能形成的答案的情况包括两种：根节点度数为3，选择子树中两个度数为2的节点相连且中间节点的度数都为3；或者根节点度数为2，根节点与子树度数为2的节点相连，其余节点度数为3。那么统计答案时应该加上\(dp[u] * dp[v]\)​​。

考虑状态转移：只有\(u\)节点度数为3时，\(dp[v]\)才能累加到\(dp[u]\)，否则就会出现中间节点不为3的情况，是不符合题意的。

我们首先判断根节点是否度数为2，是的话\(dp[u]\)设置为1，对应情况一，然后依次遍历各节点并添加答案。否则为情况二：每次统计完一个节点后，如果\(u\)的度数为3，我们先把答案加上\(dp[u] * dp[v]\)，再将\(dp[u]\)加上\(dp[v]\)。这样计数可以做到不重不漏。

同时注意：由于\(u\)和\(v\)已经相连，所以不能再考虑这种情况了，当\(u,v\)的度数都为2时，答案应该减去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
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> e(n);
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    vector<int> dp(n);
    int ans = 0;
    auto dfs = [&](auto self, int u, int fa) -> void {
        dp[u] += (e[u].size() == 2);
        for (auto v : e[u]) {
            if (v == fa) {
                continue;
            }
            self(self, v, u);
            ans += dp[u] * dp[v];
            if (e[u].size() == 2 && e[v].size() == 2) {
                ans--;
            }
            if (e[u].size() == 3) {
                dp[u] += dp[v];
            }
        }
    };
    dfs(dfs, 0, -1);
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}