A 输入输出问题

照题意输出即可

#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 = "3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679"; 

int main()
{
    int n = read();
    for (int i = 0; i <= n + 1; i++)
    {
        cout << s[i];
    }
    return 0;
}

B 排序+查找

按题意查找 $x$ 后排序即可

#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;
}

struct node
{
    int a, id;
    bool operator < (const node &A) const
    {
        if (a != A.a)
        {
            return a < A.a;
        }
        return id < A.id;
    }
} st[1005];

int n, k = 1, x, c[1005], a[1005][1005], cnt;

int main()
{
    n = read();
    for (int i = 1; i <= n; i++)
    {
        c[i] = read();
        for (int j = 1; j <= c[i]; j++)
        {
            a[i][j] = read();
        }
    }
    x = read();
    bool flag = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= c[i]; j++)
        {
            if (a[i][j] == x)
            {
                st[++cnt].a = c[i];
                st[cnt].id = i;
                flag = 1;
                break;
            }
        }
    }
    if (flag == 0)
    {
        cout << "0" << endl;
        return 0;
    }
    sort(st + 1, st + cnt + 1);
    for (int i = 2; i <= cnt; i++)
    {
        if (st[i].a == st[i - 1].a)
        {
            k++;
        }
        else
        {
            break;
        }
    }
    cout << k << endl;
    for (int i = 1; i <= k; i++)
    {
        cout << st[i].id << " ";
    }
    return 0;
}

C 链式前向星

记 $nxt_i$ 为上一个 $ci$ 出现的位置，$h{c_i}$ 为最后一个 $c_i$ 出现位置。

按题意处理后模拟即可

#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 n, m, c[200005], nxt[200005], h[200005];

int main()
{
    n = read(), m = read();
    cin >> s;
    s = " " + s;
    for (int i = 1; i <= n; i++)
    {
        c[i] = read();
        nxt[i] = h[c[i]];
        h[c[i]] = i;
    }
    int lst = 0;
    for (int i = 1; i <= m; i++)
    {
        for (int j = h[i]; j; j = nxt[j])
        {
            if (j == h[i])
            {
                lst = j;
                continue;
            }
            swap(s[j], s[lst]);
            lst = j;
        }
    }
    for (int i = 1; i < s.size(); i++)
    {
        cout << s[i];
    }
    return 0;
}

D 简单动脑筋

乍一看是数据结构，实际上先储存操作，再找到最后一个非 $1$ 操作，此操作之前的全部大写或小写，后面直接模拟即可。

时间复杂度：$O(n + q)$

#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;

struct ask
{
    int op, x;
    char c;
} a[500005];

int main()
{
    int n = read(), q;
    cin >> s;
    s = " " + s;
    q = read();
    int ji = 0, id = 0;
    for (int i = 1; i <= q; i++)
    {
        cin >> a[i].op >> a[i].x >> a[i].c;
        if (a[i].op == 2 || a[i].op == 3)
        {
            ji = a[i].op;
            id = i;
        }
    }
    if (id == 0)
    {
        for (int i = 1; i <= q; i++)
        {
            s[a[i].x] = a[i].c;
        }
    }
    else if (ji == 2)
    {
        for (int i = 1; i <= id; i++)
        {
            if (a[i].op == 1)
            {
                s[a[i].x] = a[i].c;
            }
        }
        for (int i = 1; i <= n; i++)
        {
            if (s[i] <= 'Z' && s[i] >= 'A')
            {
                s[i] = s[i] - 'A' + 'a';
            }
        }
        for (int i = id + 1; i <= q; i++)
        {
            s[a[i].x] = a[i].c;
        }
    }
    else if (ji == 3)
    {
        for (int i = 1; i <= id; i++)
        {
            if (a[i].op == 1)
            {
                s[a[i].x] = a[i].c;
            }
        }
        for (int i = 1; i <= n; i++)
        {
            if (s[i] <= 'z' && s[i] >= 'a')
            {
                s[i] = s[i] - 'a' + 'A';
            }
        }
        for (int i = id + 1; i <= q; i++)
        {
            s[a[i].x] = a[i].c;
        }
    }
    for (int i = 1; i < s.size(); i++)
    {
        cout << s[i];
    }
    return 0;
}

E dp？

对于 $i:(m - 1) - 0,j:1-n$

满足$f_i = ans = \min(ans, (sum + c_j * s_j) / (s_j - z));$

其中 $sum = {Σ_{k = 1}^{s_j}} {a[j][k]}$

#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;
}

double f[110];

int n, m, c[110], s[110], a[110][110];

signed main()
{
    n = read(), m = read();
    for (int i = 1; i <= n; i++)
    {
        c[i] = read(), s[i] = read();
        for (int j = 1; j <= s[i]; j++)
        {
            a[i][j] = read();
        }
    }
    for (int i = m - 1; i >= 0; i--)
    {
        double ans = 1e18;
        f[i] = 1e18;
        for (int j = 1; j <= n; j++)
        {
            double sum = 0, z = 0;
            for (int k = 1; k <= s[j]; k++)
            {
                if (a[j][k])
                {
                    sum += f[i + a[j][k]];
                }
                else
                {
                    z++;
                }
            }
            f[i] = ans = min(ans, (sum + c[j] * s[j]) / (s[j] - z));
        }
    }
    printf("%.21f\n", f[0]);
    return 0;
}

F 并查集按秩合并+dfs+线性求逆元

首先预处理出 $i$ 关于 $998244353$ 的逆元 $ivi = mod - iv{mod % i} * (mod / i) % mod$

每次比赛可以看做 $2$ 个并查集的合并，合并时要处理该并查集大小

最后 $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;
}

const int mod = 998244353;

int n, ans[201000], f[201000];
int ls[401000], rs[401000], iv[201000], sz[401000];

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

void dfs(int x, int t)
{
    if (x <= n)
    {
        ans[x] = t;
        return;
    }
    dfs(ls[x], (t + sz[ls[x]] * iv[sz[x]] % mod) % mod);
    dfs(rs[x], (t + sz[rs[x]] * iv[sz[x]] % mod) % mod);
}

signed main()
{
    n = read();
    iv[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        iv[i] = mod - iv[mod % i] * (mod / i) % mod;
    }
    for (int i = 1; i <= n; i++)
    {
        f[i] = i, sz[i] = 1;
    }
    for (int i = 1;i < n;i++)
    {
        int xx = read(), yy = read();
        xx = find(xx), yy = find(yy);
        sz[n + i] = sz[xx] + sz[yy];
        ls[n + i] = xx, rs[n + i] = yy;
        f[xx] = f[yy] = f[n + i] = n + i;
    }
    dfs(n * 2 - 1, 0);
    for (int i = 1; i <= n; i++)
    {
        cout << ans[i] << " ";
    }
    return 0;
}