357

A - Sanitize Hands

有一瓶消毒剂，正好可以消毒 $M$ 双手。

$N$ 名外星人按照顺序来消毒双手。 $i$ 个外星人（ $1 \leq i \leq N$ ）有 $H_{i}$ 只手，想把所有的手都消毒一次。

请计算有多少个外星人可以给所有的手消毒。

在这里，即使开始时没有足够的消毒剂给一个外星人的所有手消毒，他们也会用完剩余的消毒剂。

void solve() {
    int n, m;cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;
        m -= x;
        if (m < 0) {
            cout << i - 1 << '\n';return;
        }
    }
    cout << n << '\n';
}

B - Uppercase and Lowercase

给你一个由小写和大写英文字母组成的字符串 $S$ 。 $S$ 的长度是奇数。

如果 $S$ 中大写字母的数量大于小写字母的数量，请将 $S$ 中的所有小写字母转换为大写字母。

否则，将 $S$ 中的所有大写字母转换为小写字母。

void solve() {
    string s;cin >> s;
    int lo = 0;
    for (int i = 0;i < s.size();i++) {
        if (islower(s[i]))lo++;
    }
    if (lo >= s.size() - lo) {
        for (int i = 0;i < s.size();i++) {
            if (isupper(s[i]))cout << (char)tolower(s[i]);
            else cout << s[i];
        }
    } else {
        for (int i = 0;i < s.size();i++) {
            if (islower(s[i]))cout << (char)toupper(s[i]);
            else cout << s[i];
        }
    }
}

C - Sierpinski carpet

对于非负整数 $K$ ，我们定义一个等级地毯- $K$ 如下：

$0$ 级地毯是由一个黑色单元格组成的 $1 \times 1$ 网格。
对于 $K > 0$ ， $K$ 级地毯是一个 $3^{K} \times 3^{K}$ 网格。当这个网格被划分为九个 $3^{K - 1} \times 3^{K - 1}$ 块时：
- 中央区块完全由白色细胞组成。
- 其他八个区块是 $(K - 1)$ 级地毯。

给你一个非负整数 $N$ 。
请按照指定格式打印 $N$ 级地毯。

很版的 DFS，可惜没学好。

void solve() {
    int n;cin >> n;

    int size = 1;
    for (int i = 0; i < n; ++i) size *= 3;

    vector<string> c(size, string(size, '#'));

    auto dfs = [&](auto self, int n, int size, int x, int y) ->void {
        if (n == 0) {
            c[x][y] = '#';
            return;
        }
        int newSize = size / 3;
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (i == 1 && j == 1) {
                    for (int ix = x + newSize; ix < x + 2 * newSize; ++ix) {
                        for (int iy = y + newSize; iy < y + 2 * newSize; ++iy) {
                            c[ix][iy] = '.';
                        }
                    }
                } else {
                    self(self, n - 1, newSize, x + i * newSize, y + j * newSize);
                }
            }
        }
        };

    dfs(dfs, n, size, 0, 0);

    for (auto x : c) cout << x << '\n';
}

Rank 1 大佬的代码：只需要考虑那些需要输出 . 或 # 即可。(妙！)

int main() {
	int n;cin >> n;
	int p = 1;
	for(int i = 0;i < n;++i) {
		p *= 3;
	}
	for(int i = 0;i < p;++i) {
		for(int j = 0;j < p;++j) {
			int s = 0;
			int a = i, b = j;
			for(int x = 0;x < n;++x) {
				s = s || a % 3 == 1 && b % 3 == 1;
				a /= 3;
				b /= 3;
			}
			cout.put("#."[s]);
		}
		cout << '\n';
	}
}

D - 88888888

对于正整数 $N$ ，设 $V_{N}$ 是由 $N$ 恰好连接 $N$ 次所组成的整数。
更确切地说，把 $N$ 看作一个字符串，连接它的 $N$ 份，并把结果看作一个整数，得到 $V_{N}$ 。

求 $V_{N}$ $mod 998244353$

考察能否想到等比数列公式...^[1]

$s = n . s i z e ()$

$V_{n} = n + n \times 10^{s^{1}} + n \times 10^{s^{2}} + \dots + n \times 10^{s^{n - 1}} = n (1 + 10^{s^{1} + \dots + 10^{s^{n - 1}}}) = \frac{n (10^{s n} - 1)}{10^{s} - 1} (\mod 998244353)$

知道等比数列即解决。

注意：这里 $s \times n \leq 18 \times 10^{18} < 2 \times 10^{19}$ ，超出了 long long 的范围，可以强转 int128 或者将 $10^{s}$ 和 $10^{n}$ 分开计算，这里直接开 int128.

void solve() {
    int n;cin >> n;
    int s = to_string(n).size();
    int x = n % mod * (qpow(10, (__int128_t)s * n) % mod - 1) % mod;x %= mod;
    int y = qpow(10, s) - 1;y %= mod;
    cout << x * qpow(y, mod - 2) % mod << '\n';
}

E - Reachability in Functional Graph

有一个有向图，图中有 $N$ 个顶点，编号为 $1$ 至 $N$ ，有 $N$ 条边。
每个顶点的外度为 $1$ ，顶点 $i$ 的边指向顶点 $a_{i}$ 。
计算顶点 $(u, v)$ 与顶点 $u$ 之间可以到达顶点 $v$ 的顶点对 $(u, v)$ 的个数。

这里，如果存在长度为 $K + 1$ 的顶点序列 $w_{0}, w_{1}, \dots, w_{K}$ 且满足以下条件，则顶点 $v$ 可以从顶点 $u$ 到达。其中，如果 $u = v$ 总是可达的。

$w_{0} = u$ .
$w_{K} = v$ .
每个 $0 \leq i < K$ 都有一条从顶点 $w_{i}$ 到顶点 $w_{i + 1}$ 的边。

Solution

基环树 / 拓扑排序 /缩点

$n$ 个点 $n$ 条有向边即构成了一个基环树, 一定有且仅有一个环。断环和分类讨论是基环树常用的手段。

法一：拓扑排序

这个题目可以分为三种情况：

对于一条链：设链上的点个数为 $x$ ，则对数为 $\frac{n (n + 1)}{2}$
对于一个环：设环上的点个数为 $y$ ，则对数为 $y^{2}$
对于链和环结合的部分：则增加的对数为 $x \times y$

将各个部分加起来即可。

示例图：

代码：先进行拓扑排序顺便将链上的部分计算了，在环中部分，计算出 环中点的个数 和 能到环的点的个数 即可。

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> to(n + 1), in(n + 1);
    for (int i = 1;i <= n;i++) {
        cin >> to[i];
        ++in[to[i]];
    }
    queue<int>q;
    for (int i = 1;i <= n;i++) {
        if (!in[i])q.push(i);
    }
    int ans = 0;
    vector<int>f(n + 1);
    while (q.size()) {
        auto x = q.front();q.pop();
        ++f[x];
        f[to[x]] += f[x];
        ans += f[x];
        if (--in[to[x]] == 0){
            q.push(to[x]);
        }
    }
    vector<int> vis(n + 1);

    for (int i = 1;i <= n;i++) {
        if (in[i] > 0) {
            int cnt = 0, sum = 0;
            for (int j = i;!vis[j];j = to[j]) {
                ++cnt;
                sum += f[j];
                vis[j] = 1;
            }
            ans += cnt * (cnt + sum);
        }
    }
    cout << ans << '\n';
}

法二：缩点

首先还是找环，找到环后将环缩成一个点，这样对于这个图就好处理了。

对于这个环的权重为 环中点的个数，对于其他的点，权重即为 1。

然后这个图就变为了一个有向无环图(DAG)，只需要记忆化搜索即可解决本题。

代码：

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), vis(n + 1), f(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= n;i++) {//找环的步骤
        if (vis[i])continue;
        int u = i;
        while (1) {
            if (vis[u]) {
                if (vis[u] == i) {
                    int x = a[u], cnt = 1;
                    while (x != u) {
                        x = a[x];cnt++;
                    }
                    f[u] = cnt;
                    x = a[u];
                    while (x != u) {
                        f[x] = cnt;x = a[x];
                    }
                }
                break;
            }
            vis[u] = i;
            u = a[u];
        }
    }
    int ans = 0;
    auto dfs = [&](auto self, int x) {
        if (f[x])return f[x];
        return f[x] = self(self, a[x]) + 1;
        };
    for (int i = 1;i <= n;i++)ans += dfs(dfs, i);
    cout << ans << '\n';
}

F - Two Sequence Queries

给你长度为 $N$ 、 $A = (A_{1}, A_{2}, \dots, A_{N})$ 和 $B = (B_{1}, B_{2}, \dots, B_{N})$ 的序列。
您还得到了 $Q$ 个查询，需要按顺序处理。

查询有三种类型：

1 l r x : 在 $A$ 数组的 $[l, r]$ 区间加 $x$
2 l r x : 在 $B$ 数组的 $[l, r]$ 区间加 $x$
3 l r : 查询 $\sum_{i = l}^{r} (A_{i} \times B_{i})$ $mod 998244353$

Solution

线段树

线段树经典题目

对于单个点 $(a_{i}, b_{i})$ 加上 $(x, y)$ ，则：

则 $a_{i} \times b_{i} = (a_{i} + x) (b_{i} + y) = a_{i} b_{i} + x b_{i} + y a_{i} + x y$

对于区间 $[l, r]$ 分别加上 $x, y$ ，则：

$\sum_{i = l}^{r} (a_{i} \times b_{i}) = \sum_{i = l}^{r} (a_{i} b_{i} + x b_{i} + y a_{i} + x y) = \sum_{i = l}^{r} a_{i} b_{i} + x \sum b_{i} + y \sum_{i = l}^{r} a_{i} + x y (r - l + 1)$

这样只需要维护 4 个信息： $\sum a_{i}, \sum b_{i}, \sum a_{i} b_{i}, l e n$

对于 $a_{i}, b_{i}$ 本身， $\sum_{i = l}^{r} (a_{i} + x) = \sum_{i = l}^{r} a_{i} + (r - l + 1) x, \sum_{i = l}^{r} (b_{i} + x) = \sum_{i = l}^{r} b_{i} + (r - l + 1) x$

需要开记录 $\sum a_{i}, \sum b_{i}, \sum a_{i} b_{i}$ 信息的数组 $s a, s b, s a b$ ，和 lazy tag：ta, tb

代码：(两种码风：结构体(我觉得这个方便一点)和直接开数组)

#define lc u<<1
#define rc u<<1|1
constexpr int mod = 998244353, N = 2e5 + 10;
int a[N], b[N];
struct Tree {
    int l, r, sa, sb, sab, ta, tb;
}tr[N << 2];
void pushup(int u) {
    tr[u].sa = (tr[lc].sa + tr[rc].sa) % mod;
    tr[u].sb = (tr[lc].sb + tr[rc].sb) % mod;
    tr[u].sab = (tr[lc].sab + tr[rc].sab) % mod;
}
void ca(int u, int x) {
    tr[u].sa = (tr[u].sa + x * (tr[u].r - tr[u].l + 1)) % mod;
    tr[u].sab = (tr[u].sab + x * tr[u].sb) % mod;
    tr[u].ta = (tr[u].ta + x) % mod;
}
void cb(int u, int x) {
    tr[u].sb = (tr[u].sb + x * (tr[u].r - tr[u].l + 1)) % mod;
    tr[u].sab = (tr[u].sab + x * tr[u].sa) % mod;
    tr[u].tb = (tr[u].tb + x) % mod;
}
void pushdown(int u) {
    ca(lc, tr[u].ta);
    ca(rc, tr[u].ta);
    tr[u].ta = 0;
    cb(lc, tr[u].tb);
    cb(rc, tr[u].tb);
    tr[u].tb = 0;
}
void build(int u, int l, int r) {
    tr[u] = {l,r,a[l],b[l],a[l] * b[l] % mod,0,0};
    if (l == r)return;
    int m = l + r >> 1;
    build(lc, l, m);
    build(rc, m + 1, r);
    pushup(u);
}
void modify1(int u, int l, int r, int x) {
    if (l <= tr[u].l && tr[u].r <= r) {
        ca(u, x);
        return;
    }
    int m = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    if (l <= m) modify1(lc, l, r, x);
    if (r > m) modify1(rc, l, r, x);
    pushup(u);
}
void modify2(int u, int l, int r, int x) {
    if (l <= tr[u].l && tr[u].r <= r) {
        cb(u, x);
        return;
    }
    int m = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    if (l <= m) modify2(lc, l, r, x);
    if (r > m) modify2(rc, l, r, x);
    pushup(u);
}
int query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sab;
    int m = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    int sum = 0;
    if (l <= m) sum = (sum + query(lc, l, r)) % mod;
    if (r > m) sum = (sum + query(rc, l, r)) % mod;
    return sum;
}
void solve() {
    int n, q;cin >> n >> q;
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= n;i++)cin >> b[i];
    build(1, 1, n);
    while (q--) {
        int op, l, r;cin >> op >> l >> r;
        if (op == 1) {
            int x;cin >> x;
            modify1(1, l, r, x);
        } else if (op == 2) {
            int x;cin >> x;
            modify2(1, l, r, x);
        } else {
            cout << query(1, l, r) << '\n';
        }
    }
}

等比数列求和公式： $\frac{a_{1} (1 - q^{n})}{1 - q}$ ↩︎

A - Sanitize Hands

B - Uppercase and Lowercase

C - Sierpinski carpet

D - 88888888

E - Reachability in Functional Graph

Solution

法一 ：拓扑排序

法二 ：缩点

F - Two Sequence Queries

Solution

法一：拓扑排序

法二：缩点