比赛链接：https://atcoder.jp/contests/abc179/tasks

A - Plural Form

题意

给出一个由小写字母组成的单词，如果单词以 $s$ 结尾，在单词的末尾加上 $es$，否则在单词的末尾加上 $s$ 。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    string s;

    cin >> s;

    cout << s + (s.back() == 's' ? "es" : "s") << "\n";

    return 0;

}

B - Go to Jail

题意

给出一对骰子投掷 $n$ 次的结果，问是否有连续三次两个骰子的点数相同。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int n;

    cin >> n;

    vector<int> x(n), y(n);

    for (int i = 0; i < n; i++)

        cin >> x[i] >> y[i];

    for (int i = 0; i + 2 < n; i++) {

        if (x[i] == y[i] and x[i + 1] == y[i + 1] and x[i + 2] == y[i + 2]) {

            cout << "Yes" << "\n";

            return 0;

        }

    }

    cout << "No" << "\n";

    return 0;

}

C - A x B + C

题意

给出一个正整数 $n$，问有多少不同的三元组 $(a, b, c)$ 满足 $a,b,c > 0$ 且 $a \times b + c = n$ 。

题解

枚举 $a$ 的值，与之对应的 $b$ 的最大值为 $\lfloor \frac{n}{a} \rfloor$，然后判断是否都能取到即可。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int n;

    cin >> n;

    long long ans = 0;

    for (int a = 1; a <= n; a++) {

        ans += n / a - (n % a == 0);

    }

    cout << ans << "\n";

    return 0;

}

D - Leaping Tak

题意

给出 $k$ 个区间，区间并集中的整数为每次可以选择行走的距离，问在数轴上从点 $1$ 走到点 $n$ 的路径数目。

题解

与上一场的D题类似，可以考虑如下代码：

dp[1] = 1;

for (int i = 1; i < n; i++) {

    for (int j = 0; j < k; j++) {

        for (int k = l[j]; k <= r[j]; k++) {

            (dp[i + k] += dp[i]) %= MOD;

        }

    }

}

但是 $O_{(n^2k)}$ 的复杂度明显会超时。

注意到第三层循环为区间操作，所以可以考虑用差分或线段树降低复杂度。

代码一

差分，时间复杂度为 $O_{(nk)}$ 。

#include <bits/stdc++.h>

using namespace std;

constexpr int MOD = 998244353;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int n, k;

    cin >> n >> k;

    vector<int> l(k), r(k);

    for (int i = 0; i < k; i++)

        cin >> l[i] >> r[i];

    vector<long long> dp(2 * n + 100);

    dp[1] = 1;

    dp[2] = -1;

    for (int i = 1; i <= n; i++) {

        dp[i] += dp[i - 1];

        dp[i] = (dp[i] % MOD + MOD) % MOD;

        for (int j = 0; j < k; j++) {

            dp[i + l[j]] += dp[i];

            dp[i + r[j] + 1] -= dp[i];

        }

    }

    cout << dp[n] << "\n";

    return 0;

}

代码二

线段树，时间复杂度为 $O_{(nlog_nk)}$ 。

#include <bits/stdc++.h>

#define lson i << 1

#define rson i << 1 | 1

#define mid ((l + r) >> 1)

using namespace std;

constexpr int N = 2e5 + 100;

constexpr int MOD = 998244353;

long long sum[N << 2], lazy[N << 2];

void build(int i, int l, int r) {

    if (l == r) {

        sum[i] = 0;

        return;

    }

    build(lson, l, mid);

    build(rson, mid + 1, r);

    sum[i] = sum[lson] + sum[rson];

}

void push_down_lazy(int i, int l, int r) {

    if (lazy[i] != 0) {

        (sum[lson] += lazy[i] * (mid - l + 1)) %= MOD;

        (sum[rson] += lazy[i] * (r - mid)) %= MOD;

        (lazy[lson] += lazy[i]) %= MOD;

        (lazy[rson] += lazy[i]) %= MOD;

        lazy[i] = 0;

    }

}

void update(int i, int l, int r, int L, int R, int val) {

    if (L <= l and r <= R) {

        (sum[i] += 1LL * val * (r - l + 1) % MOD) %= MOD;

        (lazy[i] += val) %= MOD;

        return;

    }

    push_down_lazy(i, l, r);

    if (L <= mid) update(lson, l, mid, L, R, val);

    if (R > mid) update(rson, mid + 1, r, L, R, val);

    sum[i] = (sum[lson] + sum[rson]) % MOD;

}

long long query(int i, int l, int r, int L, int R) {

    if (L <= l and r <= R) {

        return sum[i];

    }

    push_down_lazy(i, l, r);

    long long res = 0;

    if (L <= mid) res += query(lson, l, mid, L, R);

    if (R > mid) res += query(rson, mid + 1, r, L, R);

    return res % MOD;

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int n, k;

    cin >> n >> k;

    vector<int> l(k), r(k);

    for (int i = 0; i < k; i++)

        cin >> l[i] >> r[i];

    build(1, 1, n);

    update(1, 1, n, 1, 1, 1);

    for (int i = 1; i <= n; i++) {

        for (int j = 0; j < k; j++) {

            if (i + l[j] <= n) {

                update(1, 1, n, i + l[j], min(n, i + r[j]), query(1, 1, n, i, i));

            }

        }

    }

    cout << query(1, 1, n, n, n) << "\n";

    return 0;

}

E - Sequence Sum

题意

$a_1 = x,\ a_{n+1} = a_n^2\ %\ m$，计算 $\displaystyle{\sum_{i=1}^n a_i}$ 。

题解

找出循环节的起点和终点即可。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    long long n, x, m;

    cin >> n >> x >> m;

    const int N = min(n + 1, m + 2);

    vector<int> a(N);

    vector<int> vis(m);

    a[1] = x;

    vis[x] = 1;

    long long ans = 0;

    for (int i = 2; i < N; i++) {

        a[i] = a[i - 1] * a[i - 1] % m;

        if (vis[a[i]]) {

            long long sum1 = accumulate(a.begin(), a.begin() + vis[a[i]], 0LL);

            vector<int> cycle;

            for (int j = vis[a[i]]; j < i; j++) {

                cycle.push_back(a[j]);

            }

            n -= vis[a[i]] - 1;

            long long sum2 = accumulate(cycle.begin(), cycle.end(), 0LL);

            long long sum3 = accumulate(cycle.begin(), cycle.begin() + n % cycle.size(), 0LL);

            cout << sum1 + sum2 * (n / cycle.size()) + sum3 << "\n";

            return 0;

        } else {

            vis[a[i]] = i;

        }

    }

    ans = accumulate(a.begin(), a.end(), 0LL);

    cout << ans << "\n";

    return 0;

}

F - Simplified Reversi

题意

有一个 $n \times n$ 的棋盘，棋盘中间 $(n-2) \times (n-2)$ 的方阵中为黑子，棋盘的最右列和最下行为白子。

接下来有 $q$ 次操作：

$(1, x)$：在棋盘的第一行的 $x$ 列放置一枚白子，白字与该列最近的白子之间均变为白子
$(2, x)$：在棋盘的第一列的 $x$ 行放置一枚白子，白字与该行最近的白子之间均变为白子

问 $q$ 操作之后还有多少个黑子。

题解

更新最左列和最上行的同时存储移动过程中黑子个数固定的列和行。（也可以直接用二维线段树但我不会）

代码

#include <bits/stdc++.h>

using namespace std;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int n, q;

    cin >> n >> q;

    long long ans = 1LL * (n - 2) * (n - 2);

    vector<int> row(n + 1), col(n + 1);

    int pos_row = n, pos_col = n;

    for (int i = 0; i < q; i++) {

        int op, pos;

        cin >> op >> pos;

        if (op == 1) {

            if (pos < pos_col) {

                ans -= pos_row - 2;

                while (pos_col > pos) col[pos_col--] = pos_row - 2;

            } else {

                ans -= col[pos];

            }

        } else {

            if (pos < pos_row) {

                ans -= pos_col - 2;

                while (pos_row > pos) row[pos_row--] = pos_col - 2;

            } else {

                ans -= row[pos];

            }

        }

    }

    cout << ans << "\n";

    return 0;

}

巴特西

AtCoder Beginner Contest 179