2025 广工月赛 题解

参数化。设 g = gcd(x, y)，x = g·u，y = g·v，gcd(u, v) = 1。则 x + y − gcd = g(u+v) − g = g(u+v−1) = k，所以 g | k，且 s := u + v = k/g + 1 固定。

反过来验证：任取 k 的约数 g、任取 1 ≤ u < s 且 gcd(u, s) = 1（因为 gcd(u, v) = gcd(u, u+v) = gcd(u, s)），令 v = s − u，则 (gu, gv) 满足方程且 gcd 恰为 g。所以枚举「约数 × u」穷尽了全部冲突数对，不重不漏。

规模估算：1081080 = 2³·3³·5·7·11·13，约数最多 256 个；对固定 g，u 只需要枚举到 ⌊maxA/g⌋（因为 g·u ≤ maxA）。总枚举量 Σ_{g|k} maxA/g = maxA·σ(k)/k ≈ 4.8×10⁶，很轻松。

把冲突对换算成位置约束：值为 x、y 的两个数在数组中的位置是 pos[x]、pos[y]，记 L = min、R = max。任何同时包含 L 与 R 的窗口都不合法，也就是「右端点 ≥ R 的窗口，左端点必须 > L」。于是记 bound[R] = max(bound[R], L+1)。

滑动窗口：left[r] = max(left[r−1], bound[r])，答案取 max(r − left[r] + 1)。注意 i = j 的情况：x = y 时方程变成 2x − x = x = k，所以「值恰好等于 k」的元素与自己冲突，此时 L = R = pos[k]，bound = pos+1，算出的窗口长度正好是 0——同一套式子顺带处理掉了。

复杂度 O(Σ_{g|k} maxA/g + n)，空间 O(maxA + n)。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; long long k;
    if (scanf("%d %lld", &n, &k) != 2) return 0;
    vector<int> a(n);
    int maxA = 0;
    for (int i = 0; i < n; i++) { scanf("%d", &a[i]); maxA = max(maxA, a[i]); }
    vector<int> pos(maxA + 1, -1);
    for (int i = 0; i < n; i++) pos[a[i]] = i;
    vector<int> bound(n, 0);                 // bound[r] = 窗口右端为 r 时，左端至少要到哪
    for (long long d = 1; d * d <= k; d++) {
        if (k % d) continue;
        for (long long g : {d, k / d}) {     // g = gcd(x,y) 必须是 k 的约数
            if (g > maxA) continue;          // x = g*u >= g
            long long s = k / g + 1;         // u + v = s
            long long lim = maxA / g;        // u、v 都不超过这个上界
            long long hi = min(s - 1, lim), lo = max(1LL, s - lim);
            for (long long u = lo; u <= hi; u++) {
                if (std::gcd(u, s) != 1) continue;   // (u,v)=1 等价于 (u,s)=1
                long long v = s - u;
                int x = (int)(g * u), y = (int)(g * v);
                if (pos[x] < 0 || pos[y] < 0) continue;
                int L = min(pos[x], pos[y]), R = max(pos[x], pos[y]);
                bound[R] = max(bound[R], L + 1);     // 含 L、R 的窗口必须从 L 右边开始
            }
        }
    }
    int left = 0, ans = 0;
    for (int r = 0; r < n; r++) {
        left = max(left, bound[r]);
        ans = max(ans, r - left + 1);
    }
    printf("%d\n", ans);
    return 0;
}

目标：对每个位置 j 定出 p_j。

询问「第 j 位放 v、其余位放 0」时，返回的 k = [p_j = v]（0 不属于 p 的值域，别的位置一定不匹配）。一个 0/1 的答案就把「p_j = v」这条假设判定完毕。

对 v = 1..n 依次处理：从左到右扫还没确定的位置，遇到返回 1 就把该位置定为 v，本个 v 结束。每个 v 至多花 n 次询问，总计 ≤ n²。实测 n = 100 的逆序排列用了 5050 次。

复杂度：O(n²) 次询问，每次输出 n 个整数，总输出量 O(n³) 个整数；n = 100 时 10⁶ 个，足够快。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    if (scanf("%d", &t) != 1) return 0;
    while (t--) {
        int n;
        if (scanf("%d", &n) != 1) return 0;
        vector<int> ans(n, 0), q(n, 0);
        for (int v = 1; v <= n; v++) {
            for (int j = 0; j < n; j++) {       // 把 v 摆在 j 位，其余位置放 0（非排列值，永不匹配）
                if (ans[j]) continue;
                fill(q.begin(), q.end(), 0);
                q[j] = v;
                printf("?");
                for (int i = 0; i < n; i++) printf(" %d", q[i]);
                printf("\n");
                fflush(stdout);
                int c;
                if (scanf("%d", &c) != 1) return 0;
                if (c) { ans[j] = v; break; }
            }
        }
        printf("!");
        for (int i = 0; i < n; i++) printf(" %d", ans[i]);
        printf("\n");
        fflush(stdout);
    }
    return 0;
}

关键恒等式：问 a = τ 时答案 = #{i : p_i = τ_i}。排列集合对复合封闭，所以「任意排列与 p 的重合数」都能无噪声地测出来。

第一步：问恒等排列，得到 F = #{i : p_i = i}。

第二步：问「交换 i、j 两位」的排列（仍是排列），记 T(i, j) = 答案 − F。把重合数展开，只有四项：T(i, j) = [p_i = j] + [p_j = i] − [p_i = i] − [p_j = j]，取值只可能是 −2..2。

对固定 i 把 T(i, j) 对 j ≠ i 求和：Σ[p_i = j] = 1 − [p_i = i]，Σ[p_j = i] = 1 − [p_i = i]，Σ[p_j = j] = F − [p_i = i]，于是 A_i = 2 − F − n·[p_i = i]。每个位置是不是不动点，一次就解出来了。

第三步：对非不动点 i，T(i, j) ≥ 1 当且仅当 j 是 p_i 或 p⁻¹(i)，所以把这些「相邻关系」连起来就得到 p 的每个环的无向版本（把有向环看成无向环，此时还剩朝向未知）。T(i, j) = 2 只可能出现在二元环上（p_i = j 且 p_j = i），可以直接定死。

第四步：长度 ≥ 3 的无向环还剩两个朝向。取候选 τ =「沿环走一步，环外恒等」，问一次：环外恒等两问贡献相同、环内没有不动点，所以 答案 − F 只能等于 L 或 0（L 为环长），据此定朝向。

询问数 = 1 + n(n−1)/2 + (#长度 ≥ 3 的环) ≤ 1 + n(n−1)/2 + ⌊n/3⌋ < n²。n = 100 时 4984 次，实测恰好是这个数。

#include <bits/stdc++.h>
using namespace std;
int n;
int ask(const vector<int>& a) {
    printf("?");
    for (int i = 0; i < n; i++) printf(" %d", a[i]);
    printf("\n");
    fflush(stdout);
    int c;
    if (scanf("%d", &c) != 1) exit(0);
    return c;
}
int main() {
    int t;
    if (scanf("%d", &t) != 1) return 0;
    while (t--) {
        if (scanf("%d", &n) != 1) return 0;
        vector<int> id(n);
        for (int i = 0; i < n; i++) id[i] = i + 1;
        if (n == 1) { printf("! 1\n"); fflush(stdout); continue; }
        int F = ask(id);                       // 不动点个数
        vector<vector<signed char>> T(n, vector<signed char>(n, 0));
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {  // 交换 i,j 两个位置上的值
                vector<int> q = id;
                swap(q[i], q[j]);
                T[i][j] = T[j][i] = (signed char)(ask(q) - F);
            }
        vector<int> p(n, 0);
        vector<char> fix(n, 0), done(n, 0);
        for (int i = 0; i < n; i++) {
            int A = 0;
            for (int j = 0; j < n; j++) if (j != i) A += T[i][j];
            // A_i = 2 - F - n*[p_i == i]
            if ((2 - F - A) / n == 1) { fix[i] = 1; p[i] = i + 1; done[i] = 1; }
        }
        for (int i = 0; i < n; i++) if (!done[i])          // T=2 就是二元环
            for (int j = i + 1; j < n; j++) if (!done[j] && T[i][j] == 2) {
                p[i] = j + 1; p[j] = i + 1; done[i] = done[j] = 1; break;
            }
        vector<vector<int>> adj(n);
        for (int i = 0; i < n; i++) if (!done[i])
            for (int j = 0; j < n; j++) if (j != i && !done[j] && T[i][j] == 1) adj[i].push_back(j);
        vector<char> vis(n, 0);
        for (int s = 0; s < n; s++) {
            if (done[s] || vis[s]) continue;
            vector<int> cyc;                    // 走出一条无向环
            int cur = s, prev = -1;
            while (!vis[cur]) {
                vis[cur] = 1; cyc.push_back(cur);
                int nxt = -1;
                for (int x : adj[cur]) if (x != prev) { nxt = x; break; }
                prev = cur; cur = nxt;
                if (cur < 0) break;
            }
            int L = (int)cyc.size();
            vector<int> q = id;                 // 猜测顺时针：cyc[t] -> cyc[t+1]
            for (int i = 0; i < L; i++) q[cyc[i]] = cyc[(i + 1) % L] + 1;
            int c = ask(q);
            bool fwd = (c - F == L);            // 环外不动，故差值只能是 0 或 L
            for (int i = 0; i < L; i++) {
                int to = fwd ? cyc[(i + 1) % L] : cyc[(i - 1 + L) % L];
                p[cyc[i]] = to + 1;
            }
        }
        printf("!");
        for (int i = 0; i < n; i++) printf(" %d", p[i]);
        printf("\n");
        fflush(stdout);
    }
    return 0;
}

这是一个「每个任务需要一台能力足够的机器」的带权调度问题：任务 j 的权值是 b_j，需要一匹 a > b_j 的马。

交换论证：按 b 降序处理。设当前最大的是 b_1。若某个最优解没有赢 b_1 而 b_1 明明能被赢下，就把「赢下集合」里权值最小的那个任务换成 b_1（马不够就挪一匹正在赢更小对手的马过来），赏金不减。归纳可知贪心最优。

实现：把 a 排序后放进 multiset，b 降序遍历，对每个 b_j 用 upper_bound(b_j) 取「第一个严格大于 b_j 的马」——这是所有能赢 b_j 的马里最慢的一匹，把更快的马留给后面（其实后面更小，但这样做天然不浪费）。找不到就放弃这个 b_j。

复杂度 O((n+m) log(n+m))；常数可以更好（排序 + 并查集/双指针），5×10⁵ 用 multiset 也只要 0.1s 量级。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < m; i++) scanf("%d", &b[i]);
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    multiset<int> have(a.begin(), a.end());
    long long ans = 0;
    for (int j = m - 1; j >= 0; j--) {          // 赏金从大到小处理
        auto it = have.upper_bound(b[j]);       // 能赢它的最慢的马
        if (it != have.end()) { ans += b[j]; have.erase(it); }
    }
    printf("%lld\n", ans);
    return 0;
}

维护 cnt[v] = 票数恰为 v 的人数、sum[v] = 这些人的编号和。那么本次答案就是 sum[cur]，cur 是当前第 k 大的票数。

维护 G = #{票数 ≥ cur}。一次操作后第 k 大最多移动 1：若 G − cnt[cur] ≥ k，说明真正的第 k 大在 cur 之上，做 G −= cnt[cur]、cur++；若 G < k，则 cur−−、G += cnt[cur]。每次操作最多挪一两步，而 cur 的总移动量是 O(q + 初值)，整体线性。

G 的增量维护：投票 x → x+1 时只有 x+1 = cur（即 x = cur−1）才让 G 加一；撤票 x → x−1 时只有 x = cur 才让 G 减一。

空间是这题的关键。票数取值在 [0, n]，直接开 sum 数组要 2×10⁷ 个 long long（160MB）+ cnt（80MB），太重。但票数是非负整数且总和 ≤ n ≤ 2×10⁷，「出现过的不同票数」至多 D 种，而 1+2+…+D ≤ n 给出 D ≤ 6326。所以用一张 32768 槽的开地址表存 (票数 → 人数, 编号和)，常驻缓存，快到可以忽略。

0 票那一桶不必逐个插入：人数 = m − 被投过票的人数，编号和 = m(m−1)/2 − Σ(被投过票的编号)。初值 cur 则把表里所有 (票数, 人数) 按票数降序累加，累到 ≥ k 为止。

复杂度 O(n + q + √n) 时间，O(m + 32768) 空间；实测 n = q = 10⁷、m = 2×10⁷ 一组约 1.1s。

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

static ll sd;
static inline ll rnd() { sd = (sd * 13331 + 23333) % 1000000007LL; return sd; }

// 出现的不同票数只有 O(sqrt(n)) 种（1+2+...+D <= 票数总和 <= n），
// 所以 (票数 -> 人数/编号和) 用一张 32768 槽的开地址散列表就够，不必开 2e7 的数组。
static const int HS = 1 << 15, HM = HS - 1;
static int hkey[HS], hcnt[HS];
static ll hsum[HS];

static inline int slotOf(int v, bool create) {
    int h = v & HM;
    while (true) {
        if (hkey[h] == v) return h;
        if (hkey[h] < 0) {
            if (!create) return -1;
            hkey[h] = v; hcnt[h] = 0; hsum[h] = 0;
            return h;
        }
        h = (h + 1) & HM;
    }
}
static inline int getCnt(int v) { int s = slotOf(v, false); return s < 0 ? 0 : hcnt[s]; }
static inline ll getSum(int v) { int s = slotOf(v, false); return s < 0 ? 0 : hsum[s]; }

int main() {
    ll k, b;
    int n, m, q;
    if (scanf("%lld %lld %d %d %d %lld", &sd, &k, &n, &m, &q, &b) != 6) return 0;
    for (int i = 0; i < HS; i++) hkey[i] = -1;

    vector<int> votes(m, 0);
    vector<int> touched;
    touched.reserve(min(n, m));
    for (int i = 0; i < n; i++) {
        int g = (int)(rnd() % m);
        if (votes[g] == 0) touched.push_back(g);
        votes[g]++;
    }
    for (int g : touched) {
        int s = slotOf(votes[g], true);
        hcnt[s]++; hsum[s] += g;
    }
    {   // 0 票的少女是最多的一批，直接算，避免 O(m) 次散列
        ll tot = (ll)m * (m - 1) / 2, positiveSum = 0;
        for (int g : touched) positiveSum += g;
        int s = slotOf(0, true);
        hcnt[s] = m - (int)touched.size();
        hsum[s] = tot - positiveSum;
    }

    // 初始的第 k 大票数
    vector<pair<int, int>> vals;
    for (int i = 0; i < HS; i++) if (hkey[i] >= 0) vals.push_back({hkey[i], hcnt[i]});
    sort(vals.begin(), vals.end(), greater<pair<int, int>>());
    int cur = 0, G = 0;
    for (auto& pv : vals) {
        G += pv.second;
        cur = pv.first;
        if (G >= k) break;
    }

    ll xorsum = 0;
    for (int i = 0; i < q; i++) {
        ll op = rnd();
        int g = (int)(rnd() % m);
        int x = votes[g];
        if (op >= b) {                       // 投票：x -> x+1
            if (x + 1 == cur) G++;           // 她跨过 cur 这条线，才影响 “>= cur” 的人数
            int s = slotOf(x, true); hcnt[s]--; hsum[s] -= g;
            s = slotOf(x + 1, true); hcnt[s]++; hsum[s] += g;
            votes[g] = x + 1;
        } else if (x > 0) {                  // 撤票：x -> x-1（0 票时忽略，但答案照算）
            if (x == cur) G--;
            int s = slotOf(x, true); hcnt[s]--; hsum[s] -= g;
            s = slotOf(x - 1, true); hcnt[s]++; hsum[s] += g;
            votes[g] = x - 1;
        }
        while (G - getCnt(cur) >= k) { G -= getCnt(cur); cur++; }   // 第 k 大上移
        while (G < k && cur > 0) { cur--; G += getCnt(cur); }       // 第 k 大下移
        xorsum ^= getSum(cur);
    }
    printf("%lld\n", xorsum);
    return 0;
}

先枚举所有摆放：把基础形状做 4 次旋转 × 2 次翻转，归一化去重，再在 4×4 内平移。T 共 24 种摆放（4 个朝向 × 每个朝向 6 个位置），L 共 48 种（8 个朝向 × 6）。

记忆化搜索 win(mask, t, l)：能放下某个不冲突的 T（t > 0）或 L（l > 0），并且走完后对手是必败态，则当前必胜；否则必败。

状态上界 2¹⁶ × 4 × 4 = 2²⁰ 个，但可达状态远少于此（掩码必须是若干四格骨牌的并集），数组只需要 1MB，实测全域 16 组 (x, y) 一次跑完不到 0.1s。

全部 16 组的结果（行 = T 数 0..3，列 = L 数 0..3，B 表示 Bob 必胜）：x=0 行 B A B A；x=1 行 A B B A；x=2 行 B B B A；x=3 行 B B B A。可以拿它检查自己的搜索。

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

static vector<int> TP, LP;                 // 所有 T / L 方块的摆放掩码（4x4 -> 16 位）
static int8_t memo[1 << 16][4][4];         // 0 未知，1 必胜，2 必败

static void genShapes(const vector<pair<int, int>>& base, vector<int>& out) {
    set<vector<pair<int, int>>> canon;
    vector<pair<int, int>> cur = base;
    for (int f = 0; f < 2; f++) {
        for (int r = 0; r < 4; r++) {
            int mnr = 9, mnc = 9;
            for (auto& p : cur) { mnr = min(mnr, p.first); mnc = min(mnc, p.second); }
            vector<pair<int, int>> nrm;
            for (auto& p : cur) nrm.push_back({p.first - mnr, p.second - mnc});
            sort(nrm.begin(), nrm.end());
            canon.insert(nrm);
            vector<pair<int, int>> nx;
            for (auto& p : cur) nx.push_back({p.second, -p.first});   // 旋转 90 度
            cur = nx;
        }
        vector<pair<int, int>> nf;
        for (auto& p : cur) nf.push_back({p.first, -p.second});       // 翻转
        cur = nf;
    }
    set<int> masks;
    for (auto& sh : canon) {
        int mr = 0, mc = 0;
        for (auto& p : sh) { mr = max(mr, p.first); mc = max(mc, p.second); }
        for (int dr = 0; dr + mr < 4; dr++)
            for (int dc = 0; dc + mc < 4; dc++) {
                int m = 0;
                for (auto& p : sh) m |= 1 << ((p.first + dr) * 4 + (p.second + dc));
                masks.insert(m);
            }
    }
    out.assign(masks.begin(), masks.end());
}

static bool win(int mask, int t, int l) {
    int8_t& r = memo[mask][t][l];
    if (r) return r == 1;
    bool w = false;
    if (t > 0)
        for (int p : TP) if (!(p & mask)) { if (!win(mask | p, t - 1, l)) { w = true; break; } }
    if (!w && l > 0)
        for (int p : LP) if (!(p & mask)) { if (!win(mask | p, t, l - 1)) { w = true; break; } }
    r = w ? 1 : 2;
    return w;
}

int main() {
    genShapes({{0, 0}, {0, 1}, {0, 2}, {1, 1}}, TP);   // T 形：3 连 + 正中伸出
    genShapes({{0, 0}, {0, 1}, {0, 2}, {1, 0}}, LP);   // L 形：3 连 + 拐角伸出
    int x, y;
    scanf("%d %d", &x, &y);
    printf("%s\n", win(0, x, y) ? "Alice" : "Bob");
    return 0;
}

对每列 c 找自上而下第一颗水果的行号 first[c]（没有就记 n+1），那么这一列从第 1 行起连续 0 的个数是 h_c = first[c] − 1。

宽度为 j 的锚定矩形，高度只能取 min(h_1..h_j)：只要有一列在那行是 1 就不行，而这么取又显然可行。所以答案 = max_j j · min(h_1..h_j)。

前缀 min 单调不增，扫描一次即可。总复杂度 O(n²) 读入 + O(n)，空间 O(n)。

注意这不是「最大全 0 子矩形」的单调栈题：锚定左上角后，宽和高的约束是「一起向右、向下延伸」，直接把二维压成一维前缀最值。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    vector<int> first(n + 1, n + 1);      // 第 c 列自上而下第一颗水果的行号
    for (int r = 1; r <= n; r++)
        for (int c = 1; c <= n; c++) {
            int x;
            scanf("%d", &x);
            if (x == 1 && first[c] == n + 1) first[c] = r;
        }
    int ans = 0, h = n;                   // h = 当前宽度下能取的最大高度
    for (int c = 1; c <= n; c++) {
        h = min(h, first[c] - 1);         // 宽度扩到 c，高度只能取所有列的最小值
        ans = max(ans, c * h);
    }
    printf("%d\n", ans);
    return 0;
}

预处理：把 n+2 行 m 列拉平成一维下标，按每只石像把对应区间标为不可走（区间含石像所在列）。

从 (1, m) 做四连通 BFS，出界或撞封锁格就跳过；能弹出 (n+2, 1) 就输出 YES。

复杂度 O(nm) ≤ 10⁶，空间 O(nm)。

因为激光与石像都不随时间变化，不存在「时间」维度，不需要建分层图或做时序 BFS。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    if (scanf("%d %d", &n, &m) != 2) return 0;
    int R = n + 2, W = m + 1;
    vector<char> block((size_t)(R + 1) * W, 0), vis((size_t)(R + 1) * W, 0);
    auto id = [&](int r, int c) { return (size_t)r * W + c; };
    for (int i = 1; i <= n; i++) {                 // 第 i 只石像在第 i+1 行
        int c; char d;
        scanf("%d %c", &c, &d);
        int r = i + 1;
        if (d == 'L') { for (int j = 1; j <= c; j++) block[id(r, j)] = 1; }
        else          { for (int j = c; j <= m; j++) block[id(r, j)] = 1; }
    }
    vector<int> q;
    q.reserve((size_t)R * m);
    if (!block[id(1, m)]) { vis[id(1, m)] = 1; q.push_back((int)id(1, m)); }
    const int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};
    size_t head = 0;
    bool ok = false;
    while (head < q.size()) {
        int cur = q[head++];
        int r = cur / W, c = cur % W;
        if (r == R && c == 1) { ok = true; break; }
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 1 || nr > R || nc < 1 || nc > m) continue;
            size_t ni = id(nr, nc);
            if (block[ni] || vis[ni]) continue;
            vis[ni] = 1;
            q.push_back((int)ni);
        }
    }
    printf("%s\n", ok ? "YES" : "NO");
    return 0;
}

构造：把 1..n 切成 B 个连续值段，段内降序输出，段间按值递增（先输出小的值段）。设第 b 段长为 s_b。

LIS = B：段内递减，递增子序列每段至多取一个；取每段最后一个元素（各段最小值）恰好递增，所以正好 B。

LDS = max s_b：段内递减给出下界；而一段里的数全都小于后面所有段的数，递减子序列不可能跨段，所以相等。

令各段长度尽量均匀（前 n mod B 段多 1），则 max s_b = ⌈n/B⌉，总和 B + ⌈n/B⌉。

下界：任意排列若 LIS = a、LDS = b，则 ab ≥ n，故 a + b ≥ min_B (B + ⌈n/B⌉)。我们枚举 B 取到这个下界，所以最优。

复杂度 O(n)（枚举 B 是 O(n)，构造也是 O(n)）。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    int bestB = 1, best = INT_MAX;
    for (int B = 1; B <= n; B++) {          // 分成 B 块：块内降序、块间升序 -> LIS=B, LDS=最大块长
        int S = (n + B - 1) / B;
        if (B + S < best) { best = B + S; bestB = B; }
    }
    int q = n / bestB, r = n % bestB, cur = 0;
    for (int b = 0; b < bestB; b++) {
        int s = (b < r) ? q + 1 : q;         // 各块长度尽量均匀
        for (int t = s; t >= 1; t--) printf("%d ", cur + t);   // 块内从大到小
        cur += s;
    }
    printf("\n");
    return 0;
}

重排后第 i 种字符形成长度 c_i 的一个连续段。c_i < 3 的段消不掉；c_i ≥ 3 的段花 1 次操作就能整段清空。

不同字符的段互不干扰：清掉某段不会让别的段合并（同种字符已全部集中在同一段里），也不会产生新的可消段。所以每种字符的花费与收益是独立的：花 1 次操作，收益 c_i（当 c_i ≥ 3）。

k 次操作最大化总收益 → 取数量最大的 k 种（且数量 ≥ 3）字符，答案 = n − 这些数量之和。

复杂度 O(n + 26 log 26)，即 O(n)。注意不是 c mod 3 那套：长度 5 的段也是 1 次清空，样例 1 的 "bbbb" 就是 1 次清掉 4 个。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    char s[100005];
    if (scanf("%d %d %s", &n, &k, s) != 3) return 0;
    int cnt[26] = {0};
    for (int i = 0; i < n; i++) cnt[s[i] - 'a']++;
    sort(cnt, cnt + 26, greater<int>());
    int rem = n;
    for (int i = 0; i < 26 && k > 0; i++)   // 一次操作能吃光一整个长度 >= 3 的段
        if (cnt[i] >= 3) { rem -= cnt[i]; k--; }
    printf("%d\n", rem);
    return 0;
}

下界：设 I = {v : deg(v) ≥ 2}，D = |I|。操作选的 u 必须有儿子，故 u ∈ I；操作后 u 的度数变成 1（离开 I），而 u 的父亲度数增加，最多新增 1 个分叉点。所以 |I| 每次至多减少 1；终态星形（n ≥ 3）|I| = 1，故至少 D − 1 次。

上界（构造）：取 c ∈ I 作花心，把 I \ {c} 里的点按到 c 的距离从小到大依次操作，每次 r = c。轮到 u 时它的父亲已经是 c（路径中间的点的度数 ≥ 2，都在 I 里且已处理完），于是 u 的所有儿子直接挂到 c。全部做完后每个点都挨着 c，得到星，恰好 D − 1 次。

所以答案是 max(0, D − 1)。第一次操作取任意两个不同的分叉点 r、u 即可：r ∈ I 保证 u 的父节点也在 I 里，这一步才会真正让 D 减 1，后续照上面的顺序做完即可。

复杂度 O(n)：只要度数，连图都不用真正建出来。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    if (scanf("%d", &t) != 1) return 0;
    while (t--) {
        int n;
        if (scanf("%d", &n) != 1) return 0;
        vector<int> deg(n + 1, 0);
        for (int i = 0; i < n - 1; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            deg[u]++; deg[v]++;
        }
        vector<int> inner;                       // 度数 >= 2 的点：已有分枝，都是操作对象
        for (int v = 1; v <= n; v++) if (deg[v] >= 2) inner.push_back(v);
        if ((int)inner.size() <= 1) { printf("0\n"); continue; }
        printf("%d\n%d %d\n", (int)inner.size() - 1, inner[0], inner[1]);
    }
    return 0;
}