AtCoder Beginner Contest 357

A - Sanitize Hands (abc357 A)

题目大意

给定\(m\)个物品。

依次来 \(n\)个人,每个人拿\(a_i\)个物品。

问有几个人可以拿走所需物品。

解题思路

求一遍前缀和然后upper_bound一下,或者直接累计求和。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (auto& x : a)
        cin >> x;
    partial_sum(a.begin(), a.end(), a.begin());
    auto ans = upper_bound(a.begin(), a.end(), m) - a.begin();
    cout << ans << '\n';

    return 0;
}



B - Uppercase and Lowercase (abc357 B)

题目大意

给定一个字符串,若大写字母占多数,则全部字母变成大写字母,否则变成小写字母。

问最终的字符串。

解题思路

按照题意统计一下大小写字母的数量,然后按照规则变换即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    int lower = count_if(s.begin(), s.end(), [](char c) { return islower(c); });
    int upper = s.size() - lower;
    if (lower >= upper) {
        transform(s.begin(), s.end(), s.begin(), ::tolower);
    } else {
        transform(s.begin(), s.end(), s.begin(), ::toupper);
    }
    cout << s << '\n';

    return 0;
}



C - Sierpinski carpet (abc357 C)

题目大意

给定\(n\),输出一个 \(3^{n} \times 3^{n}\)的图形 \(g_n\),其中有 \(9 \times 9\)格,中间格子是全 .,其余\(8\)格的图案是 \(g_{n-1}\)

\(g_0\)的图形是 #

解题思路

按照题意递归构造。

枚举\(3^{n} \times 3^{n}\)的每个位置\((i,j)\),设\(sz=3^{n-1}\)。然后通过\((\frac{i}{sz}, \frac{j}{sz})\)判断其属于 \(9\)个方格中的哪个,如果是中间,则就是 .,否则就进入子问题\((i \% sz, j % sz, n - 1)\),即 \(g_{n-1}\)的图案,位置 \((i \% sz, j \% sz)\)的图形。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    auto ns = [&](int i) {
        int sz = 1;
        for (int j = 0; j < i; j++) {
            sz *= 3;
        }
        return sz;
    };
    int sz = ns(n);
    auto solve = [&](auto solve, int i, int j, int n) -> char {
        if (n == 0)
            return '#';
        int small = ns(n - 1);
        int x = i / small, y = j / small;
        if (x == 1 && y == 1) {
            return '.';
        } else
            return solve(solve, i % small, j % small, n - 1);
    };
    for (int i = 0; i < sz; i++) {
        for (int j = 0; j < sz; j++) {
            cout << solve(solve, i, j, n);
        }
        cout << '\n';
    }

    return 0;
}



D - 88888888 (abc357 D)

题目大意

给定\(n\),定义 \(f(n)\)表示 \(n\)\(n\)的拼接得到的数字。

\(f(n) \% 998244353\)

解题思路

\(a_1\)表示 \(1\)\(n\)\(a_2\)表示\(2\)\(n\)

容易得到\(a_1 = n, a_2 = xa_1 + n = xn + n = n(x + 1), a_3 = xa_2 + n = n(x^2 + x + 1)\),其中 \(x=10^k\)\(k\)\(n\)的位数。

展开得到通项公式\(a_n = xa_{n-1} + n = n(x^{n-1} + x^{n-2} + \cdots + x + 1) = n \frac{x^n - 1}{x - 1}\)

通过费马小定理知 \(\frac{1}{x-1} \equiv (x-1)^{mo-2} \mod mo,mo=998244353\)

因此最终答案就是\(n (x^n - 1)(x - 1)^{mo-2}\) ,用快速幂计算即可。时间复杂度是\(O(\log n)\)

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int mo = 998244353;

long long qpower(long long a, long long b) {
    long long qwq = 1;
    while (b) {
        if (b & 1)
            qwq = qwq * a % mo;
        a = a * a % mo;
        b >>= 1;
    }
    return qwq;
}

long long inv(long long x) { return qpower(x, mo - 2); }

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    LL n;
    cin >> n;
    __int128 ten = 1;
    while (ten <= n) {
        ten *= 10;
    }
    ten %= mo;
    LL up = ((qpower(ten, n) - 1) + mo) % mo;
    LL down = inv(ten - 1);
    LL ans = n % mo * up % mo * down % mo;
    cout << ans << '\n';

    return 0;
}



E - Reachability in Functional Graph (abc357 E)

题目大意

给定一张基环内向森林(有向图,每个点出度为\(1\)),问点对数量 \((i,j)\),满足从点 \(i\)出发可以到达点 \(j\)

解题思路

考虑朴素做法,显而易见的\(O(n^2)\):从每个点出发,进行 \(DFS\)

分析朴素做法,会发现操作重复的地方:假想一条链 \(1 \to 2 \to 3 \to 4 \cdots\),从 \(1\)出发 \(DFS\),从 \(2\)出发 \(DFS\),会发现非常冗余,当从 \(1\)出发时,它能到达的点, \(2\)也能到达,也就是说可以利用 \(2\)节点的信息,以避免重复搜索。

我们想通过后继节点的答案来得到当前点的答案,那得先计算后继节点答案,然后再考虑当前节点。这其实非常像拓扑排序:把边方向,然后我们处理入度为 \(0\)的点(这意味着原图中的后继节点已经计算完毕了)。

然而拓扑排序适用于 \(DAG\)(有向无环图),这里有环,因此得事先找到环。环上的节点是处处到达的。

如何找到环呢?考虑这是一张基环内向森林,它有个性质,即从任何点出发,最终一定会走到环内。

注意到答案分两类,一类是环上的点的贡献,其贡献值即为环大小。另一类是非环上的点的贡献,由于从它出发最终会走到环内,因此其贡献值为环大小\(+\)沿途的点数,我们从环上的点出发,就能一路更新沿途的点数及贡献了。

首先从任意点进行\(DFS\),直到重复访问到某个点时,这个点就是环上的点,标记一下。

然后从标记的点进行\(DFS\),遍历环上的点,统计环大小和标记环上的点。同时统计环上的点对答案的贡献(即环大小)。

最后从环上的点往非环上的点进行 \(DFS\),统计非环点对答案的贡献。

\(3\)\(DFS\)即可,时间复杂度是 \(O(n)\)

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<vector<int>> edge(n), inv(n);
    for (int i = 0; i < n; ++i) {
        int p;
        cin >> p;
        --p;
        edge[i].push_back(p);
        inv[p].push_back(i);
    }
    vector<int> cnt(n), cir(n), visit(n);
    int tt = 0;
    auto dfs1 = [&](auto dfs1, int u) -> void {
        visit[u] = tt;
        for (auto v : edge[u]) {
            if (!visit[v]) {
                dfs1(dfs1, v);
            } else if (visit[v] == tt) {
                cir[v] = 1;
            }
        }
    };
    for (int i = 0; i < n; ++i) {
        if (!visit[i]) {
            ++tt;
            dfs1(dfs1, i);
        }
    }
    fill(visit.begin(), visit.end(), 0);
    int cur = 0;
    auto dfs2 = [&](auto dfs2, int u) -> void {
        visit[u] = 1;
        cir[u] = 1;
        ++cur;
        for (auto v : edge[u]) {
            if (!visit[v]) {
                dfs2(dfs2, v);
            }
        }
        cnt[u] = cur;
    };
    for (int i = 0; i < n; ++i) {
        if (cir[i] == 1 && !visit[i]) {
            cur = 0;
            dfs2(dfs2, i);
        }
    }
    LL ans = 0;
    for (int i = 0; i < n; ++i) {
        if (cir[i])
            ans += cnt[i];
    }
    auto dfs3 = [&](auto dfs3, int u, int cc) -> void {
        for (auto& v : inv[u]) {
            if (!cir[v]) {
                ans += cc + 1;
                dfs3(dfs3, v, cc + 1);
            }
        }
    };
    for (int i = 0; i < n; ++i) {
        if (cir[i]) {
            dfs3(dfs3, i, cnt[i]);
        }
    }
    cout << ans << '\n';

    return 0;
}



F - Two Sequence Queries (abc357 F)

题目大意

给定两个数组\(a,b\), 维护一下三种操作:

  • 1 l r x,给\(a_l, a_{l+1}, \cdots, a_r\)都加上 \(x\)
  • 2 l r x,给\(b_l, b_{l+1}, \cdots, b_r\)都加上 \(x\)
  • 3 l r,求\(\sum_{i=l}^{r} a_i \times b_i \mod 998244353\)

解题思路

区间操作,考虑线段树,维护的信息是什么。

首先肯定有\(\sum a_i b_i\),考虑对它修改后,要额外维护什么信息,才能得到新的 \(\sum a_i b_i\)

对它修改,即变为 \(\sum (a_i + x)(b_i + y) = \sum a_i b_i + y\sum a_i + x\sum b_i + \sum xy\)

因此我们还需维护\(\sum a_i\)\(\sum b_i\),而它们的更新则需要自己的信息即可。

由于是区间操作, \(lazy\)信息就维护 \(x,y\)

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int N = 2e5 + 8;
const int mo = 998244353;

class segment {
#define lson (root << 1)
#define rson (root << 1 | 1)
  public:
    LL sab[N << 2];
    LL sum[N << 2][2];
    LL lazy[N << 2][2];

    void pushup(int root) {
        sab[root] = (sab[lson] + sab[rson]) % mo;
        sum[root][0] = (sum[lson][0] + sum[rson][0]) % mo;
        sum[root][1] = (sum[lson][1] + sum[rson][1]) % mo;
    }

    void build(int root, int l, int r, vector<int>& a, vector<int>& b) {
        if (l == r) {
            sab[root] = 1ll * a[l - 1] * b[l - 1] % mo;
            sum[root][0] = a[l - 1];
            sum[root][1] = b[l - 1];
            return;
        }
        int mid = (l + r) >> 1;
        build(lson, l, mid, a, b);
        build(rson, mid + 1, r, a, b);
        pushup(root);
    }

    void pushdown(int root, int l, int mid, int r) {
        if (lazy[root][0] || lazy[root][1]) {
            sab[lson] =
                (sab[lson] + lazy[root][0] * sum[lson][1] % mo +
                 lazy[root][1] * sum[lson][0] % mo +
                 lazy[root][0] * lazy[root][1] % mo * (mid - l + 1) % mo) %
                mo;
            sum[lson][0] =
                (sum[lson][0] + lazy[root][0] * (mid - l + 1) % mo) % mo;
            sum[lson][1] =
                (sum[lson][1] + lazy[root][1] * (mid - l + 1) % mo) % mo;

            sab[rson] = (sab[rson] + lazy[root][0] * sum[rson][1] % mo +
                         lazy[root][1] * sum[rson][0] % mo +
                         lazy[root][0] * lazy[root][1] % mo * (r - mid) % mo) %
                        mo;
            sum[rson][0] = (sum[rson][0] + lazy[root][0] * (r - mid) % mo) % mo;
            sum[rson][1] = (sum[rson][1] + lazy[root][1] * (r - mid) % mo) % mo;

            lazy[lson][0] = (lazy[lson][0] + lazy[root][0]) % mo;
            lazy[lson][1] = (lazy[lson][1] + lazy[root][1]) % mo;
            lazy[rson][0] = (lazy[rson][0] + lazy[root][0]) % mo;
            lazy[rson][1] = (lazy[rson][1] + lazy[root][1]) % mo;

            lazy[root][0] = lazy[root][1] = 0;
        }
    }

    void update(int root, int l, int r, int L, int R, LL val, int op) {
        if (L <= l && r <= R) {
            sab[root] = (sab[root] + val * sum[root][op ^ 1] % mo) % mo;
            sum[root][op] = (sum[root][op] + val * (r - l + 1) % mo) % mo;
            lazy[root][op] = (lazy[root][op] + val) % mo;
            return;
        }
        int mid = (l + r) >> 1;
        pushdown(root, l, mid, r);
        if (L <= mid)
            update(lson, l, mid, L, R, val, op);
        if (R > mid)
            update(rson, mid + 1, r, L, R, val, op);
        pushup(root);
    }

    LL query(int root, int l, int r, int L, int R) {
        if (L <= l && r <= R) {
            return sab[root];
        }
        int mid = (l + r) >> 1;
        pushdown(root, l, mid, r);
        LL ans = 0;
        if (L <= mid)
            ans += query(lson, l, mid, L, R);
        if (R > mid)
            ans += query(rson, mid + 1, r, L, R);
        ans %= mo;
        return ans;
    }

} sg;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> a(n), b(n);
    for (auto& i : a)
        cin >> i;
    for (auto& i : b)
        cin >> i;
    sg.build(1, 1, n, a, b);
    while (q--) {
        int op;
        cin >> op;
        if (op == 3) {
            int l, r;
            cin >> l >> r;
            int ans = sg.query(1, 1, n, l, r);
            cout << ans << '\n';
        } else {
            int l, r, x;
            cin >> l >> r >> x;
            sg.update(1, 1, n, l, r, x, op - 1);
        }
    }

    return 0;
}



G - Stair-like Grid (abc357 G)

题目大意

给定\(n\),定义一个网格,前两行有 \(4\)个格子,接着两行有 \(6\)个格子,接着两行有 \(8\)个格子 \(...\)

其中有 \(m\)个格子不可走。

从左上到右下,只能往下走和往右走。问方案数。

解题思路

<++>

神奇的代码



热门相关:第99次离婚   自古红楼出才子   大亨   梁医生又在偷偷套路我   你是我生命的四分之三