AtCoder Beginner Contest 179

发表于2020-09-22更新于2023-09-15字数统计1.2k阅读时长13分

比赛链接

D Leaping Tak

Description

题目链接

Solution

设 dp[i]dp[i] 表示抵达位置 ii 的方案数，显然有 dp[1]=1dp[1]=1。考虑直接转移，则 dp[i]=∑s=1k∑j=i−Rsi−Lsdp[j]dp[i]=\sum\limits_{s=1}^{k}\sum\limits_{j=i-R_s}^{i-L_s}dp[j]，这么做最坏情况下复杂度为 O(kn2)O(kn^2)。容易发现，内层求和可以用前缀和维护，从而使时间复杂度降至O(kn)O(kn)。

Code

Leaping Tak
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;
typedef long long LL;

const int MAXN = 2E5 + 5;
const int MOD = 998244353;

int n, k;
int l[11], r[11];
LL dp[MAXN], sum[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= k; i++) cin >> l[i] >> r[i];
    dp[1] = 1, sum[1] = 1;
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= k; j++) {
            if (i - l[j] >= 0) {
                dp[i] += sum[i - l[j]] - sum[max(0, i - r[j] - 1)];
                dp[i] = (dp[i] % MOD + MOD) % MOD;
            }
            sum[i] = (sum[i - 1] + dp[i]) % MOD;
        }
    cout << dp[n];
    return 0;
}

E Sequence Sum

Description

题目链接

Solution

显然有 An+1=An∗Anmod  MA_{n+1}=A_{n}*A_{n} \mod M，那么 A2,A3……AnA_2,A_3……A_n 关于模 MM 乘构成循环群，因此可在 O(M)O(M) 时间内求得循环节并通过前缀和求得∑i=1nAi\sum\limits_{i=1}^{n}A_i。

Code

Sequence Sum
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 <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;

LL n, x, m;
LL sum[MAXN], a[MAXN], last[MAXN], st, ed;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> x >> m;
    a[1] = x, sum[1] = a[1];
    for (int i = 2; i <= n; i++) {
        a[i] = a[i - 1] * a[i - 1] % m;
        if (!a[i]) {
            cout << sum[i - 1];
            return 0;
        }
        sum[i] = sum[i - 1] + a[i];
        if (last[a[i]]) {
            st = last[a[i]];
            ed = i - 1;
            break;
        }
        last[a[i]] = i;
    }
    if (!ed)
        cout << sum[n];
    else {
        LL len = ed - st + 1;
        LL cycleSum = sum[ed] - sum[st - 1];
        LL ans = sum[st - 1];
        LL tot = n - st + 1;
        ans += tot / len * cycleSum;
        int res = tot % len;
        ans += sum[st + res - 1] - sum[st - 1];
        cout << ans;
    }
    return 0;
}

F Simplified Reversi

Description

题目链接

Solution

首先，总的黑棋子数为 (n−2)2(n-2)^2，我们只需要考虑每次操作会删除多少黑棋子，最后用 (n−2)2(n-2)^2 减去被删除黑棋子的总数就是答案。

对于操作 1，在第 xx 列上查询第一个白棋子的位置 jj，那么应该被删去的黑棋子的数目为 j−2j-2。对于 [2,j−1][2,j-1] 行，删去这些黑棋子并用白棋子替换后，显然有第一个白棋子的位置不超过 xx。

对于操作 2，可以看作是在操作 1 的基础上对行列进行了交换。

因此，我们可以对行和列分别建立线段树维护区间最小值。对于操作 1，在列上单点查询，在行上进行区间修改；对于操作 2，在行上单点查询，在列上进行区间修改。

Code

Simplified Reversi
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;

int n, q, type, x;
LL ans;

struct Node {
    int lson, rson;
    int l, r, mi, lazy;
} tr[MAXN * 8];

int root1, root2;

void update(int id) { tr[id].mi = min(tr[tr[id].lson].mi, tr[tr[id].rson].mi); }

void pushdown(int id) {
    if (tr[id].lazy != n) {
        tr[tr[id].lson].mi = min(tr[tr[id].lson].mi, tr[id].lazy);
        tr[tr[id].lson].lazy = min(tr[tr[id].lson].lazy, tr[id].lazy);
        tr[tr[id].rson].mi = min(tr[tr[id].rson].mi, tr[id].lazy);
        tr[tr[id].rson].lazy = min(tr[tr[id].rson].lazy, tr[id].lazy);
        tr[id].lazy = n;
    }
}

void build(int& id, int l, int r) {
    static int tot;
    id = ++tot;
    tr[id].l = l, tr[id].r = r;
    tr[id].lazy = n;
    if (l == r) {
        tr[id].mi = n;
        return;
    }
    int mid = l + r >> 1;
    build(tr[id].lson, l, mid);
    build(tr[id].rson, mid + 1, r);
    update(id);
}

void modify(int id, int l, int r, int val) {
    if (tr[id].mi < val) return;
    if (tr[id].l == l && tr[id].r == r) {
        tr[id].mi = min(tr[id].mi, val);
        tr[id].lazy = min(tr[id].lazy, val);
        return;
    }
    pushdown(id);
    int mid = tr[id].l + tr[id].r >> 1;
    if (r <= mid)
        modify(tr[id].lson, l, r, val);
    else if (l > mid)
        modify(tr[id].rson, l, r, val);
    else {
        modify(tr[id].lson, l, mid, val);
        modify(tr[id].rson, mid + 1, r, val);
    }
    update(id);
}

int query(int id, int x) {
    if (tr[id].l == x && tr[id].r == x) {
        return tr[id].mi;
    }
    pushdown(id);
    int mid = tr[id].l + tr[id].r >> 1;
    if (x <= mid)
        return query(tr[id].lson, x);
    else
        return query(tr[id].rson, x);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    ans = 1ll * (n - 2) * (n - 2);
    build(root1, 2, n - 1);
    build(root2, 2, n - 1);
    for (int i = 1; i <= q; i++) {
        cin >> type >> x;
        if (type == 1) {
            int now = query(root1, x);
            ans-= now - 2;
            modify(root2, 2, now - 1, x);
        } else {
            int now = query(root2, x);
            ans -= now - 2;
            modify(root1, 2, now - 1, x);
        }
    }
    cout << ans;
    return 0;
}