A

由于答案是关于 的多项式。于是暴力搜索出 的解然后拉格朗日插值。具体地：
$$

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int P = 998244353;
ll n, m, k, inv[5];
ll C(ll x, int t) {
    ll res = 1;
    for (int i = 0; i != t; i++) res = 1ll * res * (x - i) % P * inv[i + 1] % P;
    return res;
}
int main() {
    scanf("%lld%lld%lld", &n, &m, &k);
    n--;
    m--;
    inv[0] = 0;
    inv[1] = 1;
    inv[2] = (P + 1) / 2;
    inv[3] = (P + 1) / 3;
    inv[4] = 1ll * inv[2] * inv[2] % P;
    if (k == 1)
        puts("1");
    if (k == 2)
        printf("%lld", (n + m) % P);
    if (k == 3)
        printf("%lld", (m * n * 4 + C(m, 2) + C(n, 2)) % P);
    if (k == 4)
        printf("%lld", (n * m + (n * C(m, 2) + m * C(n, 2)) % P * 11 + C(m, 3) + C(n, 3)) % P);
    if (k == 5)
        printf("%lld", (C(m, 2) * C(n, 2) % P * 64 + (n * C(m, 3) + m * C(n, 3)) % P * 26 +
                        (n * C(m, 2) + m * C(n, 2)) % P * 7 + C(m, 4) + C(n, 4)) %
                           P);
    return 0;
}

B

若没有对称轴，答案为 .

若有一条对称轴，凸包上所有点作一条到对称轴的垂线，发现体积是多个圆台体积相加。

若有多个对称轴，那么一定交于同一点。最终扫过的体积就是以到这个点距离最远的点为半径的球。

问题转化为求对称轴。我们找到这个凸多边形的几何中心 。若这个多边形存在对称轴，那么几何中心一定在这条对称轴上。用点到几何中心的长度代表点，用边端点的两个点到几何中心的夹角来代表边。把得到的数组复制一遍再接上去。那么如果存在一个长为 的回文串，即存在一个对称轴。

#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const int MAXN = 1e5 + 10;
const ld EPS = 1e-6;
const ld Pi = acos(-1);
int n, Hs, L1, St, Cnt, Len[MAXN * 4];
ll H[MAXN * 4];
ld Maxr;
struct Point {
    ld X, Y;
    Point() { X = Y = 0; }
    Point(ld Nx, ld Ny) { X = Nx, Y = Ny; }
    ld Len2() { return X * X + Y * Y; }
    ld Dot(Point S) { return X * S.X + Y * S.Y; }
    ld Len1() { return sqrt(X * X + Y * Y); }
    Point Num(ld S) { return Point(X * S, Y * S); }
    Point operator+(Point S) { return Point(X + S.X, Y + S.Y); }
    Point operator-(Point S) { return Point(X - S.X, Y - S.Y); }
} Dot[MAXN * 4], Ht;
ld Min(ld A, ld B) { return A < B ? A : B; }
ld Max(ld A, ld B) { return A > B ? A : B; }
ld Calc() {
    ld Lr, Nr, Dt, Ret = 0;
    int Sl, Sr;
    Point Last, Now;
    if (St & 1)
        Now = Dot[St / 2 + 1], Lr = 0, Sl = Sr = St / 2 + 1, Nr = 0;
    else
        Sl = St / 2, Sr = St / 2 + 1, Now = (Dot[Sl] + Dot[Sr]).Num(0.5), Nr = (Dot[Sl] - Dot[Sr]).Len1() / 2;
    // printf("St=%d\n",St);
    for (Sl--, Sr++; Sr - Sl + 1 <= n; Sl--, Sr++)
        Last = Now, Lr = Nr, Now = (Dot[Sl] + Dot[Sr]).Num(0.5), Nr = (Dot[Sr] - Dot[Sl]).Len1() / 2,
        Dt = (Now - Last).Len1(), Ret += Pi * (Lr * Lr + Nr * Nr + Lr * Nr) * Dt / 3;
    return Ret;
}
void Symmetry() {
    for (int i = 1; i <= n; i++)
        H[++Hs] = (Dot[i] - Dot[i - 1]).Dot(Dot[i + 1] - Dot[i]), H[++Hs] = (Dot[i + 1] - Dot[i]).Len2();
    for (int i = 1; i <= Hs; i++) H[i + Hs] = H[i];
    H[0] = -5233, H[4 * n + 1] = -233, Hs <<= 1;
    for (int i = 1, Nr = 0, Mid = 1; i <= Hs; i++) {
        Len[i] = Min(Nr - i + 1, Len[2 * Mid - i]);
        while (Len[i] + i > Nr && i - Len[i] >= 0 && H[i + Len[i]] == H[i - Len[i]]) Len[i]++, Nr++;
        i + Len[i] > Nr ? Mid = i : 0;
    }
    for (int i = 1; i <= n; i++) Ht = Ht + Dot[i];
    Ht = Ht.Num(1.0 / n);
    for (int i = 1; i <= n; i++) Maxr = Max(Maxr, (Dot[i] - Ht).Len1());
    for (int i = n + 1; i <= n * 3; i++)
        if (Len[i] >= n)
            St = i, Cnt++;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%Lf%Lf", &Dot[i].X, &Dot[i].Y), Dot[i + n] = Dot[i];
    Dot[0] = Dot[n], Symmetry(), Cnt /= 2;
    if (Cnt == 0)
        return puts("0"), 0;
    if (Cnt >= 2)
        return printf("%.10Lf\n", 4 / 3.0 * Pi * Maxr * Maxr * Maxr), 0;
    printf("%.10Lf\n", Calc());
}

C

如果 相同就无解。考虑构造答案，没有出现过的数字随便放。剩下的数字每种最多出现一个，错排即可。

#include <bits/stdc++.h>
using namespace std;
int a[100005], b[100005];
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            b[i] = i;
        }
        bool flag = 1;
        for (int i = 1; i <= n; i++) {
            if (a[i] == b[i]) {
                flag = 0;
                for (int j = 1; j <= n; j++) {
                    if (i != j && a[i] != b[j] && a[j] != b[i]) {
                        swap(b[i], b[j]);
                        flag = 1;
                    }
                }
                if (flag == 0)
                    break;
            }
        }
        if (flag) {
            cout << "YES\n";
            for (int i = 1; i <= n; i++) {
                cout << b[i] << " ";
            }
            cout << endl;
        } else
            cout << "NO\n";
    }
}

E

对于下凸序列，若一对数 ，分类讨论 在左边还是右边看逆序对情况，发现左左和右左会贡献 ，也就是只和 放在哪里有关。

若 ，发现右左和右右会贡献 ，也就是只和 放在哪里有关。

综上，对于某一个数 ，若将其放在左边，贡献为 的个数；若将其放在右侧， 贡献为 的个数。我们不妨分别将数值设为 和 。

随着数列的增加， 是不会变的， 会越变越大。当 的时候，我们就会把这个数放在左边，否则放在右边。

于是用线段树维护每个数 的值。当这个值小于等于 的时候我们就把它放在左边去。同时我们需要维护每个数的 ，也用线段树维护。

对于上凸序列，我们只需要把所有数取负然后离散化做一遍下凸的，两个答案取 。时间复杂度 。

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

int i, j, k, n, m, t, a[200500], p[200500], g[200500], f[200500];
ll res[200500];

void add(int x, int y) {
    for (; x <= 200005; x += (-x & x)) {
        f[x] += y;
    }
}
int get(int x, int y = 0) {
    for (; x; x -= (-x & x)) {
        y += f[x];
    }
    return y;
}

void fuck() {
    vector<int> v[n + 5];
    memset(f, 0, sizeof(f));
    for (i = 1; i <= n; i++) {
        g[i] = get(a[i]);
        add(a[i], 1);
        p[a[i]] = i;
    }
    memset(f, 0, sizeof(f));
    for (i = 1; i <= n; i++) {
        int l = p[i], r = n, md, ans = p[i];
        while (l <= r) {
            md = (l + r) / 2;
            if (get(md) > 2 * g[p[i]])
                r = md - 1;
            else
                ans = max(ans, md), l = md + 1;
        }
        v[ans].push_back(i);
        add(p[i], 1);
    }
    memset(f, 0, sizeof(f));
    ll cur = 0;
    for (i = 1; i <= n; i++) {
        cur += get(n) - get(a[i]);
        for (auto j : v[i]) {
            add(j, -1);
        }
        add(a[i], 1);
        res[i] = min(res[i], cur);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> a[i];
        p[i] = a[i];
        res[i] = 1e18;
    }
    sort(p + 1, p + n + 1);
    for (i = 1; i <= n; i++) {
        a[i] = lower_bound(p + 1, p + n + 1, a[i]) - p;
    }
    fuck();
    for (i = 1; i <= n; i++) a[i] = n + 1 - a[i];
    fuck();
    for (i = 1; i <= n; i++) cout << res[i] << '\n';
}

F

所有能消除的组合是形如 。那么不妨对于 的数 ，改成 。这样的话两个数能消除当且仅当他们相同。于是可以直接用栈模拟一边。

#include <stdio.h>
int main() {
    int n, x, l, r, i = 0, s = 0, a[100002];
    for (scanf("%d%d", &n, &x); i < n; ++i) {
        scanf("%d", &a[i]);
        if (i && (a[i] == a[i - 1] || a[i] + a[i - 1] == x))
            ++s, i -= 2, n -= 2;
    }
    for (i = 0; i * 2 + 1 < n && (a[i] == a[n - 1 - i] || a[i] + a[n - 1 - i] == x); ++i) ++s;
    printf("%d", s);
}

G

首先发现，.* 能匹配所有字符串。所以肯定有最小长度 。

对于 ，长度为 ，方案数为 。

否则枚举所有可能的长度为 的表达式，然后判断是否能匹配即可。

#include <bits/stdc++.h>
using namespace std;
int i, n, m, ans, a;
char s[2000001];
int main() {
    int ti;
    cin >> ti;
    while (ti--) {
        cin >> s;
        n = strlen(s);
        if (n == 1) {
            ans = 1;
            a = 2;
        } else {
            ans = 2;
            a = 2;
            if (n == 2)
                a += 4;
            int pd = 1;
            for (int i = 1; i < n; i++)
                if (s[i] != s[i - 1]) {
                    pd = 0;
                    break;
                }
            if (pd)
                a += 2;
        }
        printf("%d %d\n", ans, a);
    }
}

H

发现定义和双极定向一样的。（不知道的可以看牛客第三场的 ）

定向了后，通过拓扑序求出每个点的目标点值，然后随便求个以 为根的 生成树化成树上问题。

首先考虑链的方案是什么。应该是每次选择 所在点进行操作，从而做到排序。

那么对于一颗普通的树，取出所有叶子向上直到分叉点的链，解决这一部分后删掉递归处理。因为每次叶子数量至少 ，所以做到 次。具体实现可以参考代码。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fast_IO ios::sync_with_stdio(false);
#define DEBUG fprintf(stderr, "Running on Line %d in Function %s\n", __LINE__, __FUNCTION__)
#define fir first
#define sec second
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read() {
    char ch = getchar();
    int nega = 1;
    while (!isdigit(ch)) {
        if (ch == '-')
            nega = -1;
        ch = getchar();
    }
    int ans = 0;
    while (isdigit(ch)) {
        ans = ans * 10 + ch - 48;
        ch = getchar();
    }
    if (nega == -1)
        return -ans;
    return ans;
}
typedef pair<int, int> pii;
void print(vector<int> x) {
    for (int i = 0; i < (int)x.size(); i++) printf("%d%c", x[i], " \n"[i == (int)x.size() - 1]);
}
#define N 2005
int fa[N], id[N], val[N], a[N];
int n, m, S, T;
int u[N], v[N], ok[N];
vector<int> G[N], H[N];
int dgr[N], rk[N], rev[N];
int toposort() {
    for (int i = 1; i <= n; i++)
        if (ok[i]) {
            for (int j : G[i]) dgr[j]++;
        }
    queue<int> q;
    q.push(S);
    int cnt = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        rk[u] = cnt++;
        for (int v : G[u]) {
            if (!--dgr[v])
                q.push(v);
        }
    }
    return cnt == n;
}
vector<int> ans, cur;
int vis[N];
void dfs(int u) {
    if (!ans.empty())
        return;
    cur.pb(u);
    vis[u] = 1;
    for (int v : H[u]) {
        if (vis[v])
            continue;
        if (ok[v]) {
            ans = cur;
            ans.pb(v);
            return;
        } else
            dfs(v);
        if (!ans.empty())
            return;
    }
    cur.pop_back();
}
namespace APC001H {
int p[N];
vector<int> ans, e[N];
void jump(int x) {
    if (x)
        jump(fa[x]), a[fa[x]] = a[x], p[a[x]] = fa[x];
}
void shift(int x) {
    int t = a[0];
    jump(x);
    ans.push_back(p[a[x] = t] = x);
}
int solve(int x, int v) {
    int res = n;
    for (int y : e[x]) {
        int t = solve(y, v);
        if (a[t] > a[res])
            res = t;
    }
    return res < n ? res : a[x] > v ? x : -1;
}
void Main() {
    e[fa[0] = n].push_back(0);
    for (int i = 1; i < n; i++) e[fa[i]].push_back(i);
    for (int i = 0; i < n; i++) p[a[i]] = i;
    for (int i = n; i--; shift(i), e[fa[i]].pop_back())
        while (a[0] != i) shift(solve(p[i], a[0]));
    assert(ans.size() <= 10000);
    cout << ans.size() << "\n";
    for (int id : ans) {
        vector<int> rv;
        int cur = id;
        while (cur) {
            rv.pb(cur);
            cur = fa[cur];
        }
        rv.pb(0);
        reverse(rv.begin(), rv.end());
        printf("%d ", (int)rv.size());
        for (int j : rv) printf("%d ", rev[j]);
        cout << "\n";
    }
}
}; 
int edg[1005][1005];
signed main() {
    cin >> n >> m >> S >> T;
    for (int i = 1; i <= n; i++) val[i] = read();
    for (int i = 1; i <= m; i++) {
        u[i] = read(), v[i] = read();
        edg[u[i]][v[i]] = edg[v[i]][u[i]] = 1;
        H[u[i]].pb(v[i]), H[v[i]].pb(u[i]);
    }
    G[S].pb(T);
    ok[S] = ok[T] = 1;
    while (!toposort()) {
        int fl = 0;
        for (int i = 1; i <= n && !fl; i++)
            if (ok[i]) {
                for (int j : H[i])
                    if (!ok[j]) {
                        ans.clear();
                        memset(vis, 0, sizeof(vis));
                        vis[i] = 1;
                        cur = { i };
                        // printf("* %d %d\n",i,j);
                        dfs(j);
                        if (ans.empty())
                            continue;
                        if (rk[ans[0]] > rk[ans.back()])
                            reverse(ans.begin(), ans.end());
                        // print(ans);
                        for (int k = 0; k + 1 < (int)ans.size(); k++)
                            G[ans[k]].pb(ans[k + 1]), ok[ans[k]] = 1;
                        fl = 1;
                        break;
                    }
            }
        if (!fl)
            cout << "-1\n", exit(0);
    }
    for (int i = 1; i <= n; i++) rev[rk[i]] = i;
    for (int i = 1; i <= n; i++)
        for (int v : G[i])
            if (edg[i][v])
                fa[rk[v]] = rk[i];
    for (int i = 1; i <= n; i++) a[rk[i]] = val[i] - 1;
    APC001H::Main();
    return 0;
}

J

如果数组 区间 和能被 整除，那前缀和数组 一定满足 。

那么考虑 表示 的个数。方案数即为 。

表示放了 ，总共放了 个，优异度为 的方案数。直接 计算。
$$

#include <cstdio>
using namespace std;
const int M = 998244353;
int n, K, t;
long f[65][2100];
long C[70][70];
int main() {
    scanf("%d%d%d", &n, &K, &t);
    C[0][0] = 1;
    for (int i = 1; i <= 65; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % M;
    }
    f[0][0] = 1;
    for (int u, i = 0; i < K; i++)
        for (int k = n; k; k--)
            for (int l = t; l >= 0; l--) {
                for (int u, j = 1; j <= k; j++) {
                    u = j * (i == 0 ? (j + 1) : (j - 1)) / 2;
                    if (u > l)
                        break;
                    f[k][l] += f[k - j][l - u] * C[k][j] % M;
                }
                f[k][l] %= M;
            }
    printf("%ld\n", f[n][t]);
}

K

若堆数为 ，先手必胜。

若堆数为 ，谁取完了一堆谁就输了。所以每一堆有一个石子不能取。我们令 ，就变成了 问题，谁最后操作不了就赢了。也就是 则先手必败，否则先手必胜。

若堆数为 ，先手操作最大的那一堆石头，从而变成堆数为 且异或和为 的局面使其胜利。

若堆数为 ，谁让堆数 谁就输了，所以还是看 是否为 。

所以堆数为奇数先手必胜。否则令 ，看多少区间异或和为 。

那么只需要前缀异或一下，离线下来莫队求解。时间复杂度 。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 1, B = 300, T = 2e6 + 1;
int n, q, s[N], bl[N], L, R, a[2][T];
ll sum, ans[N];
struct que {
    int l, r, id;
} t[N];
int operator<(const que& a, const que& b) {
    return bl[a.l] ^ bl[b.l] ? a.l < b.l : (bl[a.l] & 1 ? a.r < b.r : a.r > b.r);
}
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 0; i <= n; i++) bl[i] = i / B + 1;
    for (int i = 1; i <= n; i++) scanf("%d", s + i), s[i] = (s[i] - 1) ^ s[i - 1];
    for (int i = 1; i <= q; i++) {
        scanf("%d%d", &t[i].l, &t[i].r);
        t[i].l--;
        t[i].id = i;
    }
    sort(t + 1, t + 1 + q);
    a[0][0] = 1;
    for (int i = 1; i <= q; i++) {
        while (R < t[i].r) ++R, sum += a[R & 1][s[R]]++;
        while (L > t[i].l) --L, sum += a[L & 1][s[L]]++;
        while (R > t[i].r) sum -= --a[R & 1][s[R]], --R;
        while (L < t[i].l) sum -= --a[L & 1][s[L]], ++L;
        ans[t[i].id] = 1ll * (R - L + 1) * (R - L) / 2 - sum;
    }
    for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
    return 0;
}

L

在一个边双里，最小值和最大值可以出现在同一个环里。因为我们在最小边和最大边中间加上一个点，这图还是一个边双。

做法可以建图，以这新建的两个点跑网络流，然后把有流量的边拿出来跑欧拉回路即可。

因为网络流除了源汇点，每个点的输入流量等于输出流量。而由于是边双，所以最大流至少为 ，也就是源汇点的度数也会是 ，那么满足欧拉回路条件。

#include <bits/stdc++.h>
#define ri int
#define ll long long
#define fi first
#define se second
using namespace std;
const int Maxn = 1e6;
vector<int> s[Maxn + 5];
vector<pair<int, int>> adj[Maxn + 5];
int vis[Maxn + 5], mark[Maxn + 5];
int e[Maxn + 5];
int dfn[Maxn + 5], low[Maxn + 5], bridge[Maxn + 5], id, vt;
int lt[Maxn + 5], nt[Maxn + 5], ed[Maxn + 5], val[Maxn + 5], have[Maxn + 5], cnt = 1;
int n, m;
inline bool cmp(int x, int y) { return e[x] < e[y]; }
inline void addedge(int x, int y, int z) {
    ed[++cnt] = y;
    nt[cnt] = lt[x];
    lt[x] = cnt;
    val[cnt] = z;
}
inline void add(int x, int y, int z) {
    addedge(x, y, z);
    addedge(y, x, 0);
}
void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++vt;
    for (auto e : adj[u]) {
        int v = e.fi;
        if (v == fa)
            continue;
        if (!dfn[v]) {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) {
                bridge[e.se] = 1;
            }
        } else
            low[u] = min(low[u], dfn[v]);
    }
}
void dfs(int u) {
    vis[u] = 1;
    for (auto e : adj[u])
        if (!bridge[e.se]) {
            s[id].push_back(e.se);
            if (!vis[e.fi])
                dfs(e.fi);
        }
}
int maxflow(int S, int T, int tot) {
    int ans = 0;
    while (1) {
        vector<int> pre(tot + 1), to(tot + 1);
        queue<int> q;
        pre[S] = S, q.push(S);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (ri i = lt[u]; i; i = nt[i]) {
                int v = ed[i];
                if (!pre[v] && val[i]) {
                    pre[v] = u, to[v] = i;
                    q.push(v);
                }
            }
        }
        if (!pre[T])
            return ans;
        int u = T, flow = 1e9;
        while (u != S) {
            int e = to[u];
            u = pre[u];
            // printf("Left: %d ",u);
            flow = min(flow, val[e]);
        }
        u = T;
        while (u != S) {
            int e = to[u];
            u = pre[u];
            // printf("Left: %d ",u);
            val[e] -= flow, val[e ^ 1] += flow;
            have[e] += flow, have[e ^ 1] -= flow;
            // printf("%d %d\n",u,val[e]);
        }
        ans += flow;
    }
}
void buildcircle(int u, vector<int>& ans) {
    ans.push_back(u);
    for (ri i = lt[u]; i; i = nt[i]) {
        int v = ed[i];
        if (have[i] > 0) {
            --have[i];
            buildcircle(v, ans);
            break;
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    vector<pair<int, int>> edge(m + 1);
    for (ri i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d%d", &x, &y, &e[i]);
        adj[x].push_back(make_pair(y, i));
        adj[y].push_back(make_pair(x, i));
        edge[i] = make_pair(x, y);
    }
    tarjan(1, 0);
    for (ri i = 1; i <= n; i++)
        if (!vis[i])
            ++id, dfs(i);
    int mxd = -1, ch = 0;
    for (ri i = 1; i <= id; i++) {
        sort(s[i].begin(), s[i].end());
        s[i].erase(unique(s[i].begin(), s[i].end()), s[i].end());
        sort(s[i].begin(), s[i].end(), cmp);
        if ((int)s[i].size() >= 2) {
            int d = e[s[i].back()] - e[*s[i].begin()];
            if (d > mxd) {
                mxd = d, ch = i;
            }
        }
    }
    int S = n + 1, T = n + 2, mn = *s[ch].begin(), mx = s[ch].back();
    add(S, edge[mn].fi, 1);
    add(S, edge[mn].se, 1);
    add(edge[mx].fi, T, 1);
    add(edge[mx].se, T, 1);
    for (ri x : s[ch])
        if (x != mn && x != mx) {
            addedge(edge[x].fi, edge[x].se, 1);
            addedge(edge[x].se, edge[x].fi, 1);
        }
    maxflow(S, T, n + 2);
    printf("%d\n", mxd);
    vector<int> ans1, ans2;
    buildcircle(S, ans1);
    buildcircle(S, ans2);
    printf("%d\n", (int)ans1.size() + (int)ans2.size() - 4);
    for (ri u : ans1)
        if (u != S && u != T)
            printf("%d ", u);
    reverse(ans2.begin(), ans2.end());
    for (ri u : ans2)
        if (u != S && u != T)
            printf("%d ", u);
    puts("");
    return 0;
}