A 小红找数字

知识点：字符串、模拟

对 $s$ 逐字符扫描。第一个数字字符就是答案；若不存在，输出 $-1$​。

isdigit 是 std 命名空间直接提供的可以判断字符是否是数字的函数。

时间复杂度 $\mathcal{O}(|s|)$。

void solve() {
    string s;
    cin >> s;
    for (auto v : s)
        if (isdigit(v)) return cout << v << endl, void();
    cout << -1 << endl;
}

B 小红的回文串

知识点：字符串、枚举、回文判断

枚举待删除的字符 $c\in[\texttt{a},\texttt{z}]$，构造删除所有 $c$ 后的字符串 $t$。判断 $t$ 是否和原串相同，再判断是否等于其反串即可。

时间复杂度 $\mathcal{O}(26n)$。

void solve() {
    int n, ans = 0;
    string s;
    cin >> n >> s;
    for (char c = 'a'; c <= 'z'; ++c) {
        string t;
        for (auto v : s)
            if (v != c) t += v;
        ans += s != t && t == string(t.rbegin(), t.rend());
    }
    cout << ans << endl;
}

C 小红的权值

知识点：贪心、排序、前缀和、二分

将 $a_i$ 改成 $x$ 后，恰好能消去其全部贡献。设

$$b_i=|a_i-x|,\qquad S=\sum_{i=1}^{n}b_i.$$

要使权值不超过 $k$，需要消去至少 $S-k$ 的贡献。每次操作应优先消去最大的 $b_i$，将所有贡献降序排序并求前缀和，找到最小的满足 $P_j\ge S-k$ 的 $j$ 即可。

时间复杂度 $\mathcal{O}(n\log n+q\log n)$。

void solve() {
    int n, q, x, s = 0;
    cin >> n >> q >> x;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i], a[i] = abs(a[i] - x), s += a[i];

    sort(a.rbegin(), a.rend());
    vector<int> pre(1);
    for (auto v : a) pre.push_back(pre.back() + v);

    while (q--) {
        int k;
        cin >> k;
        cout << lower_bound(pre.begin(), pre.end(), s - k) - pre.begin() << endl;
    }
}

D 小红的01矩阵

知识点：状态压缩、计数 DP、二进制枚举

每列只有 $3$ 个位置，因此完整列型仅有 $2^3=8$ 种。若 $n>8$，由抽屉原理可知必然存在两列相同，答案为 $0$。

设 $dp[\mathrm{mask}]$ 表示已处理的列中，已使用的列型集合为 $\mathrm{mask}$ 时的方案数。对当前列枚举所有与输入限制兼容的列型 $x$，只要 $x$ 尚未出现，就转移到 $\mathrm{mask}\cup{x}$。最终累加所有状态。

时间复杂度 $\mathcal{O}(n\cdot2^8\cdot8)$。

void solve() {
    int n;
    cin >> n;
    if (n > 8) return cout << 0 << endl, void();

    vector<string> s(3);
    for (int i = 0; i < 3; ++i) cin >> s[i];

    array<int, 1 << 8> dp{};
    dp[0] = 1;

    for (int i = 0; i < n; ++i) {
        int pos = 0;
        for (int x = 0; x < 8; ++x) {
            bool f = 1;
            for (int j = 0; j < 3; ++j) {
                if (s[j][i] != '?' && (x >> j & 1) != s[j][i] - '0') {
                    f = 0;
                    break;
                }
            }
            if (f) pos |= 1 << x;
        }

        array<int, 1 << 8> ndp{};
        for (int mask = 0; mask < (1 << 8); ++mask) {
            for (int x = 0; x < 8; ++x) {
                if ((pos >> x & 1) && !(mask >> x & 1)) {
                    ndp[mask | 1 << x] += dp[mask];
                }
            }
        }
        dp.swap(ndp);
    }

    cout << accumulate(dp.begin(), dp.end(), 0LL) << endl;
}

E 小红的树染色

知识点：树的直径、LCA、倍增

先求初始红点集合 $R$ 的直径端点 $a,b$，直径为 $d$。树上有性质：

$$\max_{v\in R}\operatorname{dist}(u,v)=\max\bigl(\operatorname{dist}(u,a),\operatorname{dist}(u,b)\bigr).$$

将 $i$ 染红后，原红点之间的最大距离仍为 $d$；新增的最远点对一定包含 $i$。因此答案为：

$$\max\bigl(d,\operatorname{dist}(i,a),\operatorname{dist}(i,b)\bigr).$$

代码扫描红点并维护当前直径端点，再用倍增求 $\texttt{LCA}$ 与距离。

时间复杂度 $\mathcal{O}(n\log n)$。

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

    vector<int> r;
    for (int i = 1; i <= n; ++i)
        if (s[i - 1] == '1') r.push_back(i);

    Tree tr(n);
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        tr.add(u, v);
    }
    tr.work();

    int a = r[0], b = r[0], d = 0;
    for (auto v : r) {
        int da = tr.askDis(v, a), db = tr.askDis(v, b);
        if (max(da, db) <= d) continue;
        if (da >= db)
            b = v, d = da;
        else
            a = v, d = db;
    }

    for (int i = 1; i <= n; ++i) {
        cout << max({d, tr.askDis(i, a), tr.askDis(i, b)}) << endl;
    }
}

F 小红的排列计数

知识点：排列计数、组合 DP、插入法

法 $1$​ ：

推导 $1$ ：

设 $f_{m,j}$ 表示长度为 $m$ 的排列中，恰有 $j$ 个局部极小值的方案数。向长度为 $m$ 的排列插入新的最小值，并将原值全部加 $1$。

已有 $j$ 个极小值时，两个端点间隙和每个极小值相邻的两个间隙共有 $2j+2$ 个。在这些位置插入时，新极小值会抵消相邻旧极小值，或位于端点，因此极小值数量不变。其余 $m-2j-1$ 个间隙会新增一个极小值。

$$f_{m+1,j}=(2j+2)f_{m,j}+(m-2j+1)f_{m,j-1}.$$

初值为 $f_{2,0}=2$，长度为 $1$ 时答案单独为 $1$​​。

时间复杂度 $\mathcal{O}(nk)$。

void solve() {
    int n, k;
    cin >> n >> k;
    if (k < 0 || k > (n - 1) / 2) return cout << 0 << endl, void();
    if (n == 1) return cout << 1 << endl, void();

    vector<Z> dp(k + 1), ndp(k + 1);
    dp[0] = 2;

    for (int len = 2; len < n; ++len) {
        fill(ndp.begin(), ndp.end(), 0);
        for (int j = 0; j <= min(k, len / 2); ++j) {
            ndp[j] += (2 * j + 2) * dp[j];
            if (j) ndp[j] += (len - 2 * j + 1) * dp[j - 1];
        }
        dp.swap(ndp);
    }

    cout << dp[k] << endl;
}

推导 $2$ ：

记 $a_{n,k}$ 为长度为 $n$ 的排列中，恰有 $k$ 个内部极小值的方案数。对排列取补 $q_i=n+1-p_i$，内部极小值会一一对应为内部极大值，因此可直接统计内部峰值。

设

$$P_n(y)=\sum_{k\ge0}a_{n,k}y^k, \qquad F(x,y)=\sum_{n\ge0}P_n(y)\frac{x^n}{n!}.$$

内部峰值的经典指数型生成函数为：

$$F(x,y)= \frac{\sqrt{1-y}\cosh\left(x\sqrt{1-y}\right)} {\sqrt{1-y}\cosh\left(x\sqrt{1-y}\right) -\sinh\left(x\sqrt{1-y}\right)} = \frac{1} {1-\dfrac{\tanh\left(x\sqrt{1-y}\right)}{\sqrt{1-y}}}.$$

因此所求答案就是：

$$\boxed{ a_{n,k}=n!\,[x^ny^k]F(x,y) }$$

对上式求偏导并整理，可得：

$$(1-xy)F_x = (2-y)F+y-1+2y(1-y)F_y.$$

比较 $x^ny^k$ 的系数，得到：

$$a_{n+1,k} = (2k+2)a_{n,k} + (n-2k+1)a_{n,k-1}.$$

代码同推导 $1$

---

法 $2$ ：

从刚才的推导 $2$ 继续：

设 $a_{n,k}$ 为答案，$A_n(q)$ 为欧拉多项式：

$$A_n(q)=\sum_{j=0}^{n-1}\left\langle {n\atop j}\right\rangle q^j.$$

由补排列将局部极小值转化为局部极大值，可得计数多项式：

$$\sum_k a_{n,k}y^k = (1+\sqrt{1-y})^{n-1} A_n\left(\frac{1-\sqrt{1-y}}{1+\sqrt{1-y}}\right).$$

因此：

$$\boxed{ a_{n,k}=[y^k]\, (1+\sqrt{1-y})^{n-1} A_n\left(\frac{1-\sqrt{1-y}}{1+\sqrt{1-y}}\right) }$$

欧拉数可直接写为：

$$\left\langle {n\atop j}\right\rangle = \sum_{r=0}^{j+1} (-1)^r\binom{n+1}{r}(j+1-r)^n.$$

为避免处理根号，对 $k\ge1$ 使用拉格朗日反演。令 $m=n-2k$，则：

$$a_{n,k}= \frac{2^{n-2k-1}}{k} [q^{k-1}](1+q)^{2k-n} \left((1+q)A_n'(q)-(n-1)A_n(q)\right).$$

设 $E_j=\left\langle n\atop j\right\rangle$，并令：

$$f_r=(-1)^r\binom{n+1}{r}, \qquad g_t=t^n, \qquad E_j=(f*g)_{j+1}.$$

再令：

$$c_t=(-1)^t\binom{m+t-1}{t}.$$

于是可直接得到：

$$a_{n,k}= \frac{2^{n-2k-1}}{k} \sum_{j=0}^{k-1} \left((j+1)E_{j+1}+(j-n+1)E_j\right)c_{k-1-j}\pmod{998244353}.$$

当 $2k>n-1$ 时答案为 $0$。对剩余合法的 $k$，先用一次 $\texttt{NTT}$ 卷积求出所需欧拉数，再计算上式即可，这样可以处理 $n,k$ 很大的情况。

时间复杂度 $\mathcal{O}(k\log k+k\log n)$。

void solve() {
    int n, k;
    cin >> n >> k;
    if (k > (n - 1) / 2) return cout << 0 << endl, void();
    vector<Z> f(k + 2), g(k + 2);
    Z cb = 1;
    f[0] = 1;
    for (int r = 1; r <= k + 1; ++r) cb *= Z(n + 2 - r) / r, f[r] = (r & 1 ? -cb : cb);
    for (int t = 1; t <= k + 1; ++t) g[t] = Z(t).pow(n);
    auto h = NTT::mul(f, g);
    vector<Z> e(k + 1);
    for (int j = 0; j <= k; ++j) e[j] = h[j + 1];
    int m = n - 2 * k;
    vector<Z> c(k);
    c[0] = 1;
    for (int t = 1; t < k; ++t) c[t] = -c[t - 1] * Z(m + t - 1) / t;
    Z s = 0;
    for (int j = 0; j < k; ++j) {
        Z b = Z(j + 1) * e[j + 1] + Z(j - n + 1) * e[j];
        s += b * c[k - 1 - j];
    }
    cout << Z(2).pow(n - 2 * k - 1) * s / k << endl;
}

约定

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

#define int long long
#define pii array<int, 2>
#define endl "\n"

void solve() {

}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cout << fixed << setprecision(20);
    int t = 1;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
    return 0;
}

使用到的算法模板见 $\texttt{github}$ 仓库 林月的XCPC模板库