ABC357(A-G)

A - Sanitize Hands ¶

题目大意

给你 $N$ 个数，第 $i$ 个数是 $H_i$，同时给你一个数字 $M$，求出大的下标 $t$，使得 $\sum\limits_{i = 1}^tH_i \le M$

参考代码

C++

#include <iostream>

using namespace std;

int main()
{
    int n, m, h, ans = 0;
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        cin >> h;
        m -= h;
        if(m >= 0)
            ans++;
    }
    cout << ans << endl;
    return 0;
}

B - Uppercase and Lowercase ¶

题目大意

给你一个由大小写字母组成的字符串 $S$，如果大写字母比小写字母多，则将所有小写字母转成大写字母，否则将所有大写字母转成小写字母。

参考代码

C++

#include <iostream>
#include <cctype>

using namespace std;

int main()
{
    string s;
    cin >> s;
    int cnt = 0;
    for(auto ch : s)
        if(isupper(ch))
            cnt++;
        else
            cnt--;
    if(cnt > 0)
        for(auto &ch : s)
            ch = toupper(ch);
    else
        for(auto &ch : s)
            ch = tolower(ch);
    cout << s << endl;
    return 0;
}

C - Sierpinski carpet ¶

题目大意

对于一个非负整数 $K$，我们定义 $K$ 阶矩阵的内容为：

如果 $K = 0$，一个 $0$ 阶矩阵是一个大小为 $1 \times 1$ 的矩阵，矩阵的值为 #
如果 $K > 0$，一个 $K$ 阶矩阵是一个大小为 $3^K \times 3^K$ 的矩阵，我们可以将其分成 $9$ 个大小为 $3^{K-1} \times 3^{K-1}$ 的块：
- 中心块的值全部为 .
- 其余块都是 $K-1$ 阶的矩阵。

输入一个整数 $N(0 \le N \le 6)$，输出 $N$ 阶矩阵的内容。

解题思路

$3^6 = 729$，直接模拟即可。

参考代码

C++

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> p(n+1);
    p[0] = 1;
    for (int i = 1; i <= n; i++)
        p[i] = p[i - 1] * 3;

    int len = p[n];
    vector<string> carpet(len, string(len, '#'));

    auto padding = [&carpet, &p](auto &&self, int k)
    {
        static const int dr[] = {0, 0, 1, 1, 2, 2, 2};
        static const int dc[] = {1, 2, 0, 2, 0, 1, 2};
        if (k == 0)
            return;
        self(self, k - 1);
        int len = p[k - 1];
        for (int r = 0; r < len; r++)
            for (int c = 0; c < len; c++)
                for (int i = 0; i < 7; i++)
                {
                    int nr = r + dr[i] * len;
                    int nc = c + dc[i] * len;
                    carpet[nr][nc] = carpet[r][c];
                }

        int r = len, c = len;
        for (int dr = 0; dr < len; dr++)
            for (int dc = 0; dc < len; dc++)
                carpet[r + dr][c + dc] = '.';
    };

    padding(padding, n);

    for (int r = 0; r < len; r++)
        cout << carpet[r] << endl;;

    return 0;
}

D - 88888888 ¶

题目大意

对于正整数 $N$，定义 $V_N$ 表示 $N$ 重复了 $N$ 次所得到的数字，例如：$V_3 = 333$，$V_{10} = 10101010101010101010$

输入一个正整数 $N(1 \le N \le 10^{18})$，输出 $V_N$，答案对 $998244353$ 取模。

解题思路

设 $t$ 表示数字 $N$ 对应的字符串的长度，不难发现 $V_N = N \times(10^t + 10^{2t} + \cdots + 10^{Nt})$，令 $q = 10^t$，根据等比数列求和公式可得： $$ V_N & = & N \times (q + q^2 + q^N) \ & = & N \times \frac{q^N-1}{q-1} $$ 因为答案要取模，分母的部分求个逆元，分子的部分求个快速幂即可。

注意求 $q$ 的时候也要边算边取模，不然会 WA 一个点。

参考代码

C++

#include <iostream>

using namespace std;

typedef long long LL;

const LL mod = 998244353;

void exgcd(LL a, LL b, LL &x, LL &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return;
    }
    exgcd(b, a%b, y, x);
    y -= a/ b * x;
}

LL getinv(LL a)
{
    LL x, y;
    exgcd(a, mod, x, y);
    if(x < 0)
        x += mod;
    return x;
}

LL qpow(LL a, LL x)
{
    a %= mod;
    x %= mod-1;
    LL ans = 1;
    while(x)
    {
        if(x & 1)
            ans = ans * a % mod;
        x >>= 1;
        a = a * a % mod;
    }
    return ans;
}

int main()
{
    LL n;
    cin >> n;
    LL ans = n % mod;
    LL q = 1;
    for(int t = to_string(n).size(); t; t--)
        q = q * 10 % mod;
    LL total = qpow(q, n) - 1;
    if(total < 0)
        total += mod;
    total = total * getinv(q-1) % mod;
    ans = ans * total % mod;
    cout << ans << endl;
    return 0;
}

E - Reachability in Functional Graph ¶

题目大意

给你一个 $N(1 \le N \le 2 \times 10^5)$ 个点 $N$ 条边的有向图，每个点都有一条出边，第 $i$ 个点的出边指向的点是 $a_i$

定义 $c(u)$ 表示从 $u$ 点出发最多能到达多少个点，特别的，我们规定任何点到自身总是可达的。求出 $\sum\limits_{u = 1}^Nc(u)$

解题思路

用 tarjan 算法缩一下点，由于本题每个点的出度都为 $1$，计算答案更加简单，首先计算出每个强连通分量的点的个数，如果连通分量大小大于 $1$，则这些点一定是成环的，对于环上的任意点，都只能访问连通分量大小的点。

而如果连通分量大小为 $1$，则直接加上出边的答案值即可，记忆化搜索即可。

参考代码

C++

#include <iostream>
#include <vector>
#include <stack>
#include <functional>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> ne(n + 1);
    vector<int> p(n + 1);
    vector<int> cnt(n + 1);
    vector<int> dfn(n + 1);
    vector<int> low(n + 1);
    for (int u = 1; u <= n; u++)
        cin >> ne[u];
    vector<bool> inst(n + 1);
    stack<int> st;
    int ti = 1;
    function<void(int)> tarjan = [&](int u)
    {
        dfn[u] = low[u] = ti++;
        st.push(u);
        inst[u] = 1;
        int v = ne[u];
        if (!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (inst[v])
            low[u] = min(low[u], dfn[v]);

        if (dfn[u] == low[u])
        {
            while (1)
            {
                v = st.top();
                st.pop();
                inst[v] = 0;
                p[v] = u;
                cnt[u]++;
                if (u == v)
                    break;
            }
        }
    };

    for (int u = 1; u <= n; u++)
        if (!dfn[u])
            tarjan(u);

    long long ans = 0;
    vector<int> dp(n + 1);
    auto DP = [&dp, &p, &ne, &cnt](auto &&self, int u) -> int
    {
        if (cnt[u] > 1)
            return cnt[u];
        if (dp[u])
            return dp[u];
        int v = p[ne[u]];
        if(u == v)
            return 1;
        dp[u] = 1 + self(self, v);
        return dp[u];
    };

    for (int u = 1; u <= n; u++)
        ans += DP(DP, p[u]);
    cout << ans << endl;
    return 0;
}

F - Two Sequence Queries ¶

题目大意

给你两个长度为 $N(1 \le N \le 2 \times 10^5)$ 序列 $A = (A_1, A_2, \cdots, A_N)$ 和 $B = (B_1, B_2, \cdots, B_N)$。

有 $Q(1 \le Q \le 2 \times 10^5)$ 个询问，询问有 $3$ 种类型：

1 l r x：$A$ 序列的 $A_l, A_{l+1}, \cdots, A_r$ 这些数加 $x$。
2 l r x：$B$ 序列的 $B_l, B_{l+1}, \cdots, B_r$ 这些数加 $x$。
3 l r：查询 $\sum\limits_{i = l}^rA_iB_i$ 的值。

解题思路

前两个修改显然可以用懒标记线段树，线段树节点存储 $\sum\limits_{i = l}^rA_iB_i$ 的值，下面考虑如何下放懒标记。

由于有 $A$ 和 $B$ 两种类型的懒标记，一次性下放的时候两个懒标记都会放下来，所以先考虑能不能无序下放。

无序下放就相当于将 $1$ 操作和 $2$ 操作合并，结果的值变为 $\sum\limits_{i = l}^r(A_i+x)(B_i+y)$

推导一下：

\[ \begin{aligned} \sum\limits_{i = l}^r(A_i+x)(B_i+y) & = \sum\limits_{i = l}^r(A_iB_i+xB_i+yA_i+xy) \\ & = \sum\limits_{i = l}^rA_iB_i + x\sum\limits_{i = l}^rB_i + y\sum\limits_{i = l}^rA_i + (r-l+1)xy \end{aligned} \]

于是我们发现，只需要同时维护区间和 $\sum\limits_{i = l}^rA_i$ 和 $\sum\limits_{i = l}^rB_i$，那么下放懒标记的时候就不用考虑顺序了，剩下的就是懒标记线段树的操作了。

参考代码

C++

#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;
const LL mod = 998244353;

class SegTree
{
public:
    SegTree(int n, const vector<LL> &a, const vector<LL> &b) : n(n), t(4 * n)
    {
        auto build = [&](auto &&self, int p, int beg, int end)
        {
            if (beg == end)
            {
                t[p].sum_a = a[beg] % mod;
                t[p].sum_b = b[beg] % mod;
                t[p].sum_ab = (t[p].sum_a * t[p].sum_b) % mod;
                return;
            }
            int mid = (beg + end) / 2;
            int lch = p * 2, rch = p * 2 + 1;
            self(self, lch, beg, mid);
            self(self, rch, mid + 1, end);
            push_up(p, lch, rch);
        };
        build(build, 1, 1, n);
    }

    LL query(int l, int r)
    {
        auto ask = [&](auto &&self, int p, int beg, int end) -> LL
        {
            if (end < l || beg > r)
                return 0;
            if (beg >= l && end <= r)
                return t[p].sum_ab;
            push_down(p, beg, end);
            int mid = (beg + end) / 2;
            int lch = p * 2, rch = p * 2 + 1;
            return (self(self, lch, beg, mid) + self(self, rch, mid + 1, end)) % mod;
        };
        return ask(ask, 1, 1, n);
    }

    void add_a(int l, int r, LL x)
    {
        auto add = [&](auto &&self, int p, int beg, int end)
        {
            if (end < l || beg > r)
                return;
            if (beg >= l && end <= r)
            {
                int pn = end - beg + 1;
                t[p].sum_ab = (t[p].sum_ab + t[p].sum_b * x % mod) % mod;
                t[p].sum_a = (t[p].sum_a + pn * x) % mod;
                t[p].la = (t[p].la + x) % mod;
                return;
            }
            push_down(p, beg, end);
            int mid = (beg + end) / 2;
            int lch = p * 2, rch = p * 2 + 1;

            self(self, lch, beg, mid);
            self(self, rch, mid + 1, end);

            push_up(p, lch, rch);
        };

        add(add, 1, 1, n);
    }

    void add_b(int l, int r, LL y)
    {
        auto add = [&](auto &&self, int p, int beg, int end)
        {
            if (end < l || beg > r)
                return;
            if (beg >= l && end <= r)
            {
                int pn = end - beg + 1;
                t[p].sum_ab = (t[p].sum_ab + t[p].sum_a * y % mod) % mod;
                t[p].sum_b = (t[p].sum_b + pn * y) % mod;
                t[p].lb = (t[p].lb + y) % mod;
                return;
            }
            push_down(p, beg, end);
            int mid = (beg + end) / 2;
            int lch = p * 2, rch = p * 2 + 1;

            self(self, lch, beg, mid);
            self(self, rch, mid + 1, end);

            push_up(p, lch, rch);
        };

        add(add, 1, 1, n);
    }

private:
    struct Node
    {
        LL sum_a, sum_b, sum_ab;
        LL la{0}, lb{0};
    };
    int n;
    vector<Node> t;

    void push_up(int p, int lch, int rch)
    {
        t[p].sum_a = (t[lch].sum_a + t[rch].sum_a) % mod;
        t[p].sum_b = (t[lch].sum_b + t[rch].sum_b) % mod;
        t[p].sum_ab = (t[lch].sum_ab + t[rch].sum_ab) % mod;
    }

    void push_down(int p, int beg, int end)
    {
        int mid = (beg + end) / 2;
        int lch = p * 2, rch = p * 2 + 1;
        LL la = t[p].la, lb = t[p].lb;
        LL ln = mid - beg + 1, rn = end - mid;
        t[p].la = t[p].lb = 0;

        t[lch].sum_ab = (t[lch].sum_ab + la * t[lch].sum_b % mod + lb * t[lch].sum_a % mod + ln * la % mod * lb % mod) % mod;
        t[lch].sum_a = (t[lch].sum_a + ln * la % mod) % mod;
        t[lch].sum_b = (t[lch].sum_b + ln * lb % mod) % mod;
        t[lch].la = (t[lch].la + la) % mod;
        t[lch].lb = (t[lch].lb + lb) % mod;

        t[rch].sum_ab = (t[rch].sum_ab + la * t[rch].sum_b % mod + lb * t[rch].sum_a % mod + rn * la % mod * lb % mod) % mod;
        t[rch].sum_a = (t[rch].sum_a + rn * la % mod) % mod;
        t[rch].sum_b = (t[rch].sum_b + rn * lb % mod) % mod;
        t[rch].la = (t[rch].la + la) % mod;
        t[rch].lb = (t[rch].lb + lb) % mod;
    }
};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<LL> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    SegTree t(n, a, b);
    LL op, l, r, x;
    while(q--)
    {
        cin >> op >> l >> r;
        if(op == 3)
            cout << t.query(l, r) << endl;
        else
        {
            cin >> x;
            op == 1 ? t.add_a(l, r, x) : t.add_b(l, r, x);
        }
    }
    return 0;
}

最后更新: 2024-06-21
创建日期: 2024-06-14

ABC357(A-G)

A - Sanitize Hands¶

B - Uppercase and Lowercase¶

C - Sierpinski carpet¶

D - 88888888¶

E - Reachability in Functional Graph¶

F - Two Sequence Queries¶

A - Sanitize Hands ¶

B - Uppercase and Lowercase ¶

C - Sierpinski carpet ¶

D - 88888888 ¶

E - Reachability in Functional Graph ¶

F - Two Sequence Queries ¶