前言

连我都能做六题，难道不简单吗？

讲解

A and B 循环查找

过于简单，略

C 前缀和

预处理相邻两个相同的对数的前缀和

直接 $s_r - s_l$ 即可

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

int read()
{
    int f = 1, k = 0;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
        {
            f = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        k = k * 10 + c - '0';
        c = getchar();
    }
    return f * k;
}

string s;
int ji[1000005];

int main()
{
    int n = read(), m = read();
    cin >> s;
    ji[0] = 0;
    for (int i = 1; i < n; i++)
    {
        ji[i] = ji[i - 1];
        if (s[i] == s[i - 1])
        {
            ji[i]++;
        }
    }
    while (m--)
    {
        int l = read(), r = read();
        printf("%d\n", ji[r - 1] - ji[l - 1]);
    }
    return 0;
}

D 栈的应用

与 CSP-S 2023 T2 相似

字符依次进栈，若栈最前面三个字符为 ABC，弹出，最后依次输出从栈底到栈顶的元素即可。

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

int read()
{
    int f = 1, k = 0;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
        {
            f = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        k = k * 10 + c - '0';
        c = getchar();
    }
    return f * k;
}

char st[1000005];
int tp;

int main()
{
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++)
    {
        st[++tp] = s[i];
        while (tp >= 3 && st[tp] == 'C' && st[tp - 1] == 'B' && st[tp - 2] == 'A')
        {
            tp -= 3;
        }
    }
    for (int i = 1; i <= tp; i++)
    {
        cout << st[i];
    }
    return 0;
}

E 暴搜+并查集

考虑用 dfs 枚举出边的可能性，用并查集判断是否为树，然后找最小答案即可。

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

int read()
{
    int f = 1, k = 0;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
        {
            f = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        k = k * 10 + c - '0';
        c = getchar();
    }
    return f * k;
}

int a[100005], b[100005], c[100005], n, m, k;
int xa[100005], xb[100005], f[100005], ans = 1e18;

int find(int x)
{
    if (x == f[x])
    {
        return f[x];
    }
    return f[x] = find(f[x]);
}

bool check()
{
    for (int i = 1; i <= n; i++)
    {
        f[i] = i;
    }
    for (int i = 1; i < n; i++)
    {
        int aa = find(xa[i]), bb = find(xb[i]);
        if (aa == bb)
        {
            return 0;
        }
        f[aa] = bb;
    }
    return 1;
}

void dfs(int x, int nw, int sum)
{
    if (x == 0)
    {
        if (check())
        {
            ans = min(ans, sum % k);
        }
        return;
    }
    if (nw == 0)
    {
        return;
    }
    dfs(x, nw - 1, sum);
    xa[x] = a[nw], xb[x] = b[nw];
    dfs(x - 1, nw - 1, (sum + c[nw]) % k);
}

signed main()
{
    n = read(), m = read(), k = read();
    for (int i = 1; i <= m; i++)
    {
        a[i] = read(), b[i] = read(), c[i] = read();
    }
    dfs(n - 1, m, 0);
    printf("%lld\n", ans);
    return 0;
}

F 并查集的应用

每次相当于把 $x_{ai}$ 与 $x{b_i}$ 相连即可，若已联通，则判断是否满足限制即可。

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

int read()
{
    int f = 1, k = 0;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
        {
            f = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        k = k * 10 + c - '0';
        c = getchar();
    }
    return f * k;
}

int n, q;

int f[200005], w[200005];

int find(int x)
{
    if (f[x] == x)
    {
        return x;
    }
    int kly = find(f[x]);
    w[x] += w[f[x]];
    return f[x] = kly;
}

signed main()
{
    n = read(), q = read();
    for (int i = 1; i <= n; i++)
    {
        f[i] = i, w[i] = 0;
    }
    for (int i = 1; i <= q; i++)
    {
        int a = read(), b = read(), d = read();
        int aa = find(a), bb = find(b);
        if (aa == bb)
        {
            if (w[b] - w[a] == d)
            {
                printf("%lld ", i);
            }
            continue;
        }
        f[aa] = bb;
        w[aa] = w[b] - w[a] - d;
        printf("%lld ", i);
    }
    return 0;
}