牛客周赛 Round 133 题解

A 小红的闭合标签

直接在位置 $1$ 处插入一个 $/$ 即可。

void solve() {
    int n;
    string s;
    cin >> n >> s;
    s.insert(1, 1, '/');
    cout << s << endl;
}

B 小红的众数

统计每个数字出现的次数，最多的出现次数 $-$ $x$ 的出现次数即为答案。

void solve() {
    int n, x;
    cin >> n >> x;
    unordered_map<int, int> mp;
    for (int i = 0, x; i < n; ++i)
        cin >> x, mp[x]++;
    int mx = 0;
    for (auto [_, v] : mp)
        mx = max(mx, v);
    cout << mx - mp[x] << endl;
}

C 小红的数字查找

$x\times y$ 为完全平方数，如果令 $s$ 为 $x$ 中出现奇数次的素因子之积，那么有 $y=s\cdot t^2$ ，其中 $t$ 为整数。我们只需要求出 $s$ ，并判断是否存在整数 $t$ 满足 $l\leq s\cdot t^2\leq r$ 即可。

需要注意本题有数据卡了实现较差的质因数分解，例如：

while (x != 1) {
    if (x % ptr == 0) {
        int cnt = 0;
        while (x % ptr == 0) {
            x /= ptr;
            cnt ^= 1;
        }
        if (cnt)
            t *= ptr;
    }
    ptr++;
}

此类方法在遇到 $x$ 中有较大质因子时性能较差，会退化到 $O(x)$ ，需要注意。

void solve() {
    int x, l, r;
    cin >> x >> l >> r;
    int t = 1;
    for (int p = 2; p * p <= x; ++p) {
        if (x % p == 0) {
            int cnt = 0;
            while (x % p == 0) {
                x /= p;
                cnt ^= 1;
            }
            if (cnt)
                t *= p;
        }
    }
    t *= x;
    if ((l + t - 1) / t > r / t) {
        cout << -1 << endl;
        return;
    }
    ll lo = sqrt((l + t - 1) / t), hi = sqrt(r / t);
    if (lo * lo < (l + t - 1) / t)
        lo++;
    if (lo <= hi) {
        cout << t * lo * lo << endl;
    } else {
        cout << -1 << endl;
    }
}

D 小红的异或分组

设前缀异或和 $pre[k] = a_1\oplus a_2\oplus ...\oplus a_k$

由于三段异或和相等，设每段异或和为 $x$ ，那么就有

$T = sum[a] \oplus sum[b] \oplus sum[c] = x\oplus x\oplus x = x$
第一段 $sum[a] = pre[a] = x$
第三段 $sum[c] = pre[n]\oplus pre[b] = x\oplus pre[b] = x\rightarrow pre[b] = 0$

所以我们只要找到 $pre[a] = T$ 且 $pre[b] = 0$ 的 $(a,b)$ 对的数量即可。

$n^2$ 为 $4\times 10^{10}$ 量级，注意使用 $64$ 位存储。

void solve() {
    int n, s = 0;
    cin >> n;
    vector<int> a(n), pre(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i], s ^= a[i], pre[i] = s;
    ll ans = 0;
    int cur = 0, cnt = 0;
    for (int i = 0; i < n - 1; ++i) {
        cur ^= a[i];
        if (cur == 0)
            ans += cnt;
        if (cur == s)
            ++cnt;
    }
    cout << ans << endl;
}

E 小红的路径

先来分析无解的情况（手玩一下即可）：

当 $y_1=y_2$ 并且 $y_1\neq 1$ 或 $y_1\neq n$
棋盘染色后起点与终点颜色相同：因为要遍历 $2n$ 个格子就要经过 $2n-1$ 次缝隙，每经过一次缝隙就要变换一次颜色，所以头和尾的颜色必然不相同。

为了方便构造，我们把起点放到终点的左边。

对于 $y\leq y_1$ 的部分，我们直接向左走到底，然后绕回来。
对于 $y_1<y<y_2$ 的部分，我们按蛇形一上一下去填满中间部分。
对于 $y\geq y_2$ 的部分，我们向右走到底再走回来。

void solve() {
    int n, x1, y1, x2, y2;
    cin >> n >> x1 >> y1 >> x2 >> y2;
    if ((x1 + y1 + x2 + y2 + 1) & 1) {
        cout << -1 << endl;
        return;
    }
    bool f = false;
    if (y1 > y2) {
        swap(x1, x2);
        swap(y1, y2);
        f = true;
    }

    string s = "";

    if (y1 == y2) {
        if (y1 > 1 && y1 < n) {
            cout << -1 << endl;
            return;
        } else if (y1 == 1) {
            s += string(n - 1, 'R');
            s += (x1 == 1 ? 'D' : 'U');
            s += string(n - 1, 'L');
        } else {
            s += string(n - 1, 'L');
            s += (x1 == 1 ? 'D' : 'U');
            s += string(n - 1, 'R');
        }
    } else {
        int cx = x1;
        if (y1 > 1) {
            s += string(y1 - 1, 'L');
            s += (cx == 1 ? 'D' : 'U');
            cx = 3 - cx;
            s += string(y1 - 1, 'R');
        } else {
            s += (cx == 1 ? 'D' : 'U');
            cx = 3 - cx;
        }

        for (int c = y1; c < y2 - 1; ++c) {
            s += 'R';
            s += (cx == 1 ? 'D' : 'U');
            cx = 3 - cx;
        }
        s += 'R';

        if (y2 < n) {
            s += string(n - y2, 'R');
            s += (cx == 1 ? 'D' : 'U');
            s += string(n - y2, 'L');
        } else {
            s += (cx == 1 ? 'D' : 'U');
        }
    }

    if (f) {
        reverse(all(s));
        for (auto &c : s) {
            if (c == 'L')
                c = 'R';
            else if (c == 'R')
                c = 'L';
            else if (c == 'U')
                c = 'D';
            else if (c == 'D')
                c = 'U';
        }
    }
    cout << s << endl;
}

F 小红删树

本题题解中的菊花图链长均为 $1$

我们不妨展开这三步过程：

第一轮，整棵树是一个连通块，我们删除了一个节点后，它变成若干个连通块。
第二轮：对于每一个连通块，我们再删了其中的一个节点，变成更小的连通块。
第三轮：每个连通块的大小都为 $1$ ，对每个连通块都操作后消除了所有节点。

也就是说，删除了第一轮的节点 $r$ 后，我们要保证对于每一个 $r$ 的邻居 $u$ ，它所在的连通块 $C_u$ 在第二次删除后，剩下的连通块大小均为 $1$ 。满足这一点的情况只有两种：

$C_i$ 的大小为 $1$ ，第二轮就删掉了
$C_i$ 为菊花图（我们认为只有两个点的连通块也是菊花图），删除了中心节点后，剩余的所有连通块大小均为 $1$ 。

当然还要排除第二轮就全部删完的情况，也就是在第一轮之后，剩余的所有连通块的大小就已经只剩 $1$ 了。

所以我们可以把答案表示为 $P = \frac{1}{n}\sum\limits_r P_r-\frac{1}{n}\sum\limits_r I_r$ ，其中 $P_r$ 为第一轮删除 $r$ ，第二轮删除后剩下的每个连通块大小都为 $1$ 的概率， $I_r$ 为第一轮删除 $r$ 后，是否所有的连通块大小均为 $1$ 。

我们枚举每一个节点 $r$ ，再枚举它的所有邻居 $u$ 和对应的连通块 $C$ ：

如果 $deg[u] = 1$ ，显然在删除 $r$ 后，这个邻居会变成一个单点，成功概率为 $100\%$ 。
如果 $deg[u]\geq3$ ，唯一可能使得 $C$ 成为菊花图并且能在第 $2$ 轮通过选中其中心把剩余变成单点的情形是 $u$ 本身是 $C$ 的中心。这要求 $u$ 在 $C$ 中的所有除 $v$ 以外的邻居都是叶（即在整棵树里，这些邻居的度都是 1）。用 $cnt[u]$ 表示 $u$ 与非叶相连的个数，则在整棵树里 $cnt[u]$ 包括 $v$ （如果 $deg[v]>1$ ）和 $u$ 在 $C$ 内与非叶的连接。对于 $u$ 成为中心的充要条件可以推导为：
- $cnt[u] = cc$ ，其中当 $deg[v] > 1$ 时 $cc = 1$ （因为 $v$ 可能是非叶，会被 $cnt[u]$ 计数一次），否则 $cc = 0$ （若 $v$ 是叶，则 $cnt[u]$ 不应计 $v$ ）。
  
  在满足条件时，分支大小为 $sz = deg[u]$ （剔除 $v$ 之后的叶数 $+ u$ 自身共 $deg[u]$ 个结点），被选中中心的概率是 $\frac{1}{sz}$ 。
如果 $deg[u] = 2$ ：若 $C$ 是菊花图，唯一可能的中心是邻居 $ww$ 。那么 $sz = deg[ww] + 1$ （ $ww$ 的所有叶加上 $u$ 本身），对于 $ww$ 成为中心需要 $cnt[ww] == 1$ （ $ww$ 的唯一非叶邻居应当是 $u$ ；需要注意 $v$ 是否为非叶会影响计数，需做特殊小型情况处理）。对于小的特例（ $sz <= 2$ ）显然概率是 $1$ （因为 $sz=2$ 里任选一个都会使其余变成单点），所以对 $sz\leq 2$ 单独处理。

因此对定点 $v$ ，第 $2$ 轮成功使得每个分支变成单点（或空）的概率就是对其所有邻居 $u$ 的独立事件概率的乘积，记为 $prob_v$ 。对于 $v$ 若 $prob_v > 0$ 且并且对于每个邻居分支 $sz\leq 1$ （即所有分支本来就是单点），那 $v$ 会在第 $2$ 轮就把整棵树删光，也就是 $I_v=1$ 的情况。

void solve() {
    int n;
    cin >> n;
    if (n == 1) {
        cout << 0 << endl;
        return;
    }

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

    vector<int> cnt(n + 1, 0);
    for (int u = 1; u <= n; ++u) {
        if (deg[u] > 1) {
            for (auto v : g[u]) {
                cnt[v]++;
            }
        }
    }

    Z tot3 = 0, tot2 = 0;

    for (int v = 1; v <= n; ++v) {
        Z prob = 1;
        bool f = true;

        for (int u : g[v]) {
            int sz = 0;
            Z w = 0;

            if (deg[u] == 1) {
                sz = 1;
                w = 1;
            } else if (deg[u] == 2) {
                int ww = (g[u][0] == v) ? g[u][1] : g[u][0];
                sz = deg[ww] + 1;

                if (sz <= 2) {
                    w = 1;
                } else {
                    if (cnt[ww] == 1)
                        w = Z(1) / sz;
                    else
                        w = 0;
                }
            } else {
                sz = deg[u];

                int cc = (deg[v] > 1 ? 1 : 0);
                if (cnt[u] == cc)
                    w = Z(1) / sz;
                else
                    w = 0;
            }

            if (sz > 1)
                f = false;
            prob *= w;
            if (prob == 0)
                break;
        }

        tot3 += prob;
        if (f)
            tot2 += 1;
    }

    Z ans = (tot3 - tot2) / n;
    cout << ans << 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>;

题解 | 牛客周赛 Round 133