由于牛客的渲染问题，你可以点此链接进入我的博客查看

个人难度评级

签到：

简单：

中等：

困难：

A 比赛安排

等价于我们把三种比赛分成一组，如 ，最后的结果一定是 ，所以我们检查是否满足

即可

void solve() {
    ll a, b, c;
    cin >> a >> b >> c;
    int x = min({a, b, c});
    if (a - x <= 1 && b - x <= 1 && c - x <= 1)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

B NCPC

显然最大的可以把所有小的全踢死；如果最大的有偶数个，那么自己也会死。

由以上结论我们可以得到：

• 如果最大有偶数个，它自己一定赢不了（因为清除不掉所有同级选手），但是可以帮助任何一个选手踢死其他所有对手，然后自杀，所以除了最大的每个都可能赢
• 如果最大有奇数个，最大踢死其他对手后不能找一个同级的撞死，所以只有最大能赢。

void solve() {
    int n, mx = -1;
    cin >> n;
    vector<int> a(n);
    unordered_map<int, int> cnt;
    for (int i = 0; i < n; i++)
        cin >> a[i], mx = max(mx, a[i]), cnt[a[i]]++;

    bool f = cnt[mx] & 1;

    for (int i = 0; i < n; ++i) {
        if (f) {
            if (a[i] == mx)
                cout << 1;
            else
                cout << 0;
        } else {
            if (a[i] < mx)
                cout << 1;
            else
                cout << 0;
        }
    }
    cout << endl;
}

C 炮火轰炸

把炮火点看作图的节点，如果两个炮火点在8邻域（周围一圈8个格子）内，则连边。首先找出所有炮火点的连通块。每一个封闭的炮火圈对应一个连通块的外轮廓。对于每个连通块，我们需要找到它的外边界。只需要找到连通块中最左下角的点作为起点，然后沿着逆时针方向（始终保持炮火点在左手边）遍历边界，直到回到起点。在这个过程中，我们记录下边界上的有向边。

对于每个询问点 ，我们想象向右发射一条射线（ ）。计算这条射线与炮火圈边界的垂直边的交点数。如果边界边向上穿过射线，计数 ；向下穿过，计数 ​ 。若最终计数的总和不为0，说明点在圈内，否则在圈外。

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

struct Point {
    int x, y;
    bool operator<(const Point &other) const {
        if (x != other.x)
            return x < other.x;
        return y < other.y;
    }
    bool operator==(const Point &other) const {
        return x == other.x && y == other.y;
    }
};

void solve() {
    int n, q;
    cin >> n >> q;
    map<Point, int> mp;
    vector<Point> pts(n);
    for (int i = 0; i < n; ++i) {
        cin >> pts[i].x >> pts[i].y;
        mp[pts[i]] = i;
    }

    vector<bool> vis(n);
    map<int, vector<PII>> Eve;

    for (int i = 0; i < n; ++i) {
        if (vis[i])
            continue;

        vector<int> comp, q = {i};
        vis[i] = 1;
        int head = 0;
        while (head < q.size()) {
            int u = q[head++];
            comp.pb(u);
            for (int k = 0; k < 8; k++) {
                Point nb = {pts[u].x + dx[k], pts[u].y + dy[k]};
                if (mp.count(nb)) {
                    int v = mp[nb];
                    if (!vis[v]) {
                        vis[v] = true;
                        q.pb(v);
                    }
                }
            }
        }

        if (comp.size() < 2)
            continue;

        int st = comp[0];
        for (int id : comp)
            if (pts[id] < pts[st])
                st = id;

        int curr = st, cd = 4, steps = 0, ms = 4 * comp.size() + 100;

        do {
            int nn = -1, nd = -1;
            for (int k = 0; k < 8; ++k) {
                int dir = (cd + k) % 8;
                Point nb = {pts[curr].x + dx[dir], pts[curr].y + dy[dir]};
                if (mp.count(nb)) {
                    nn = mp[nb];
                    nd = dir;
                    break;
                }
            }

            if (nn != -1) {
                if (pts[nn].y > pts[curr].y)
                    Eve[pts[curr].y].pb({pts[curr].x, 1});
                else if (pts[nn].y < pts[curr].y)
                    Eve[pts[nn].y].pb({pts[nn].x, -1});

                curr = nn;
                cd = (nd + 6) % 8;
            } else
                break;
            steps++;
        } while (curr != st && steps < ms);
    }

    map<int, vector<PII>> queries;
    for (int i = 0; i < q; ++i) {
        int a, b;
        cin >> a >> b;
        queries[b].pb({a, i});
    }

    vector<string> ans(q, "NO");
    for (auto &[y, qs] : queries) {
        if (!Eve.count(y))
            continue;

        auto &evs = Eve[y];
        sort(all(evs));
        sort(all(qs));

        int winding = 0;
        int ptr = 0;
        for (auto &_pt : qs) {
            while (ptr < evs.size() && evs[ptr].fi < _pt.fi) {
                winding += evs[ptr].se;
                ptr++;
            }
            if (winding != 0)
                ans[_pt.se] = "YES";
        }
    }

    for (auto v : ans)
        cout << v << endl;
}

D 数字积木

我已急哭

直接枚举所有连通子图并计算 显然不可行。我们利用 的性质转化求和顺序。

根据 的定义：

当且仅当集合 包含在子图 的点权集合中。

利用恒等式 ，我们可以将总答案转化为：

设 为权值 的节点集合。

要在树上连通地包含 ，这个子图必须包含 在树上的极小连通生成子图 。如果我们以权值为 的节点为根：

• 一定包含根节点（因为 0 在其中）。
• 是从根节点出发，延伸到所有权值在 的节点的路径的并集。

对于一个固定的 ，任何包含它的合法连通子图都是由两部分组成：

1. 必须包含完整的
2. 对于 上的每一个节点 ，可以挂载它那些不在 中的子树

设 为在原树中，以 为根的子树内，包含 的连通子图的个数。

状态转移方程为：

那么， 的计算公式为：

直观理解就是： 上所有节点原本的方案数乘起来，但要剔除掉那些已经变成了它的一部分的子节点分支的贡献（因为它们变成了必选，不再是可选可不选）。

如果我们对每个 都重新遍历树计算 ，复杂度是 ，会超时。我们注意到 是在 的基础上增加节点 形成的。

设权值为 的节点为 。

• 如果 已经在 中（即它在 某点的路径上），则 。

• 如果不在，我们需要把从 到 的路径合并进核心。找到 往上跳直到碰到 的路径。路径上的点是新加入核心的点。

• 设路径与原核心的交点为 ，路径上 的那个子节点为 。

• 原来 是挂在 下的一个可选分支，贡献是 。现在它变成了核心的一部分，所以要从总乘积中除以 。

• 对于路径上新加入的每个节点 ，我们要把它的贡献乘进总答案。它的贡献是它所有不在路径上的子树的选择方案。

  即乘以 。对于 节点本身，直接乘以 ​ 。

对于卡逆元的解决办法：

维护一个结构体，记录数值 和因子中 的个数 。

• 乘 时：
• 除 时：
• 取值时：若 则为 ，否则为 。

struct SafeZ {
    Z val = 1;
    int cnt = 0;

    SafeZ(Z v) {
        mul(v);
    }
    void mul(Z x) {
        if (x.val() == 0)
            cnt++;
        else
            val *= x;
    }
    void div(Z x) {
        if (x.val() == 0)
            cnt--;
        else
            val /= x;
    }
    Z get() {
        return cnt > 0 ? Z(0) : val;
    }
};

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1), pos(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i], pos[a[i]] = i;

    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v), g[v].pb(u);
    }

    vector<bool> vis(n + 1);
    vector<int> pa(n + 1);
    int s = pos[0];
    vector<int> q;
    int h = 0;
    q.pb(s);
    vis[s] = 1;
    pa[s] = 0;
    while (h < q.size()) {
        int u = q[h++];
        for (auto v : g[u]) {
            if (vis[v])
                continue;
            vis[v] = 1;
            pa[v] = u;
            q.pb(v);
        }
    }

    vector<Z> way(n + 1);
    for (int i = n - 1; i >= 0; --i) {
        int u = q[i];
        way[u] = 1;
        for (int v : g[u]) {
            if (v != pa[u]) {
                way[u] *= way[v] + 1;
            }
        }
    }

    vis.assign(n + 1, 0);
    vis[s] = 1;
    SafeZ cur = way[s];
    Z ans = cur.get();
    for (int k = 1; k < n; ++k) {
        int tar = pos[k];

        if (vis[tar]) {
            ans += cur.get();
            continue;
        }

        vector<int> path;
        int curr = tar;
        while (!vis[curr]) {
            path.pb(curr);
            curr = pa[curr];
        }
        reverse(all(path));

        cur.div(way[path[0]] + 1);
        for (int i = 0; i < path.size(); ++i) {
            int u = path[i];
            vis[u] = 1;
            cur.mul(way[u]);

            if (i < path.size() - 1) {
                cur.div(way[path[i + 1]] + 1);
            }
        }
        ans += cur.get();
    }

    cout << ans << endl;
}

E 01矩阵

打表发现，先构造一个严格下三角矩阵，在按 重排行和列后，连通块数量正好为 ​ 。

简单的证明：

• 原下三角矩阵每行（列）1 的个数是 ，行和列按同一置换重排，多重集合不变
• 由于 高低交错：
  • 固定一行 ，条件 随 变化至多翻转一次
  • 所以每行、每列的 ​ 都是一个连续区间
• 按值 分层：
  • 当 时，会出现一个新的、与之前全部不连通的区域
  • 每个 恰好产生一个新的 连通块，因此连通块总数

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

    if (n == 1) {
        cout << "0" << endl;
        return;
    }

    vector<string> g(n, string(n, '0'));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            g[i][j] = '1';
        }
    }
    int l = 0, r = n - 1;
    vector<int> p;
    while (l <= r) {
        p.pb(l++);
        if (l <= r)
            p.pb(r--);
    }

    vector<string> ans(n, string(n, '0'));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            ans[i][j] = g[p[i]][p[j]];
        }
    }
    for (int i = 0; i < n; ++i)
        cout << ans[i] << endl;
}

F x?y?n!

如果 ，不难想到令 即可满足条件，那么就有

我们要让 ，所以我们想到如果取 （显然互质），即 ，有

我们只需要去找满足 的 ​ 即可。

void solve() {
    int n;
    cin >> n;
    ll x = 0, y = 0, t = n;
    for (int i = 1; i <= 31; ++i) {
        t <<= 1;
        if ((t & n) == 0) {
            x = t, y = t + n;
            break;
        }
    }
    cout << x << " " << y << endl;
}

H 权值计算

我们不妨考虑数组中每个元素对最终答案贡献了多少。

函数 计算的是子数组 的所有前缀中不同元素个数之和。换个角度，最终的总权值等于：对于所有的 ，如果 中 是第一次出现，则产生 ​ 的贡献。

对于第 个位置的元素 ，它被统计的条件是：它必须在统计范围 内（即 ）。它必须是该范围内 的第一次出现。这意味着起始点 必须在 上一次出现的位置 ​ 之后。因此，对于固定的 ，合法的 组合满足：

• 的范围： ，共有 种选择。
• 的范围： 。
• 的范围： 。

对于每一个固定的 （ ），合法的 有 个。所以对于固定的 ，右边部分 的组合总数为：

所以最后答案为

void solve() {
    int n;
    cin >> n;
    map<int, int> pos;
    ll tot = 0;

    auto S = [&](ll x) {
        return x * (x + 1) / 2;
    };

    for (int i = 1, x; i <= n; ++i) {
        cin >> x;
        tot += (i - pos[x]) * S(n - i + 1);
        pos[x] = i;
    }

    cout << tot << endl;
}

I 01回文

回文串有两种基本形式：

• 长度为 的：直接检查相邻元素。

• 长度大于 的：

  如果 的所有邻居的值都与它不同（例如它是 ，周围全是 ），那么任何路径必然是 。要形成回文串，路径必须以 结尾。最短的形式是 。这意味着我们需要从 出发，进入一片 的区域，并能从这片区域走到另一个 的位置。

  推广来说，如果 相邻的那些 所在的连通分量连接了至少两个 （其中一个是 自己，另一个是目标终点），那么就存在 这样的路径。

  所以如果 相邻的异色连通分量接触到了除 以外的其他同色节点，输出 。这等价于：一个连通分量如果接触了超过 个异色节点，那么这些异色节点都能通过该连通分量形成回文路径。

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

void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (int i = 0; i < n; ++i)
        cin >> g[i];
    vector<string> ans(n, string(m, 'N'));

    auto check = [&](int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < m;
    };

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            for (int k = 0; k < 4; ++k) {
                int nx = i + dx[k], ny = j + dy[k];
                if (check(nx, ny)) {
                    if (g[nx][ny] == g[i][j]) {
                        ans[i][j] = 'Y';
                        break;
                    }
                }
            }
        }
    }

    auto ssolve = [&](char tar) {
        vector<vector<bool>> vis(n, vector<bool>(m));
        vector<int> vis2(n * m, -1);
        int id = 0;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (g[i][j] == tar && !vis[i][j]) {
                    id++;
                    vector<PII> nei;
                    queue<PII> q;

                    q.push({i, j});
                    vis[i][j] = 1;

                    while (!q.empty()) {
                        auto [x, y] = q.front();
                        q.pop();

                        for (int k = 0; k < 4; ++k) {
                            int nx = x + dx[k], ny = y + dy[k];

                            if (check(nx, ny)) {
                                if (g[nx][ny] == tar) {
                                    if (!vis[nx][ny]) {
                                        vis[nx][ny] = 1;
                                        q.emplace(nx, ny);
                                    }
                                } else {
                                    int idx = nx * m + ny;
                                    if (vis2[idx] != id) {
                                        vis2[idx] = id;
                                        nei.eb(nx, ny);
                                    }
                                }
                            }
                        }
                    }

                    if (nei.size() > 1) {
                        for (auto [x, y] : nei) {
                            ans[x][y] = 'Y';
                        }
                    }
                }
            }
        }
    };

    ssolve('0');
    ssolve('1');

    for (int i = 0; i < n; ++i) {
        cout << ans[i] << endl;
    }
}

J 终于再见

首先根据每个城市的繁华度（度数）将城市进行分级。度数相同的城市属于同一级。将所有出现的度数从小到大排序，对应不同的级别 。对于级别为 的城市，我们需要找到通往级别 的城市的最短路径。这意味着我们可以从最高级别的城市开始，逐步向下处理。多源 求解一下即可。

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v), g[v].pb(u);
    }

    vector<vector<int>> gp(n);
    for (int i = 1; i <= n; ++i) {
        gp[g[i].size()].pb(i);
    }

    vector<vector<int>> L;
    for (int d = 0; d < n; ++d) {
        if (!gp[d].empty()) {
            L.pb(gp[d]);
        }
    }

    vector<int> dist(n + 1, inf), ans(n + 1, -1);
    queue<int> q;

    int K = L.size();

    if (K > 0) {
        for (int u : L[K - 1]) {
            dist[u] = 0;
            q.push(u);
        }
    }

    auto bfs = [&]() {
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : g[u]) {
                if (dist[v] > dist[u] + 1) {
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
        }
    };

    bfs();

    for (int i = K - 2; i >= 0; --i) {
        for (int u : L[i]) {
            if (dist[u] != inf) {
                ans[u] = dist[u];
            } else {
                ans[u] = -1;
            }
        }

        for (int u : L[i]) {
            if (dist[u] != 0) {
                dist[u] = 0;
                q.push(u);
            }
        }
        bfs();
    }

    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << " ";
    }
    cout << endl;
}

头文件

#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define eb emplace_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define endl "\n"
using namespace std;

using ll = long long;
using ld = long double;
using ui = unsigned;
using ull = unsigned long long;
using i128 = __int128;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
using TIII = tuple<int, int, int>;
using TLLL = tuple<ll, ll, ll>;

void init() {
}

void solve() {
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    init();

    int t = 1;
    cin >> t;
    cout << fixed << setprecision(15);
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }

    return 0;
}

自动取模

constexpr int MOD = 998244353;

template <class T>
constexpr T ksm(T a, ll b) {
    T res = 1;
    while (b) {
        if (b & 1)
            res *= a;
        b >>= 1;
        a *= a;
    }
    return res;
}

template <int P>
struct MInt {
    int x;
    constexpr MInt() : x() {}
    constexpr MInt(ll x) : x{norm(x % getMod())} {}
    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return ksm(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr istream &operator>>(istream &is, MInt &a) {
        ll v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr ostream &operator<<(ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};

template <>
int MInt<0>::Mod = 998244353;

template <int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

using Z = MInt<MOD>;