A - 并查集板子

并查集模板，结果用二进制表示，注意要快读。

#include <cstdio>
#include <iostream>
using namespace std;

int fa[4000010], ans;

inline int read() {
    char ch = getchar();
    int ans = 0, f = 1;
    while (ch < '0' || ch > '9') {
        if (ch == '-') {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        ans = (ans << 3) + (ans << 1) + (ch ^ 48);
        ch = getchar();
    }
    return ans * f;
}

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

void uni(int x, int y) {
    int fax = find(x);
    int fay = find(y);
    if (fax != fay) {
        fa[fax] = fay;
    }
}

int main() {
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
    }
    for (int i = 0; i < m; ++i) {
        int act = read();
        if (act == 0) {
            int x = read(), y = read();
            uni(x, y);
        } else {
            int x = read(), y = read();
            ans = ((ans << 1) + (find(x) == find(y))) % 998244353;
        }
    }
    printf("%d", ans);
    return 0;
}

B - 线段树板子

\(cin,cout\)貌似会超时，要用\(scanf,printf\)或者快读，考察对\(lazy\)标记的使用。

#include <ctype.h>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define ll long long

struct node {
    ll tree, left, right, lazy;
} a[4000005];

ll n, m, add, ans, x, y, act;

ll read() {
    char x = getchar();
    ll ans = 0LL, f = 1LL;
    while (!isdigit(x)) {
        if (x == '-') f = -1LL;
        x = getchar();
    }
    while (isdigit(x)) {
        ans = (ans << 3) + (ans << 1) + (x ^ 48);
        x = getchar();
    }
    return ans * f;
}

void create(ll l, ll r, ll k) {
    a[k].lazy = 0, a[k].left = l, a[k].right = r;
    if (l == r) {
        a[k].tree = read();
        return;
    }
    ll mid = (l + r) / 2;
    create(l, mid, k * 2);
    create(mid + 1, r, k * 2 + 1);
    a[k].tree = a[k * 2].tree + a[k * 2 + 1].tree;
    return;
}

void load(ll k) {
    ll l = k * 2, r = k * 2 + 1;
    a[l].lazy += a[k].lazy;
    a[r].lazy += a[k].lazy;
    a[l].tree += a[k].lazy * (a[l].right - a[l].left + 1);
    a[r].tree += a[k].lazy * (a[r].right - a[r].left + 1);
    a[k].lazy = 0;
    return;
}

void change(ll k) {
    if (a[k].left >= x && a[k].right <= y) {
        a[k].tree += add * (a[k].right - a[k].left + 1);
        a[k].lazy += add;
        return;
    }
    if (a[k].lazy) load(k);
    ll mid = (a[k].left + a[k].right) / 2;
    if (x <= mid) change(k * 2);
    if (y >= mid + 1) change(k * 2 + 1);
    a[k].tree = a[k * 2].tree + a[k * 2 + 1].tree;
    return;
}

void inquery(ll k) {
    if (a[k].left >= x && a[k].right <= y) {
        ans += a[k].tree;
        return;
    }
    if (a[k].lazy) load(k);
    ll mid = (a[k].left + a[k].right) / 2;
    if (x <= mid) inquery(k * 2);
    if (y >= mid + 1) inquery(k * 2 + 1);
    return;
}

int main() {
    n = read();
    m = read();
    create(1, n, 1);
    while (m--) {
        act = read(), x = read(), y = read();
        if (act == 1) {
            add = read();
            change(1);
        }
        if (act == 2) {
            ans = 0LL;
            inquery(1);
            printf("%lld\n", ans);
        }
    }
    return 0;
}

C - 树状数组板子

树状数组模板，注意要开\(long\) \(long\)。

#include <iostream>
#include <cstring>
using namespace std;

long long bit[1000010];
int n, q, act, l, r;

int lowbit(int x) { return x & (-x); }

void update(int x, int k) {
    while (x <= n) {
        bit[x] += (long long)k;
        x += lowbit(x);
    }
}

long long getSum(int x) {
    long long ans = 0;
    while (x > 0) {
        ans += bit[x];
        x -= lowbit(x);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    while (cin >> n >> q) {
        memset(bit, 0, sizeof(bit));
        for (int i = 1, x; i <= n; ++i) {
            cin >> x;
            update(i, x);
        }
        while (q--) {
            cin >> act >> l >> r;
            if (act == 2) {
                cout << getSum(r) - getSum(l - 1) << endl;
            } else {
                update(l, r);
            }
        }
    }
    return 0;
}

D - 单调队列板子

用两个双向队列\(deque\)模拟单调队列来维护区间，一个单调递增，一个单调递减，使当前区间的最大最小值分别出现在两个队列的队首。

#include <cstdio>
#include <deque>
#include <iostream>
using namespace std;

int n, k, a[1000010];

int main() {
    deque<int> maxn, minn;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < k; ++i) {  // 单调队列
        while (!minn.empty() && a[i] < minn.back()) {
            minn.pop_back();
        }
        minn.push_back(a[i]);
        while (!maxn.empty() && a[i] > maxn.back()) {
            maxn.pop_back();
        }
        maxn.push_back(a[i]);
    }
    // 窗口移动求最小
    for (int i = k; i < n; ++i) {
        cout << minn.front() << " ";
        if (minn.front() == a[i - k]) {
            minn.pop_front();
        }
        while (!minn.empty() && a[i] < minn.back()) {
            minn.pop_back();
        }
        minn.push_back(a[i]);
    }
    cout << minn.front() << " ";
    cout << endl;
    // 窗口移动求最大
    for (int i = k; i < n; ++i) {
        cout << maxn.front() << " ";
        if (maxn.front() == a[i - k]) {
            maxn.pop_front();
        }
        while (!maxn.empty() && a[i] > maxn.back()) {
            maxn.pop_back();
        }
        maxn.push_back(a[i]);
    }
    cout << maxn.front() << " ";
    cout << endl;
    return 0;
}

E - 带权并查集

正解是带权并查集，这里选用了一种开三倍并查集的思想。
开了三倍大小的标记数组来表示三个物种，\(1\)到\(n\)为\(A\)物种，\(n+1\)到\(2 \times n\)为\(B\)物种，\(2 \times n + 1\)到\(3 \times n\)为\(C\)物种。
如果\(u\)吃\(v\)，则相对的\(u+n\)与\(v\)为一个物种，\(u+2\times n\)与\(v + n\)为一个物种，\(u\)与\(v + 2\times n\)为一个物种。
通过并查集关联同一物种。

#include <iostream>
#include <cstdio>
#include <ctype.h>
using namespace std;
#define MAXN 100010
#define INF 100000000
#define ll long long

ll read() {     // fast read
    ll ans = 0; int f = 1;  char x = getchar();
    while (!isdigit(x)) {
        if (x == '-')
            f = -1;
        x = getchar();
    }
    while (isdigit(x)) {
        ans = (ans << 3) + (ans << 1) + (x ^ 48);
        x = getchar();
    }
    return ans * f;
}

int fa[150050], n, k, act, u, v, ans;

int find(int x) {   // find father
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int main() {
    n = read(), k = read();
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
        fa[i + n] = i + n;
        fa[i + n * 2] = i + n * 2;
    }
    while (k--) {
        act = read(), u = read(), v = read();
        if (u > n || v > n) {
            ans++;
            continue;
        }
        else if (act == 1) {
            if (find(u) == find(v + n) || find(v) == find(u + n)) {
                ans++;
            }
            else {  // same father
                fa[find(u)] = find(v);
                fa[find(u + n)] = find(v + n);
                fa[find(u + n * 2)] = find(v + n * 2);
            }
        }
        else {
            if (find(u) == find(v + n) || find(u) == find(v)) {
                ans++;
            }
            else {  // u -> v
                fa[find(u + n)] = find(v);
                fa[find(u + n * 2)] = find(v + n);
                fa[find(u)] = find(v + n * 2);
            }
        }
    }
    cout << ans;
    return 0;
}

正解如下：

// 带权并查集
#include <cstdio>
#include <iostream>
using namespace std;

int f[50005], d[50005], n, k, d1, x, y, ans;

int find(int x) {
    if (x != f[x]) {
        int xx = f[x];
        f[x] = find(f[x]);
        d[x] = (d[x] + d[xx]) % 3;
    }
    return f[x];
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        f[i] = i;
        d[i] = 0;
    }
    for (int i = 1; i <= k; i++) {
        scanf("%d%d%d", &d1, &x, &y);
        if ((d1 == 2 && x == y) || (x > n || y > n)) {
            ans++;
            continue;
        }
        if (d1 == 1) {
            if (find(x) == find(y)) {
                if (d[x] != d[y]) ans++;
            } else {
                d[f[x]] = (d[y] - d[x] + 3) % 3;
                f[f[x]] = f[y];
            }
        }
        if (d1 == 2) {
            if (find(x) == find(y)) {
                if (d[x] != (d[y] + 1) % 3) ans++;
            } else {
                d[f[x]] = (d[y] - d[x] + 4) % 3;
                f[f[x]] = f[y];
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

F - ST表板子

ST表模板。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int num[50005], minn[50005][50], maxn[50005][50], n, q;

void stPreWork() {
    for (int i = 1; i <= n; ++i) {
        minn[i][0] = num[i];
        maxn[i][0] = num[i];
    }
    for (int j = 1; (1 << j) <= n; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            minn[i][j] = min(minn[i][j - 1], minn[i + (1 << (j - 1))][j - 1]);
            maxn[i][j] = max(maxn[i][j - 1], maxn[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int stQuery(int l, int r) {
    int k = 0;
    while (l + (1 << (k + 1)) - 1 <= r) {
        k++;
    }
    return max(maxn[l][k], maxn[r - (1 << k) + 1][k]) - min(minn[l][k], minn[r - (1 << k) + 1][k]);
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &num[i]);
    }
    stPreWork();
    for (int i = 1, l, r; i <= q; ++i) {
        scanf("%d%d", &l, &r);
        printf("%d\n", stQuery(l, r));
    }
    return 0;
}

G - 要求用并查集做

通过并查集来建立信息传递关系。

#include <iostream>
using namespace std;

int n, fa[200010], ans = 0x3f3f3f3f, cnt, x;

int get(int x) {
    cnt++;
    return fa[x] == x ? x : get(fa[x]);
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
    }
    for (int i = 1; i <= n; ++i) {
        cnt = 0;
        cin >> x;
        if (get(x) == i) {
            ans = min(ans, cnt);
        } else {
            fa[i] = x;
        }
    }
    cout << ans;
    return 0;
}

H - 欧拉筛

由于任意一个数\(n\)可以表示为\(n=p^{a_1}_1 + {p}^{a_2}_2+...\)，\(p_1,p_2...\)为质数。
所以\(n=p_i^{a_i} \times x\)，由题意知\(a_i\)只能为\(1\)或\(2\)，否则无法拆分出符合条件的情况。
当\(a_i\)为\(1\)时，一个素数有两种拆分方式，所以贡献为\(2\)；当\(a_i\)为\(2\)时，只有将一个\(p_i\)分配到\(x\)里去，且\(x\)本身不可整除\(p_i\)时，才能满足条件，因此贡献为\(1\)。
可得到递推式：\(\left\{ \begin{matrix} &f(n)=2\times f(x),&a_i=1 \\ &f(n)=f(x),&a_i=2 \\ &f(n)=0,&an=3 \end{matrix} \right.\)。
再用前缀和记录结果。每次查询为\(O(1)\)。

#include <cstdio>
#include <iostream>
using namespace std;
#define N 20000010

bool vis[N];
int f[N], prime[N], T, n;
long long sum[N];

void init() {
    int cnt = 0;
    f[1] = 1;
    for (int i = 2; i <= N; ++i) {
        if (!vis[i]) {
            prime[++cnt] = i;
            f[i] = 2;
        }
        for (int j = 1; j <= cnt && (prime[j] * i) < N; ++j) {
            int num = i * prime[j];
            vis[num] = true;
            if (i % prime[j]) {
                f[num] = 2 * f[i];
            } else if (i % (prime[j] * prime[j]) == 0) {
                f[num] = 0;
            } else {
                f[num] = f[i / prime[j]];
                break;
            }
        }
    }
    for (int i = 1; i <= N; ++i) {
        sum[i] = sum[i - 1] + f[i];
    }
}

int main() {
    init();
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        printf("%lld\n", sum[n]);
    }
    return 0;
}