A 运动会

知识点：字符串、计数

题面保证支柱总是成组出现并组成合法栏架，而一个栏架恰好需要两个支柱 $\texttt{|}$，所以只需要统计字符串中 $\texttt{|}$ 的数量，答案就是其一半。

时间复杂度 $\mathcal{O}(n)$。

void solve() {
    int n;
    string s;
    cin >> n >> s;
    cout << count(s.begin(), s.end(), '|') / 2 << endl;
}

B 数方格

知识点：异或、构造

不妨直接选择第 $1$ 行和第 $1$ 列，设除 $(1,1)$ 以外所有被选中格子的异或和为 $s$，把 $a_{1,1}$ 改成 $s\oplus x$ 后，整行整列的异或和就恰好为 $x$。

时间复杂度 $\mathcal{O}(n+m)$。

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for (auto &u : a)
        for (auto &v : u) cin >> v;
    int x;
    cin >> x;
    int s = 0;
    for (int i = 1; i < n; i++) s ^= a[i][0];
    for (int i = 1; i < m; i++) s ^= a[0][i];
    cout << "YES" << endl;
    cout << "1 1 " << (s ^ x) << endl;
    cout << "1 1" << endl;
}

C 列竖式

知识点：字符串、高精度加法

把两个数按小数点对齐，整数部分在左侧补 $\texttt{0}$，小数部分在右侧补 $\texttt{0}$。之后从最低位开始模拟十进制加法，每当当前位产生进位，就把答案加一，并把进位继续传给更高位。

时间复杂度 $\mathcal{O}(L)$。

void solve() {
    string a1, a2, b1, b2;
    getline(cin, a1, '.');
    getline(cin, a2);
    getline(cin, b1, '.');
    getline(cin, b2);
    while (a1.size() < b1.size()) a1 = '0' + a1;
    while (b1.size() < a1.size()) b1 = '0' + b1;
    a1 = '0' + a1, b1 = '0' + b1;
    while (a2.size() < b2.size()) a2 += '0';
    while (b2.size() < a2.size()) b2 += '0';
    int c = 0, ans = 0;
    for (int i = a2.size() - 1; i >= 0; --i) {
        c = a2[i] + b2[i] + c - 2 * '0';
        ans += c /= 10;
    }
    for (int i = a1.size() - 1; i >= 0; --i) {
        c = a1[i] + b1[i] + c - 2 * '0';
        ans += c /= 10;
    }
    cout << ans << endl;
}

D 走迷宫

知识点：二维前缀和、BFS

把当前位置看作矩形身体左上角的位置，那么一个位置合法，当且仅当这个 $a\times b$ 矩形不越界且内部没有墙。先对墙格做二维前缀和，就能 $\mathcal{O}(1)$ 判断一个矩形是否合法，再在所有合法位置上从 $S$ 开始 BFS，判断是否能到达 $E$。

时间复杂度 $\mathcal{O}(nm)$。

int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

void solve() {
    int n, m, a, b;
    cin >> n >> m >> a >> b;
    vector<vector<int>> g(n, vector<int>(m));
    pii st, ed;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            char c;
            cin >> c;
            if (c == 'S')
                st = {i, j};
            else if (c == 'E')
                ed = {i, j};
            if (c == '#')
                g[i][j] = 1;
            else
                g[i][j] = 0;
        }
    vector<vector<int>> pre(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + g[i - 1][j - 1];
    auto check = [&](int x, int y) {
        if (x < 0 || y < 0 || x + a > n || y + b > m) return false;
        return pre[x + a][y + b] - pre[x][y + b] - pre[x + a][y] + pre[x][y] == 0;
    };
    vector<vector<bool>> vis(n, vector<bool>(m, 0));
    queue<pii> q;
    q.push(st);
    vis[st[0]][st[1]] = 1;
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        if (x == ed[0] && y == ed[1]) return cout << "Yes" << endl, void();
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (!check(nx, ny)) continue;
            if (vis[nx][ny]) continue;
            vis[nx][ny] = 1;
            q.push({nx, ny});
        }
    }
    cout << "No" << endl;
}

E 跷跷板

知识点：公式化简、枚举

设赶走一个小朋友后，剩余小朋友的总重量为 $S$，坐标乘重量之和为 $T$。把题目给出的力矩平衡式展开整理，有：
$$2p(S+W)=2T+Wl$$

因此合法支点唯一可能为：

$$p=\frac{2T+Wl}{2(S+W)}$$

枚举被赶走的小朋友，维护去掉后的 $S,T$，只要判断上式是否整除，且 $0\le p\le l$ 即可。中间显然会溢出，需使用 $\text{i128}$。

时间复杂度 $\mathcal{O}(n)$。

void solve() {
    int n, l, W;
    cin >> n >> l >> W;
    vector<pii> a(n);
    int sumW = 0, sumWX = 0;
    for (auto &[u, v] : a) cin >> u >> v, sumW += v, sumWX += u * v;
    int ans = 0;
    for (auto [u, v] : a) {
        int S = sumW - v, T = sumWX - u * v;
        int x = 2 * T + W * l, y = 2 * (S + W);
        ans += x % y == 0 && 0 <= x / y && x / y <= l;
    }
    cout << ans << endl;
}

F 解方程

知识点：约数计数、组合数学、生成函数、并查集

组合意义解：

对每个整数 $d$，记 $c_d$ 表示数组中能被 $d$ 整除的元素个数。对于询问 $k$，若要让所选 $k$ 个数的最大公约数至少为 $d$，就必须且只需要有不少于 $k$ 个数是 $d$ 的倍数，即 $c_d\ge k$。所以最优的最大公约数，就是所有满足 $c_d\ge k$ 的 $d$ 中最大的那个。

设这个最大值为 $g$，那么答案就是从所有 $g$ 的倍数中选出 $k$ 个数：
$$\binom{c_g}{k}$$

只需要找满足 $cnt[g] \geq k$ 的最大 $g$ 计算即可，预处理枚举 $k$ 使用 $\text{DSU}$ 维护没有被填的数字即可。

时间复杂度 $\mathcal{O}(n\sqrt{A}+DlogD + (m+n)\alpha(n) + q)$。

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

    unordered_map<int, int> mp;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        for (int d = 1; d * d <= x; d++) {
            if (x % d == 0) {
                mp[d]++;
                if (d * d != x) mp[x / d]++;
            }
        }
    }

    vector<pii> v;
    for (auto [d, c] : mp) v.push_back({d, c});
    sort(v.rbegin(), v.rend());

    vector<int> f(n + 2);
    vector<Z> ways(n + 2, 0);

    iota(f.begin(), f.end(), 0);

    auto find = [&](auto self, int x) -> int {
        if (f[x] == x) return x;
        return f[x] = self(self, f[x]);
    };

    for (auto [d, c] : v) {
        for (int k = find(find, 1); k <= c; k = find(find, k)) {
            ways[k] = C.C(c, k);
            f[k] = find(find, k + 1);
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int k;
        cin >> k;
        cout << ways[k] << endl;
    }
}

约定

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii array<int, 2>
#define endl "\n"

void solve() {

}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed << setprecision(20);
    int t = 1;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
    return 0;
}