GDUT 2026 月赛 题解

签到题。零输入，直接把字符串打印出来即可，时间、空间都是 O(1)。

唯一会挂的地方是抄错串：本题的串里有 7 个下划线（We_are_going_to_the_50th_World_Finals!），开头 We 是大写 W，结尾是半角感叹号，行末要有换行。

#include <cstdio>

int main() {
    // 本题零输入：一个 scanf / cin 都不要写，否则会一直等输入
    const char* ans = "We_are_going_to_the_50th_World_Finals!";
    std::puts(ans);      // puts 输出后自动补换行；用 printf 则要自己写 \n
    return 0;
}

施法的唯一作用是让空位 +1。若当前空位 > 0，提前施法只是让空位暂时变大，而下一个 s_i = 1 马上把它吃掉——这个座位存不住，等于白施。所以最优解可以在「空位 = 0 且有人到达」时才施法。

而在空位 = 0 时，餐厅必然是满的（n 个座位全被占，且 n ≥ 1），所以一定有「正在用餐的人」可以逼走，施法合法。逼走一人 → 空位变 1 → 该客人立刻坐下 → 空位回到 0。净效果就是：答案 +1，空位数不变。

于是只需 O(m) 扫一遍串，维护空位数 empty：

s_i = 0：若 empty < n 则 ++empty（题面专门说了全空时不增）。

s_i = 1：若 empty > 0 则 --empty；否则 ++ans（施法一次，empty 仍然为 0）。

样例 1：n=1,k=0，串 101 —— 第 1 个 1 时 empty=0，施法一次；随后 0 让 empty 变 1，最后一个 1 顺利入座，答案 1。

样例 2：n=3,k=2，串 1110 —— 前两个 1 吃掉两个空位，第三个 1 时 empty=0 需施法一次，答案 1。

样例 3：n=2,k=2，串 00111 —— 前两个 0 因为全空所以空位不变（仍是 2），两个 1 坐满，第三个 1 施法一次，答案 1。

#include <cstdio>

// B：只需跟踪"空位数"这一个状态。
// 施法只在空位为 0 的那一刻才可能有用：让一名正在用餐的人离开，
// 空位 +1，随后到达者立刻坐下，空位又回到 0，净效果就是"多接待一人"。
// 提前施法是浪费（空位迟早会被吃掉），所以贪心按需施法即可。
int main() {
    int T;
    std::scanf("%d", &T);
    static char s[1000005];
    while (T--) {
        int n, k, m;
        std::scanf("%d %d %d", &n, &k, &m);
        std::scanf("%s", s);
        long long empty = k, magic = 0;
        for (int i = 0; i < m; ++i) {
            if (s[i] == '0') {
                if (empty < n) ++empty;      // 全员都在吃时没人能离开，空位不变
            } else {
                if (empty > 0) --empty;      // 有空位，直接入座
                else ++magic;                // 满座：逼走一人腾位，坐下后仍满座
            }
        }
        std::printf("%lld\n", magic);
    }
    return 0;
}

第一步 O(M)：对每首歌维护 best[i]，用 S(d[s], a) 去更新取最大值。同一首歌多次游玩只留最高分，正是「同一首歌最多出现一次」的含义。

第二步 O(N log N)：把 best[1..N] 降序排序，取前 min(N, 30) 个求和，再除以 30。不足 30 首的位置按 0 分补，而补 0 不影响和，所以直接只加前 min(N,30) 项即可。

评分公式要注意 a 是「百分数本体」：a = 97.50 时给 d 分，a = 100.90 时给 d + 2.15 分，中间线性。a = 97.49 虽然只差 0.01，也是 0 分——样例的第 3 首歌正是这个陷阱。

验样例：歌 1 最高 15.90 + 2.15 = 18.05；歌 2 在 99.20% 得 12.00 + 2.15 × (99.20−97.50)/3.40 = 13.075；歌 3 的 ACC 97.49 < 97.50 得 0。B30 之和 31.125，其余 27 个位置补 0，Rating = 31.125 / 30 = 1.0375。

double 的精度远好于 1e-6 的宽容度，输出 10 位小数即可。

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>

// C：每首歌只留最高单曲评分，然后取前 30 高求和除以 30。
// 关键三点：① 同一首歌的多次游玩只取 max；② 不足 30 首用 0 补齐（0 不影响和）；
// ③ 评分公式里 a 是百分数本体（如 97.50），不是小数。
static double scoreOf(double d, double a) {
    if (a < 97.50) return 0.0;
    return d + 2.15 * (a - 97.50) / (100.90 - 97.50);
}

int main() {
    int N, M;
    std::scanf("%d %d", &N, &M);
    std::vector<double> d(N + 1), best(N + 1, 0.0);
    for (int i = 1; i <= N; ++i) std::scanf("%lf", &d[i]);
    for (int j = 0; j < M; ++j) {
        int s;
        double a;
        std::scanf("%d %lf", &s, &a);
        double sc = scoreOf(d[s], a);
        if (sc > best[s]) best[s] = sc;               // 每首歌只保留最高分
    }
    // best[1..N] 是各歌的最高分；从大到小排，取前 30
    std::sort(best.begin() + 1, best.end(), std::greater<double>());
    double sum = 0.0;
    for (int i = 1; i <= std::min(N, 30); ++i) sum += best[i];   // 缺的位置补 0
    std::printf("%.10f\n", sum / 30.0);               // 分母恒为 30，不是 min(N,30)
    return 0;
}

三进制数字 ∈ {0, 1, 2}，所以各位数字之积只可能是 0，或者 2^t（t 为数字 2 的个数）。这把问题一下压扁了：

情形一：这个数含 0 且至少两位 → 第一步的积就是 0，而 0 本身是一位数，持续性 = 1。

情形二：数字只由 1 和 2 组成 → 积恒等于 2^t，其中 t 是数字 2 的个数，持续性 = 1 + P(2^t)（P 表示持续性）。

枚举 t = 0..38 直接算 P(2^t)：P(1) = P(2) = 0，P(4) = 1（4 = 11₃ → 1），P(8) = 2（8 = 22₃ → 4 → 1），而 t ≥ 4 时 2^t 的三进制表示必然含 0，P(2^t) = 1。

所以可达的持续性只有 {0, 1, 2, 3}，x ≥ 4 一律输出 −1。最小代表分别是：x=0 → 1（一位数）、x=1 → 10（1×0 = 0）、x=2 → 22（样例）、x=3 → 222（222₃ = 26 → 8 → 4 → 1，三步）。

程序里不必背表：对 t = 0..38 现场算 1 + P(2^t) 去匹配 x 就行，复杂度 O(38 log)。

#include <cstdio>
#include <string>

// D：三进制只有 0/1/2 三个数字，乘法持续性的取值范围被死死卡住。
//   ① 一个数若含数字 0 且至少两位 -> 积为 0，0 是一位数，持续性 = 1；
//   ② 只含 1/2 -> 积恒等于 2^(2 的个数)，记 t = 2 的个数，持续性 = 1 + P(2^t)。
// 于是可达集合 = {0} U {1 + P(2^t) : t = 0..38}，用暴力枚举就能确定。
// 实测：P(2^t) 在 t<=38 内只取 0/1/2，可达持续性只有 0,1,2,3，
// 故 x>=4 一律输出 -1。最小代表：1、10、22、222。

// 三进制下的乘法持续性
static int persistence(unsigned long long n) {
    int steps = 0;
    while (n > 2) {                 // 0/1/2 都是一位数，停
        unsigned long long p = 1;
        while (n > 0) { p *= n % 3; n /= 3; }
        n = p;                      // 含 0 时 p = 0，下一轮直接停
        ++steps;
    }
    return steps;
}

int main() {
    int x;
    if (std::scanf("%d", &x) != 1) return 0;
    // 一位数：持续性 0
    if (x == 0) { std::puts("1"); return 0; }
    // 枚举"2 的个数" c，构造 c 个 2 + 若干 1 保证长度 >= 2
    for (int c = 0; c <= 38; ++c) {
        int extra = (c == 0 ? 2 : (c == 1 ? 1 : 0));   // 让总长度至少 2
        int len = c + extra;
        if (len > 38) break;
        unsigned long long v = 1ULL << c;               // c <= 38，2^c 不会溢出
        if (1 + persistence(v) == x) {
            std::string ans(c, '2');
            ans.append(extra, '1');
            std::puts(ans.c_str());
            return 0;
        }
    }
    std::puts("-1");
    return 0;
}

设所有半径的最大值为 R。点 v 被源 s 覆盖要求 dist(s,v) < r_s ≤ R，而两边都是整数，所以等价于 dist(s,v) ≤ R − 1。

必要性：对每个 v 都要存在某个 s 使 dist(s,v) ≤ R − 1，即 min_s dist(s,v) ≤ R − 1，于是 R ≥ 1 + max_v min_s dist(s,v)。

充分性：把所有源的半径都设成同一个 R。此时覆盖集合就是「半径 R − 1 的球」之并；只要 R − 1 ≥ max_v min_s dist(s,v)，就全覆盖了。注意不同的 r_i 之间没有任何耦合约束（没有总能量预算），所以「让所有源都用满」永远不亏。

结论：答案 = 1 + max_v min_s dist(s,v)。做法就是多源 Dijkstra：把所有源以距离 0 一起入堆，跑完取 dist 的最大值再加 1。

验样例 1：源为点 1，dist = 0, 5, 12，max = 12 → 13。验样例 2：源为 1 和 5，最近源距离 = 0, 4, 7, 2, 0，max = 7 → 8。

路径长度可达 4 × 10^5 × 10^9 = 4 × 10^14，必须 64 位整数。

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>

// E：答案就是 "1 + 树上每个点到最近影响源的距离" 的最大值。
// 证明（两句话）：设所有半径的最大值为 R。
//   必要性：点 v 被源 s 覆盖要求 dist(s,v) < r_s <= R，即 dist 至多 R-1，
//           所以 R >= 1 + min_s dist(s,v)，对每个 v 都成立。
//   充分性：把每个源的半径都取 R，覆盖集合就是半径 R-1 的球之并，正好达标。
// 于是先多源 Dijkstra 求出 dist 数组，取 max 再加 1。边权可到 1e9、路径可到 4e14，必须 64 位。

const int MAXN = 400005;
const int MAXE = 800005;

static int head[MAXN], to[MAXE], nxt[MAXE], ecnt;
static long long wt[MAXE];

static inline void addEdge(int u, int v, int w) {
    to[++ecnt] = v; wt[ecnt] = w; nxt[ecnt] = head[u]; head[u] = ecnt;
}

static char buf[1 << 24];
static int blen, bpos;

static inline int nextInt() {
    while (bpos < blen && (buf[bpos] < '0' || buf[bpos] > '9')) ++bpos;
    int x = 0;
    while (bpos < blen && buf[bpos] >= '0' && buf[bpos] <= '9') x = x * 10 + (buf[bpos++] - '0');
    return x;
}

int main() {
    blen = (int)fread(buf, 1, sizeof(buf), stdin);
    int n = nextInt(), m = nextInt();
    ecnt = 0;
    for (int i = 1; i <= n; ++i) head[i] = 0;
    for (int i = 1; i < n; ++i) {
        int u = nextInt(), v = nextInt(), w = nextInt();
        addEdge(u, v, w);
        addEdge(v, u, w);
    }

    const long long INF = (long long)4e18;
    std::vector<long long> dist(n + 1, INF);
    typedef std::pair<long long, int> PII;
    std::priority_queue<PII, std::vector<PII>, std::greater<PII> > pq;

    for (int i = 0; i < m; ++i) {
        int s = nextInt();
        dist[s] = 0;
        pq.push(PII(0, s));          // 所有源同时入堆 = 多源最短路
    }
    while (!pq.empty()) {
        PII cur = pq.top(); pq.pop();
        long long d = cur.first;
        int u = cur.second;
        if (d > dist[u]) continue;
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            if (d + wt[e] < dist[v]) {
                dist[v] = d + wt[e];
                pq.push(PII(dist[v], v));
            }
        }
    }

    long long far = 0;
    for (int i = 1; i <= n; ++i) if (dist[i] > far) far = dist[i];
    std::printf("%lld\n", far + 1);
    return 0;
}

记 next[p] 为 p 之后与 S[p] 同字符的下一个位置（没有则记 n+1）。那么 S[i..j] 里每个字符恰好在它「最后一次出现」的位置被数到一次，即 w(S[i..j]) = #{ p ∈ [i, j] : next[p] > j }。

交换求和次序并整理，可以得到一个很干净的闭式：

Ans(l, r) = Σ_{p=l..r} (p − l + 1) · c_p(r)， 其中 c_p(r) = min(r, next[p] − 1) − p + 1。

c_p(r) 的含义是：p 在多少个右端点 r' ≤ r 上仍然是「最后一次出现」，也就是它对 B 数组的累计贡献。

于是 Ans = S1 − l · S2，其中 S2 = Σ c_p(r)、S1 = Σ (p + 1) · c_p(r)（p 取遍 [l, r]）。用两个树状数组分别维护 c_p 和 (p+1)·c_p 即可。

关键观察：当右端点从 r−1 走到 r 时，唯一会「死掉」的位置是上一个与 S[r] 同字符的位置 pv —— 它的 next 就是 r，从此刻起 c_pv 永远定格为 r − pv，把它塞进树状数组。而仍然活着的位置恰好是 26 个字符各自的最后一次出现位置，最多 26 个，查询时直接扫一遍累加，不必进树状数组。

复杂度 O(n log n + q (26 + log n))，Σn、Σq 各 10^6 都跑得很快（实测 1.6s）。

验样例：S = abc，next = 4, 4, 4，于是 c = 3, 2, 1；S2 = 6，S1 = 2×3 + 3×2 + 4×1 = 16；Ans(1,3) = 16 − 1×6 = 10 ✓Ans(1,1) = 2 − 1×1 = 1 ✓ Ans(2,3) = 10 − 2×3 = 4 ✓

#include <cstdio>
#include <cstring>

// F：Ans(l,r) = sum_{l<=i<=j<=r} w(S[i..j])
// 关键变形：把"每个子串的不同字符数"换成"每个位置 p 作为某字符最后一次出现"的次数。
//   w(S[i..j]) = #{ p in [i,j] : next[p] > j }，next[p] 是 p 之后同字符的下一个位置。
// 交换求和次序可得
//   Ans(l,r) = sum_{p=l..r} (p-l+1) * c_p(r),
//   c_p(r)   = min(r, next[p]-1) - p + 1  = "p 在多少个 r' <= r 里仍存活"。
// 于是答案 = S1 - l*S2，其中
//   S2 = sum c_p(r)，S1 = sum (p+1)*c_p(r)（p 取遍 [l,r]）。
// 当 r 前进时：只有"上一个同字符位置"会死掉，把它的 c 定死成 (r-p) 塞进树状数组；
// 而仍然存活的 p 恰好是 26 个字符各自的最后出现位置，最多 26 个，直接扫一遍即可。

const int MAXN = 1000005;

static int n, q;
static char s[MAXN];
static long long bit1[MAXN], bit2[MAXN];   // bit1 存 c_p，bit2 存 (p+1)*c_p
static int last[26];
static int qhead[MAXN], qnext[MAXN], qleft[MAXN];
static long long qans[MAXN];

static inline void bitAdd(long long* b, int i, long long v) {
    for (; i <= n; i += i & (-i)) b[i] += v;
}
static inline long long bitSum(long long* b, int i) {
    long long r = 0;
    for (; i > 0; i -= i & (-i)) r += b[i];
    return r;
}

static char obuf[1 << 25];
static int olen;

static inline void writeLL(long long v) {
    if (v == 0) { obuf[olen++] = '0'; return; }
    char t[24]; int k = 0;
    while (v > 0) { t[k++] = (char)('0' + v % 10); v /= 10; }
    while (k > 0) obuf[olen++] = t[--k];
}

int main() {
    int T;
    if (std::scanf("%d", &T) != 1) return 0;
    while (T--) {
        std::scanf("%d %d", &n, &q);
        std::scanf("%s", s + 1);
        for (int i = 0; i <= n + 1; ++i) { bit1[i] = bit2[i] = 0; qhead[i] = -1; }
        memset(last, 0, sizeof(last));
        for (int j = 0; j < q; ++j) {
            int l, r;
            std::scanf("%d %d", &l, &r);
            qleft[j] = l;
            qnext[j] = qhead[r];          // 按右端点把询问挂成链表
            qhead[r] = j;
        }
        for (int r = 1; r <= n; ++r) {
            int ch = s[r] - 'a';
            int pv = last[ch];
            if (pv) {                     // pv 的 next 就是 r，它的 c 从此定格为 r-pv
                long long v = r - pv;
                bitAdd(bit1, pv, v);
                bitAdd(bit2, pv, (long long)(pv + 1) * v);
            }
            last[ch] = r;
            for (int e = qhead[r]; e != -1; e = qnext[e]) {
                int l = qleft[e];
                long long S2 = bitSum(bit1, r) - bitSum(bit1, l - 1);
                long long S1 = bitSum(bit2, r) - bitSum(bit2, l - 1);
                for (int c = 0; c < 26; ++c) {
                    int p = last[c];      // 存活位置：各字符的最后一次出现
                    if (p >= l) {         // last[c] <= r 恒成立，只需判下界
                        long long cc = r - p + 1;
                        S2 += cc;
                        S1 += (long long)(p + 1) * cc;
                    }
                }
                qans[e] = S1 - (long long)l * S2;
            }
        }
        for (int j = 0; j < q; ++j) {
            if (j) obuf[olen++] = ' ';
            writeLL(qans[j]);
        }
        obuf[olen++] = '\n';
    }
    fwrite(obuf, 1, olen, stdout);
    return 0;
}

先排序。若两组的人交错（a_u ≤ a_v ≤ a_w，u、w 同组而 v 在别组），把 v 换进来不会让「最大值−最小值」变大，而每个组的 a_min 也不会变大——所以最优解一定可以取成连续段分组。

对一段 [l, r]：要存在整数 x 使所有 |x − a_i| ≤ d，等价于 a_r − a_l ≤ 2d。在此前提下 k·x 随 x 增大而增大，而 x 的上界是 a_l + d（a_l、d 都是整数，所以 x 也是整数）。于是该段贡献 (r − l + 1)(a_l + d)。

关键剪枝：把一段拆成更小的段后，每一小段的 a_min 都不小于原段的 a_l，所以 Σ size·(a_min + d) 只会变大；而最细的拆法只能拆到 2 元组和 3 元组（每组至少 2 人）。因此最优解只由 2 元组和 3 元组构成。

于是 dp[i] = 前缀 i 的最大总分，转移只看最后一段是 2 个还是 3 个：

dp[i] = max( dp[i−2] + 2(a_{i−1} + d) 若 a_i − a_{i−1} ≤ 2d , dp[i−3] + 3(a_{i−2} + d) 若 i ≥ 3 且 a_i − a_{i−2} ≤ 2d )。

用 −∞ 表示该前缀无法划分；dp[n] 仍是 −∞ 就输出 Impossible。复杂度 O(n log n)（排序）。

验样例 1：排序后 0 1 2 3，dp = 0, −∞, 4, 6, 12 —— 分成 {0,1} 取 x=2、{2,3} 取 x=4，总分 4 + 8 = 12。

验样例 2：d = 0 时只有原始分相同的评委能同组，原始分为 0 的评委（只有 1 人）无法进任何合法组 → Impossible。

验样例 3：三人一组，a_min = 2，x 取 2 + 2 = 4，总分 3 × 4 = 12。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <climits>

// G：排序后最优解的分组一定是连续段（把交错的两个人互换不会变差）。
// 一段 [l,r] 里所有 a 都要满足 |x-a| <= d，故 x 最大取 a_l + d（要整数，a_l、d 都是整数），
// 该段贡献 (r-l+1)*(a_l+d)，可行当且仅当 a_r - a_l <= 2d。
// 再注意一个单调事实：把一个大段拆成若干小段，每小段的 a_l 都不小于原段的 a_l，
// 所以拆开只会更赚 —— 最细的拆法只能拆到 2 元组和 3 元组。
// 于是 dp[i] 只用考虑"最后一段是 2 个还是 3 个"。
int main() {
    int T;
    std::scanf("%d", &T);
    const long long NEG = LLONG_MIN / 4;
    while (T--) {
        int n;
        long long d;
        std::scanf("%d %lld", &n, &d);
        std::vector<long long> a(n + 1);
        for (int i = 1; i <= n; ++i) std::scanf("%lld", &a[i]);
        std::sort(a.begin() + 1, a.end());

        long long lim = 2 * d;
        std::vector<long long> dp(n + 1, NEG);
        dp[0] = 0;
        for (int i = 2; i <= n; ++i) {
            if (dp[i - 2] > NEG / 2 && a[i] - a[i - 1] <= lim)      // 最后一段是 {i-1, i}
                dp[i] = std::max(dp[i], dp[i - 2] + 2 * (a[i - 1] + d));
            if (i >= 3 && dp[i - 3] > NEG / 2 && a[i] - a[i - 2] <= lim)  // 最后一段是 {i-2,i-1,i}
                dp[i] = std::max(dp[i], dp[i - 3] + 3 * (a[i - 2] + d));
        }
        if (dp[n] <= NEG / 2) std::puts("Impossible");
        else std::printf("%lld\n", dp[n]);
    }
    return 0;
}

第一阶段（1 次询问）：问 k = 10^9，拿到 a = ⌊n / 10^9⌋。由整除的定义立即有 n ∈ [a·10^9, (a+1)·10^9 − 1]，区间宽度正好 10^9。

第二阶段（把 k 当比较器）：在窗口内取 k = mid。因为 mid ≥ a·10^9 且 n < (a+1)·10^9 ≤ 2·mid，所以 ⌊n/mid⌋ 只可能是 0 或 1，且⌊n/mid⌋ ≥ 1 ⟺ n ≥ mid。一次询问等于一次比较。

于是对宽度 10^9 的窗口二分，需要 ⌈log2 10^9⌉ = 30 次。总计 1 + 30 = 31 次，卡进 32。

两个边界要处理：n = 10^18 时 a = 10^9，窗口上界被 10^18 截断成单点，直接输出；a ≥ 1 是因为 n ≥ 10^9，所以下界 a·10^9 一定 ≥ 10^9，k 不会越界。

样例解读：n = 10^9，a = 1，窗口 [10^9, 2·10^9 − 1]。问 1234567890 得 0 ⇒ n < 1234567890；问 1000000001 得 0 ⇒ n < 1000000001，配合 n ≥ 10^9 就锁定 n = 10^9。

#include <cstdio>
#include <cstdlib>
#include <algorithm>

// H：k 可以取到 1e18，而 n <= 1e18，所以询问 k 得到的 floor(n/k) 只有
//   "n >= k ? 至少 1 : 0" 这一位信息最好用。
// 但若直接对 [1e9,1e18] 二分要 60 次，超了。先花 1 次询问 k = 1e9 拿到
//   a = floor(n/1e9)，就把 n 锁进长度恰好 1e9 的窗口 [a*1e9, (a+1)*1e9-1]。
// 窗口内再用 k = mid 询问：由 mid >= a*1e9 且 n < (a+1)*1e9 <= 2*mid 可知
//   floor(n/mid) >= 1  <=>  n >= mid
// 正好是一次比较，于是 30 次二分足够。总计 1 + 30 = 31 <= 32 次。

static long long ask(long long k) {
    std::printf("? %lld\n", k);
    std::fflush(stdout);
    long long q;
    if (std::scanf("%lld", &q) != 1) std::exit(0);
    return q;
}

int main() {
    const long long LO = 1000000000LL;         // 1e9
    const long long HI = 1000000000000000000LL; // 1e18
    long long a = ask(LO);                     // a = floor(n / 1e9)
    long long lo = a * LO;
    long long hi = std::min((a + 1) * LO - 1, HI);
    if (lo < LO) lo = LO;
    while (lo < hi) {
        long long mid = lo + (hi - lo + 1) / 2;   // 上取整，避免死循环
        if (ask(mid) >= 1) lo = mid;              // n >= mid
        else hi = mid - 1;
    }
    std::printf("! %lld\n", lo);
    std::fflush(stdout);
    return 0;
}

用期望的线性性：E[存活人数] = Σ_i P(第 i 人存活)，问题变成 n 个独立的小概率。

j 打中 i 的概率 = (a_j / 100) × 1/(n − 1)。所以 P(i 存活) = Π_{j ≠ i} p_j，其中 p_j = 1 − a_j / (100(n − 1))。

于是 E = Σ_i Π_{j≠i} p_j = (Π_j p_j) × (Σ_i 1/p_i) —— 一次前缀积加上一次倒数和，O(n)。

p_j = 0 怎么办？p_j = 0 ⟺ a_j = 100(n − 1)。因为 a_j ≤ 100，这只可能出现在 n = 2 且 a_j = 100 时。分三种情况：两个 0 → 所有人都必死，答案 0；恰好一个 0 → 只有那个人的「他人乘积」非零，答案就是其余 p 的乘积；没有 0 → 用上面的公式。

模运算：p_j = (100(n − 1) − a_j) / (100(n − 1))，1/p_j = 100(n − 1) / (100(n − 1) − a_j)。由于 n ≤ 2 × 10^6，有 100(n − 1) ≤ 2 × 10^8 < 998244353，分母恒可逆。

验样例 2：n = 2，p_1 = 3/4、p_2 = 1/5。P(1 存活) = 1/5，P(2 存活) = 3/4，E = 19/20，取模得 848507701。

验样例 1：n = 3，p 全为 1/2，E = 3 × (1/2)^2 = 3/4，取模得 249561089。

#include <cstdio>
#include <cstring>

// I：求存活人数期望。用期望的线性性，逐个算每个人存活的概率。
// 子弹 j 打中 i 的概率 = (a_j/100) * 1/(n-1)，所以
//   P(i 存活) = prod_{j != i} (1 - a_j / (100(n-1))) = prod_{j != i} p_j。
// 于是 E = sum_i prod_{j!=i} p_j = (prod_j p_j) * (sum_i 1/p_i)。
// p_j = 0 只会出现在 n == 2 且 a_j == 100 时（此时 100(n-1) == 100），要单独处理：
//   两个 0 -> 全员必死，答案 0；一个 0 -> 只有那个零的"别人乘积"非零。

typedef long long ll;
const ll MOD = 998244353;

static ll pw(ll b, ll e) {
    ll r = 1;
    b %= MOD;
    while (e > 0) {
        if (e & 1) r = r * b % MOD;
        b = b * b % MOD;
        e >>= 1;
    }
    return r;
}

static char buf[1 << 24];
static int blen, bpos;

static inline int nextInt() {
    while (bpos < blen && (buf[bpos] < '0' || buf[bpos] > '9')) ++bpos;
    int x = 0;
    while (bpos < blen && buf[bpos] >= '0' && buf[bpos] <= '9') x = x * 10 + (buf[bpos++] - '0');
    return x;
}

int main() {
    blen = (int)fread(buf, 1, sizeof(buf), stdin);
    int T = nextInt();
    static int cnt[101];
    static ll invMemo[101];
    while (T--) {
        int n = nextInt();
        ll Dnum = 100LL * (n - 1);          // 分母的分子部分，<= 2e8 < MOD
        ll invD = pw(Dnum % MOD, MOD - 2);
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < 101; ++i) invMemo[i] = -1;

        ll zeros = 0, accNum = 1;
        for (int i = 0; i < n; ++i) {
            int x = nextInt();
            ++cnt[x];
            ll num = Dnum - x;              // p = num / Dnum
            if (num == 0) ++zeros;
            else accNum = accNum * (num % MOD) % MOD;
        }
        ll prod = accNum * pw(invD, n - zeros) % MOD;   // 只对非零项除 Dnum，零项已跳过

        ll invsum = 0;
        for (int x = 0; x <= 100; ++x) {
            if (!cnt[x]) continue;
            ll num = Dnum - x;
            if (num == 0) continue;
            if (invMemo[x] < 0) invMemo[x] = pw(num % MOD, MOD - 2);
            // 1/p = Dnum / num
            ll invp = (Dnum % MOD) * invMemo[x] % MOD;
            invsum = (invsum + (ll)cnt[x] % MOD * invp) % MOD;
        }

        ll ans;
        if (zeros >= 2) ans = 0;
        else if (zeros == 1) ans = prod;            // 只有那个零的"他人乘积"非零
        else ans = prod * invsum % MOD;
        std::printf("%lld\n", ans);
    }
    return 0;
}

先看可行性结构：若某个 a_i 单独就不整除 u，那么任何含 i 的区间都不可能整除 u，窗口只能从 i+1 重新开始。

否则，把左端点 s 往左移只会让乘积变大、更难整除，所以「能让 Πa[s..i] 整除 u」的 s 恰好是一段后缀 [L, i]。用双指针维护 L：每加入 a_i 就把左端往右挪，直到乘积重新整除 u。由于 L 单调不减，总复杂度 O(n)。

再叠 DP：dp[i] 表示前缀 i 的最大有效区间数。最后一段是 [j + 1, i]，必须满足 i − j ≥ k，即分界点 j ≤ i − k。于是

dp[i] = max( 1 + max{ dp[j] : L − 1 ≤ j ≤ i − k } , max{ dp[j] : 0 ≤ j ≤ min(L − 2, i − k) } )。

前一项表示最后一段有效（+1），后一项表示最后一段无效（不加分，但允许存在）。两个区间最大值都用线段树查。

乘积不会溢出：因为只在 prod 整除 u 时保留，prod ≤ u ≤ 10^18；加入 a_i 前先用 prod > u / a[i] 判一下，再决定是否把左端挪走。

验样例：a = 2 2 3 1 2 2 3 5，k = 3，u = 12。L 依次为 1,1,1,1,2,3,4,9，dp = 0,−∞,−∞,1,1,0,2,2,1，输出 dp[8] = 1。唯一有效的划分是 [1,3]（积 12）+ 剩下的 [4,8]（积 60，无效）。

#include <cstdio>
#include <algorithm>
#include <climits>

// J：dp[i] = 前缀 i 能拿到的最大有效区间数。
// 对固定右端点 i，"起点 s 使 prod(a[s..i]) 整除 u" 的 s 构成一段后缀 [L, i]
// （把区间再往左延长只会让乘积变大、更难整除，所以可行集合对 s 单调），
// 用双指针维护这个 L；L = i+1 表示一个有效段都没有。
// 于是
//   dp[i] = max( 1 + max dp[L-1 .. i-k] ,  max dp[0 .. min(L-2, i-k)] )
// 前一项 = 最后一段有效，后一项 = 最后一段无效（无效段允许，只是不加分）。
// 注意长度约束：最后一段长度 >= k，所以分界点 j <= i-k。
// 两个区间最大值都落在 dp 上，线段树查询，整体 O(n log n)。

typedef long long ll;
const ll NEG = LLONG_MIN / 4;

static int n, k;
static ll u;
static ll a[500005];
static ll dp[500005];

static int segsz;
static ll seg[1 << 21];

static void segInit(int m) {
    segsz = 1;
    while (segsz < m) segsz <<= 1;
    for (int i = 0; i < 2 * segsz; ++i) seg[i] = NEG;
}
static void segUpdate(int p, ll v) {
    p += segsz;
    seg[p] = v;
    for (p >>= 1; p; p >>= 1) seg[p] = std::max(seg[p << 1], seg[p << 1 | 1]);
}
static ll segQuery(int l, int r) {          // 闭区间 [l,r]；l > r 返回 NEG
    if (l > r) return NEG;
    ll res = NEG;
    for (l += segsz, r += segsz; l <= r; l >>= 1, r >>= 1) {
        if (l & 1) res = std::max(res, seg[l++]);
        if (!(r & 1)) res = std::max(res, seg[r--]);
    }
    return res;
}

int main() {
    std::scanf("%d %d %lld", &n, &k, &u);
    for (int i = 1; i <= n; ++i) std::scanf("%lld", &a[i]);

    segInit(n + 1);
    dp[0] = 0;
    segUpdate(0, 0);

    int L = 1;
    ll prod = 1;                 // prod = a[L] * ... * a[i]，始终 <= u，不会乘爆
    for (int i = 1; i <= n; ++i) {
        if (u % a[i] != 0) {
            // 单个 a[i] 都不整除 u，任何有效段都不能含 i：窗口清空
            L = i + 1;
            prod = 1;
        } else {
            while (L <= i && prod > u / a[i]) { prod /= a[L]; ++L; }  // 先防溢出
            prod *= a[i];
            while (L <= i && u % prod != 0) { prod /= a[L]; ++L; }    // 再保证整除
        }

        int hi = i - k;                        // 分界点 j 的上界
        ll best = NEG;
        if (hi >= L - 1) best = std::max(best, segQuery(L - 1, hi) + 1);
        if (hi >= 0 && L - 2 >= 0) best = std::max(best, segQuery(0, std::min(L - 2, hi)));
        dp[i] = best;
        segUpdate(i, dp[i]);
    }
    std::printf("%lld\n", dp[n] < 0 ? 0LL : dp[n]);
    return 0;
}

以中心 (n, n) 为原点看偏移 dx = x − n、dy = y − n。第 d 圈正是 max(|dx|, |dy|) = d 的等值线，也就是「切比雪夫距离」，而这一圈的得分是 n − d。

所以每一支飞镖的得分就是 n − max(|x − n|, |y − n|)，逐个累加即可，O(k)。

验样例：n = 3。(3,3) → d = 0 → 3 分；(1,1) → max(2,2) = 2 → 1 分；(2,4) → max(1,1) = 1 → 2 分；(5,3) → max(2,0) = 2 → 1 分。合计 3 + 1 + 2 + 1 = 7 ✓

n = 1 时 d 只能为 0，得 1 分，公式自洽，不需要特判。

#include <cstdio>
#include <algorithm>

// K：(2n-1)*(2n-1) 的方阵，第 d 个环得分 n-d，其中 d 是切比雪夫距离
// d = max(|x-n|, |y-n|)。中心 (n,n) 得 n，最外环得 1。
// 逐点累加即可，注意 n<=1000、k<=4e6，总和可达 4e9，要 64 位。
int main() {
    int n, k;
    std::scanf("%d %d", &n, &k);
    long long ans = 0;
    for (int i = 0; i < k; ++i) {
        int x, y;
        std::scanf("%d %d", &x, &y);
        int d = std::max(std::abs(x - n), std::abs(y - n));
        ans += n - d;
    }
    std::printf("%lld\n", ans);
    return 0;
}

记 S_v = subtree(v)。这些集合一定是「层叠（laminar）」的：任取两个关键点 u、v，S_u 与 S_v 要么不相交，要么一个包含另一个——因为子树结构本身就是这样。

对每个关键点 v 定义 B_v = S_v 去掉它内部那些「极大关键后代」的子树。于是 B_v 两两不交、都含 v、且不含别的关键点，并且 XOR(B_v) = XOR(S_v) ⊕ (内部关键子树的异或) = 0 ⊕ 0 = 0。所以「每个关键点 v 都配一个互不相交、含 v、异或为 0 的集合 B_v」是必要条件。

反过来也够用：把这些 B_v 按任意顺序排成一条链，每个 B_v 里的关键点放在该块最前面、其余点挂在它后面，再把所有没用上的点（连同 1 号点）放在链首当作前缀，就得到一棵合法的树（v ≠ 1 时 B_v 不能含 1；若 1 是关键点则还要全局异或为 0，此时 B_1 自动取剩下的全部点）。

于是问题化归为：为每个关键点 v 找一个互不相交的集合 B_v ∋ v、XOR(B_v) = 0（即给每个需求找一个异或等于 a_v 的辅助集合）。这才是真正要写搜索的部分——也正是我在这里不敢保证写对的地方。

反例（证明「子树 = 输入顺序里的连续段」这个简化是错的）：n = 4、a = [1, 5, 7, 5]、关键点 {2}。树 1-2、2-4、1-3 中 subtree(2) = {2, 4}，异或 5 ⊕ 5 = 0，合法；而任何让子树等于连续段的构造都做不到——{[2], [2,3], [2,4]} 的异或分别是 5、2、7，没有 0。

逐条读入四个字段，若最后一项为 1，就拼接 "gdut_" + 队名 + " " + 赛站名 + " " + 比赛日期 输出一行。

n ≤ 50，直接按输入顺序输出即可，O(n) 时间、O(1) 额外空间。多条输出拼进一个缓冲区再一次性写出更省事。

#include <cstdio>
#include <iostream>
#include <string>

// M：纯筛选。报名结果为 1 的记录输出，格式为 gdut_<队名> <赛站> <日期>，顺序任意。
int main() {
    int n;
    std::scanf("%d", &n);
    std::string out;
    for (int i = 0; i < n; ++i) {
        char team[64], site[32], date[32];
        int ok;
        std::scanf("%s %s %s %d", team, site, date, &ok);
        if (ok == 1) {
            out += "gdut_";
            out += team;
            out += ' ';
            out += site;
            out += ' ';
            out += date;
            out += '\n';
        }
    }
    std::fwrite(out.data(), 1, out.size(), stdout);
    return 0;
}

mex(S) ≤ K ⟺ 0, 1, …, K 里至少有一个数不在 S 里。（反之若 0..K 全都在 S 里，mex 至少是 K + 1 > K。）注意是「至少缺一个」，不是「全都缺」。

于是答案 = max_{t = 0..K}（区间里完全不含 t 的最长长度）。而对固定的 t，完全不含 t 的最长子段就是 t 的相邻出现位置之间的最大空档，并且要把「第一个出现位置之前」和「最后一个出现位置之后」这两段也算进去。

还有一个 O(1) 的快路：因为 a_i ≤ n，所以 K > n 时必有某个 t ∈ [0, K] 永不出现（例如 t = n + 1），答案直接是 n。这样就不需要为 10^18 级别的 K 开数组。

复杂度 O(n + K) = O(n)。

验样例 1：n = 8、K = 2、a = 0 1 2 3 0 2 3 1。t = 0 位置 {1,5}，空档 max(0,3,3) = 3；t = 1 位置 {2,8}，空档 max(1,5,0) = 5；t = 2 位置 {3,6}，空档 max(2,2,2) = 2 → 答案 5（区间 [3,7] 缺 1）。

验样例 2：n = 5、K = 0，t = 0 位置 {3}，空档 max(2,2) = 2 → 答案 2。

#include <cstdio>
#include <vector>
#include <algorithm>

// N：mex(S) <= K 等价于 "0..K 里至少缺一个数"（若 0..K 全出现则 mex >= K+1）。
// 于是答案 = max_{t=0..K} (区间里完全不含 t 的最长子段)
//          = max_t (t 的相邻出现位置之间的最大空档)。
// 又因 a_i <= n：K > n 时必有某个 t 永不出现，答案直接是 n。
int main() {
    int T;
    std::scanf("%d", &T);
    static int a[200005];
    while (T--) {
        int n;
        long long K;
        std::scanf("%d %lld", &n, &K);
        for (int i = 1; i <= n; ++i) std::scanf("%d", &a[i]);
        if (K > n) {                          // 0..K 里一定有值超出 a_i 范围，必不出现
            std::printf("%d\n", n);
            continue;
        }
        std::vector<std::vector<int> > pos((size_t)K + 1);
        for (int i = 1; i <= n; ++i)
            if (a[i] <= K) pos[a[i]].push_back(i);
        int best = 0;
        for (int t = 0; t <= (int)K; ++t) {
            int prev = 0;                     // 哨兵：位置 0
            for (size_t j = 0; j < pos[t].size(); ++j) {
                int p = pos[t][j];
                best = std::max(best, p - prev - 1);
                prev = p;
            }
            best = std::max(best, n - prev);  // 最后一段到 n 为止
        }
        std::printf("%d\n", best);
    }
    return 0;
}