官方题解 | 巅峰赛29

hopebetter

2026-01-07 14:16:43

发布于：浙江

36阅读

0回复

0点赞

巅峰赛29题解

本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平

题目编号	题目标题	难度
T1	奇核匹配	普及-
T2	连通祭坛的封匣仪式	普及/提高-
T3	风祭城的碑阵刻印	普及+/提高
T4	星塔抄卷	普及+/提高
T5	夜巡城的望炬布防	普及+/提高
T6	月环封印	提高+/省选-

T1

题解

把每个能量写成 二进制分解 的形式

$x=2^{e}\cdot t,\qquad t\ \text{为奇数（或 }x=0\text{）}.$

题目中的操作等价于：

当能量为偶数时，只能“剥去”一个因子 $2$ （ $x\mapsto x/2$ ）；可反复，直到变成奇数；
当能量为奇数时，只能先变成 $2t$ ，但下一步又只能除以 $2$ 回到 $t$ ，于是奇数不能再改变；
能量 $0$ 只能保持为 $0$ 。

于是一个数 $x$ 可达的所有取值恰为

${,2^{e'}\cdot t\mid 0\le e'\le e,} \quad(\text{若 }x>0),\qquad {0}\ (\text{若 }x=0).$

这给出充要条件：

必要性：任意施术后，每件灵具的奇数部分 $t$ （把 $x$ 去掉所有 $2$ 的因子）保持不变； $0$ 也不会变成非 $0$ 。因此，若两箱最终能一致，则两箱中按“奇数部分（或 $0$ ）”分组后的计数必须完全相同。
充分性：若两箱在“奇数部分（或 $0$ ）”的多集计数相同，则把每一组（相同奇数部分 $t$ 的物件）两两配对。设一对的指数分别为 $e_1,e_2$ ，两件都可降到

$2^{\min(e_1,e_2)}\cdot t,$

从而每对都能变成完全相同的数。各组独立配对后，两箱整体多集即相同。

因此，只需把两箱每个数反复除以 $2$ 直到变为奇数（或保留 $0$ ），得到两组“奇数核”多集，比较是否相同即可。

复杂度：每个数最多除 $\log_2(\max x)$ 次，整体

$O!\bigl(n\log \max x\bigr).$

参考代码

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

static i64 core(i64 x) {
    if (x == 0) return 0;
    while ((x & 1LL) == 0) x >>= 1;
    return x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<i64> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    vector<i64> A(n), B(n);
    for (int i = 0; i < n; i++) A[i] = core(a[i]);
    for (int i = 0; i < n; i++) B[i] = core(b[i]);

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    cout << (A == B ? "YES" : "NO") << '\n';
    return 0;
}

T2

题解

把整张图按连通分量拆开。对每个连通分量 $C$ ，记节点数为 $\lvert C\rvert$ ，灵石总和为 $S_C=\sum_{i\in C}a_i$ 。
在这个分量里最多能封成的灵匣数恰为

$\min\bigl(,\lvert C\rvert,\ \lfloor S_C/k\rfloor,\bigr).$

全图答案是各分量答案之和：

$\text{Ans}=\sum_{C}\min\bigl(,\lvert C\rvert,\ \lfloor S_C/k\rfloor,\bigr).$

参考代码

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

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

    int n, m; i64 k;
    cin >> n >> m >> k;

    vector<i64> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<vector<int>> e(n + 1);
    for (int i = 0; i < m; i++) {
        int x, y; cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }

    vector<char> vs(n + 1, 0);
    i64 z = 0;

    for (int s = 1; s <= n; s++) if (!vs[s]) {
        queue<int> q; q.push(s); vs[s] = 1;
        int c = 0; i64 sm = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            c++; sm += a[u];
            for (int w : e[u]) if (!vs[w]) {
                vs[w] = 1; q.push(w);
            }
        }
        z += min<i64>(c, sm / k);
    }

    cout << z << '\n';
    return 0;
}

T3

题解

从全 $0$ 矩阵出发，只能做“整行 $+1$ / 整列 $+1$ ”。记第 $i$ 行被加了 $r_i$ 次、第 $j$ 列被加了 $c_j$ 次，则必须有

$A_{ij}=r_i+c_j.$

因此可达性的充要条件是

$A_{ij}+A_{11}=A_{i1}+A_{1j}\quad(\forall,i,j).$

必要性：上式由 $A_{ij}=r_i+c_j$ 直接得到；
充分性：若恒等式成立，取
$r_i^0=A_{i1}-A_{11},\qquad c_j^0=A_{1j},$
则 $r_i=r_i^0+t,\ c_j=c_j^0-t$ 对任意整数 $t$ 都满足 $r_i+c_j=A_{ij}$ 。在 $A\ge 0$ 的前提下，取 $t=\min_j A_{1j}$ 可保证 $r_i,c_j\ge 0$ ，从而存在一系列行列加法把全 $0$ 变到 $A$ 。

算法：枚举全部 $(i,j)$ 检查恒等式是否成立；若有一处不等则不可达，否则可达。时间 $O(nm)$ 。

参考代码

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

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

    int n, m;
    cin >> n >> m;

    vector<long long> a1(m + 1, 0);       
    long long a11;                            
    long long sum_c0 = 0;                    
    long long R = (long long)4e18;  
    for (int j = 1; j <= m; ++j) {
        cin >> a1[j];
        sum_c0 += a1[j];
        R = min(R, a1[j]);
    }
    a11 = a1[1];

    long long sum_r0 = 0;      
    long long L = 0;     
    for (int i = 2; i <= n; ++i) {
        long long ai1;                     
        cin >> ai1;
        sum_r0 += (ai1 - a11);
        L = max(L, a11 - ai1);

        for (int j = 2; j <= m; ++j) {
            long long x; cin >> x;      
            if (x + a11 != ai1 + a1[j]) {   
                cout << "NO\n";
                return 0;
            }
        }
    }
 
    if (L > R) {   
        cout << "NO\n";
        return 0;
    }
 
    long long S = sum_r0 + sum_c0;
    long long t;
    if (n > m) t = L;
    else if (n < m) t = R;
    else t = L;                  

    long long ans = S + (long long)(n - m) * t;

    cout << "YES\n" << ans << '\n';
    return 0;
}

T4 题解

要求目标串 $t$ 满足：任意相邻长度为 $3$ 的子串里三个字符两两不同。等价于：当我们从左到右填第 $i$ 位字符 $v$ 时，只要保证它与前两位 $w=t_{i-2},u=t_{i-1}$ 都不同，即 $v\ne u$ 且 $v\ne w$ ，那么所有长度为 $3$ 的窗口都会合法。

因此用“末两位”做状态 DP。把字母映射为 $0..25$ 。

设 $dp[w][u]$ 表示已经填到当前位置 $i-1$ ，末两位是 $(w,u)$ 的方案数（且之前都合法）。第 $i$ 位允许的字母由输入决定：若 $s[i]='?'$ 则任意 $0..25$ ，否则只能取固定字母。

转移到新末两位 $(u,v)$ ：必须 $v\ne u$ 、 $v\ne w$ ，且 $v$ 允许。直接枚举 $w$ 会多一层 $26$ 。用列和降维：

对每个 $u$ 先算

$S_u=\sum_{w=0}^{25} dp[w][u].$

那么

$dp2[u][v]=\sum_{w\ne v} dp[w][u] = S_u - dp[v][u],$

同时还要满足 $v\ne u$ ，否则该状态为 $0$ 。另外如果 $v$ 不允许，也为 $0$ 。

初始化：

$n=1$ ：答案是第 $0$ 位可选字母数；
$n\ge 2$ ：先把前两位所有允许的 $(w,u)$ 置为 $1$ ，然后从 $i=2$ 滚动到 $n-1$ 。
最终答案是最后一层所有 $dp[w][u]$ 的总和。全程对模数 $998244353$ 取模，复杂度是 $O(26^2 n)$ 。

参考代码（更短一些）

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

const int A = 26;
const int MOD = 998244353;

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

    int n;
    string s;
    cin >> n >> s;

    int ok0[A] = {0};
    for (int c = 0; c < A; c++) {
        if (s[0] == '?' || s[0] - 'A' == c) ok0[c] = 1;
    }

    if (n == 1) {
        int ans = 0;
        for (int c = 0; c < A; c++) ans = (ans + ok0[c]) % MOD;
        cout << ans << "\n";
        return 0;
    }

    int dp[A][A];
    for (int i = 0; i < A; i++)
        for (int j = 0; j < A; j++)
            dp[i][j] = 0;

    for (int w = 0; w < A; w++) if (ok0[w]) {
        for (int u = 0; u < A; u++) {
            if (s[1] == '?' || s[1] - 'A' == u) dp[w][u] = 1;
        }
    }

    if (n == 2) {
        int ans = 0;
        for (int w = 0; w < A; w++)
            for (int u = 0; u < A; u++)
                ans = (ans + dp[w][u]) % MOD;
        cout << ans << "\n";
        return 0;
    }

    for (int i = 2; i < n; i++) {
        int okv[A] = {0};
        for (int c = 0; c < A; c++) {
            if (s[i] == '?' || s[i] - 'A' == c) okv[c] = 1;
        }

        int su[A] = {0};
        for (int u = 0; u < A; u++) {
            int t = 0;
            for (int w = 0; w < A; w++) {
                t += dp[w][u];
                if (t >= MOD) t -= MOD;
            }
            su[u] = t;
        }

        int ndp[A][A];
        for (int u = 0; u < A; u++)
            for (int v = 0; v < A; v++)
                ndp[u][v] = 0;

        for (int u = 0; u < A; u++) {
            for (int v = 0; v < A; v++) {
                if (!okv[v]) continue;
                if (v == u) continue;
                int val = su[u] - dp[v][u];
                if (val < 0) val += MOD;
                ndp[u][v] = val;
            }
        }

        for (int w = 0; w < A; w++)
            for (int u = 0; u < A; u++)
                dp[w][u] = ndp[w][u];
    }

    int ans = 0;
    for (int w = 0; w < A; w++)
        for (int u = 0; u < A; u++) {
            ans += dp[w][u];
            if (ans >= MOD) ans -= MOD;
        }

    cout << ans << "\n";
    return 0;
}

T5

把“点灯”抽象为树上的最小支配集：选一些点放灯，使得每个点要么自己有灯，要么与某个有灯的点相邻，且灯的数量最少。把树以 $1$ 为根，做树形 DP。

对每个结点 $u$ 定义三种状态：

$f_0(u)$ ：在 $u$ 放灯；
$f_1(u)$ ： $u$ 不放灯，但由某个子结点放灯覆盖（至少有一个子结点处于状态 $0$ ）；
$f_2(u)$ ： $u$ 不放灯，且未被覆盖（等待父结点覆盖）。

设 $v$ 枚举 $u$ 的子结点，有：

$f_0(u)=1+\sum_v \min{f_0(v),f_1(v),f_2(v)}.$

当 $u$ 未被覆盖（交给父亲），则子结点不能处于“也未被覆盖”的状态，否则子树里会出现无人覆盖的点，因此：

$f_2(u)=\sum_v \min{f_0(v),f_1(v)}.$

当 $u$ 由子结点覆盖时，子结点同样只能取 $0/1$ ，并且必须至少一个子结点取 $0$ 。先算基准和

$S=\sum_v \min{f_0(v),f_1(v)}.$

如果在某个子结点上本来就满足 $f_0(v)\le f_1(v)$ ，那么基准选择里已经可能取到 $f_0(v)$ ，这时可以令 $\Delta=0$ 。否则需要强制把某个子结点从 $\min{f_0(v),f_1(v)}$ 改成 $f_0(v)$ ，代价为 $f_0(v)-\min{f_0(v),f_1(v)}$ ，取最小即可：

$\Delta=\min_v \bigl(f_0(v)-\min{f_0(v),f_1(v)}\bigr).$

于是

$f_1(u)=S+\Delta.$

叶子结点没有子结点，不可能被“子结点的灯”覆盖，所以 $f_1(u)=+\infty$ 。

根结点没有父结点，不能处于 $f_2$ ，答案为：

$\min{f_0(1),f_1(1)}.$

整体复杂度 $O(n)$ 。

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

const int INF = 1000000000;

int n;
vector<vector<int>> g;
vector<int> f0, f1, f2;

void dfs(int u, int p) {
    int leaf = 1;
    int s_all = 0, s01 = 0;
    int ok = 0;
    int best = INF;

    for (int v : g[u]) {
        if (v == p) continue;
        leaf = 0;
        dfs(v, u);

        int a = f0[v], b = f1[v], c = f2[v];
        int m_all = min(a, min(b, c));
        int m01 = min(a, b);

        s_all += m_all;
        s01 += m01;

        if (a <= b) ok = 1;
        best = min(best, a - m01);
    }

    f0[u] = 1 + s_all;   // u 放灯
    f2[u] = s01;         // u 不放灯且未覆盖（等父亲）
    if (leaf) {
        f1[u] = INF;     // 叶子不可能由子覆盖
    } else {
        f1[u] = s01 + (ok ? 0 : best); // u 由子覆盖：至少一个子取 0
    }
}

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

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

    f0.assign(n + 1, 0);
    f1.assign(n + 1, 0);
    f2.assign(n + 1, 0);

    dfs(1, 0);
    cout << min(f0[1], f1[1]) << "\n";
    return 0;
}

T6

题意转化

把切开得到的串记为 $s$ ，长度为偶数 $n$ ，只含 '(' 与 ')'。允许：

在环上交换两个位置字符（也可不交换，视为 $l=r$ ）；
再任选切口摊平（等价于对串做任意循环位移）；
问：最多有多少个切口能得到正规括号序列，最大值记为 $g$ ，并输出一组达到 $g$ 的交换位置。

若总平衡不为 $0$ （即 #'(' \ne #')'），则无论怎么交换、怎么切口都不可能成为正规括号序列，直接 $g=0$ 。

关键结论：好切口 = 最小前缀出现次数

对线性串（总平衡为 $0$ ），定义前缀和：

$pre[0]=0,\quad pre[i]=pre[i-1]+(s_i=='('?1:-1).$

设 $mn=\min_{0\le i\le n} pre[i]$ 。经典结论：切口 $k$ （从 $s_{k+1}$ 开始的循环位移）是正规括号序列，当且仅当 $pre[k]=mn$ 。
因此“不交换”的好切口数是

g_0=#{k\mid pre[k]=mn}.

代码先用 rot 把串旋到某个最小前缀处开头得到 $t$ （只为方便分类，最后把下标旋回原串）。

并在 $t$ 上标记：

$B[i]=[pre[i]=mn]$ （原本的好切口）
$C[i]=[pre[i]=mn+1]$
$D[i]=[pre[i]=mn+2]$

一次交换的影响：只会让一段前缀整体 $-2$

交换两处字符，只有交换 '(' 与 ')' 才会改变前缀形态。设选定一段弧 $(l,r]$ （沿环走从 $l$ 到 $r$ ），并要求：

位置 $l$ 上是 '('，位置 $r$ 上是 ')'（这样交换后这段弧对应的前缀会下降）。

交换后效果是：

在弧 $(l,r]$ 内，所有前缀和整体 $-2$ ；
弧外前缀不变。

所以新的全局最小值只可能是 $mn-2$ 、 $mn-1$ 或仍为 $mn$ 。对应三类情况，新的好切口数可以直接数：

情况 1（kind=1）：新最小值变成 $mn-2$

弧内原本 $pre=mn$ 的位置会变成 $mn-2$ ，成为新的最小，因此

g=#(B\text{ 在弧内}).

std 用双倍扫描 + 单调队列，在满足“左端 '('、右端 ')'、弧长 $\le n-1$ ”的弧中最大化弧内 $B$ 的数量。

情况 2（kind=2）：新最小值变成 $mn-1$

为避免出现 $mn-2$ ，弧内必须没有任何 $B$ （否则会压到 $mn-2$ ）。在这种弧里，原本 $mn+1$ 的位置会被压到 $mn-1$ ，因此

g=#(C\text{ 在弧内}).

弧内无 $B$ 等价于弧必须落在“相邻两个 $B$ 之间”的空隙里。std 枚举每个空隙，并在空隙内用 seg 求弧内 $C$ 最大。

情况 3（kind=3）：新最小值仍为 $mn$

弧内不能出现 $mn$ 或 $mn+1$ ，否则最小值会下降，所以弧必须落在连续满足

$pre \ge mn+2$

的块里。这时弧内 $mn+2$ 的位置会被压到 $mn$ ，相当于在原来的 $g_0$ 上增加这些切口：

g=g_0+#(D\text{ 在弧内}).

std 扫描所有 $pre\ge mn+2$ 的连续块，每块用 seg 求弧内 $D$ 最大，取最优。

参考代码

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

void rot(const string &s, string &t, int &sh) {
    int n = (int)s.size();
    vector<int> pre(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + (s[i - 1] == '(' ? 1 : -1);
    }
    int mn = 0, pos = 0;
    for (int i = 0; i <= n; i++) {
        if (pre[i] < mn) {
            mn = pre[i];
            pos = i;
        }
    }
    sh = pos;
    t.assign(n, '(');
    for (int i = 0; i < n; i++) t[i] = s[(pos + i) % n];
}

/*
  在给定前缀下标集合 pos 中，选一段弧 (L, R]：
    左交换字符位置 = L-1 需为 '('
    右交换字符位置 = R   需为 ')'
  最大化弧内 S[u] 之和（u 为前缀下标）。
  返回最大值，并写回 lp,rp（前缀下标）。
*/
int seg(const vector<int> &pos, const vector<int> &S, const string &t, int &lp, int &rp) {
    int n = (int)t.size();
    int L = (int)pos.size();
    if (L == 0) { lp = rp = -1; return 0; }

    vector<int> pf(L + 1, 0);
    for (int i = 0; i < L; i++) pf[i + 1] = pf[i] + S[pos[i]];

    int best = 0, bi = -1, bj = -1;
    int mn = 0x3f3f3f3f, mi = -1;

    for (int j = 0; j < L; j++) {
        int u = pos[j];
        int b = (u - 1 + n) % n;          // 左端点字符位置：u-1
        if (t[b] == '(') {
            int base = pf[j];
            if (base < mn) {
                mn = base;
                mi = j;
            }
        }
        if (t[u] == ')' && mi != -1) {    // 右端点字符位置：u
            int cur = pf[j + 1] - mn;
            if (cur > best) {
                best = cur;
                bi = mi;
                bj = j;
            }
        }
    }
    if (bi == -1) { lp = rp = -1; return 0; }
    lp = pos[bi];
    rp = pos[bj];
    return best;
}

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

    int n;
    string s;
    cin >> n >> s;

    int bal = 0;
    for (char c : s) bal += (c == '(' ? 1 : -1);
    if (bal != 0) {
        cout << 0 << " " << 1 << " " << 1 << "\n";
        return 0;
    }

    string t;
    int sh = 0;
    rot(s, t, sh);
    int N = (int)t.size();

    vector<int> pre(N + 1, 0);
    for (int i = 1; i <= N; i++) pre[i] = pre[i - 1] + (t[i - 1] == '(' ? 1 : -1);
    int mn = 0;
    for (int i = 0; i <= N; i++) mn = min(mn, pre[i]);

    vector<int> B(N, 0), C(N, 0), D(N, 0);
    int g0 = 0;
    for (int i = 0; i < N; i++) {
        if (pre[i] == mn) { B[i] = 1; g0++; }
        if (pre[i] == mn + 1) C[i] = 1;
        if (pre[i] == mn + 2) D[i] = 1;
    }

    int best = g0, kind = 0;
    int L = 0, R = 0; 

  
    vector<int> pb(2 * N + 1, 0);
    for (int i = 0; i < 2 * N; i++) pb[i + 1] = pb[i] + B[i % N];

    deque<pair<int,int> > dq; // (idx, val=pb[idx+1])，val 单调递增
    int L1 = -1, R1 = -1;

    for (int r = 0; r < 2 * N; r++) {
        int lim = r - (N - 1);
        while (!dq.empty() && dq.front().first < lim) dq.pop_front();

        if (t[r % N] == ')' && !dq.empty()) {
            int cur = pb[r + 1] - dq.front().second; // B 在 (l,r] 的个数
            if (cur > best) {
                best = cur;
                kind = 1;
                L1 = dq.front().first % N;
                R1 = r % N;
            }
        }

        if (t[r % N] == '(') {
            int val = pb[r + 1];
            while (!dq.empty() && dq.back().second >= val) dq.pop_back();
            dq.push_back(make_pair(r, val));
        }
    }
    if (kind == 1) { L = L1; R = R1; }
 
    vector<int> posB;
    posB.reserve(g0);
    for (int i = 0; i < N; i++) if (B[i]) posB.push_back(i);

    int k = (int)posB.size();
    for (int i = 0; i < k; i++) {
        int a = posB[i], b = posB[(i + 1) % k];
        vector<int> pos;
        for (int x = (a + 1) % N; x != b; x = (x + 1) % N) pos.push_back(x);
        if (pos.empty()) continue;

        int lp = -1, rp = -1;
        int cur = seg(pos, C, t, lp, rp);
        if (cur > best) {
            best = cur;
            kind = 2;
            L = (lp - 1 + N) % N; // 字符位置
            R = rp;
        }
    }

    // kind=3：最小值仍为 mn（弧内需 pre>=mn+2），最大化弧内 D，并加上 g0
    for (int i = 0; i < N; ) {
        if (pre[i] >= mn + 2) {
            int j = i;
            while (j < N && pre[j] >= mn + 2) j++;
            vector<int> pos;
            for (int x = i; x < j; x++) pos.push_back(x);

            int lp = -1, rp = -1;
            int cur = seg(pos, D, t, lp, rp);
            if (g0 + cur > best) {
                best = g0 + cur;
                kind = 3;
                L = (lp - 1 + N) % N;
                R = rp;
            }
            i = j;
        } else {
            i++;
        }
    }

    if (kind == 0) {
        cout << best << " " << 1 << " " << 1 << "\n";
        return 0;
    }

    int lo = (sh + L) % N + 1;
    int ro = (sh + R) % N + 1;
    cout << best << " " << lo << " " << ro << "\n";
    return 0;
}