官方题解 | 巅峰赛28

hopebetter

2025-12-08 09:56:43

发布于：浙江

197阅读

0回复

0点赞

巅峰赛28题解

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

题目编号	题目标题	难度
T1	Alice的石子合并	普及/提高-
T2	Alice的奇妙爬山之旅	普及/提高-
T3	Alice的神秘二叉树	普及/提高-
T4	Alice的棋盘游戏	普及/提高-
T5	Alice 的回文串	普及+/提高
T6	Alice 的分段游戏	普及+/提高

T1

题解

定义权值

$w_1=b_1,\qquad w_i=\min(a_i,b_i)\ (2\le i\le n-1),\qquad w_n=a_n.$

记

$\text{base}=\sum_{i=1}^n w_i =b_1+\sum_{i=2}^{n-1}\min(a_i,b_i)+a_n.$

则最小总代价为

$\boxed{\ \text{Ans}=\text{base}-\max_{1\le i\le n} w_i\ }.$

下界：若最终幸存的是位置 $s$ ，它不付费；其他位置至少各付 $w_i$ ，故总代价 $\ge \text{base}-w_s$ 。
可达：选使 $w_s$ 最大的 $s$ 为幸存点；对每个 $i\ne s$ ，只主动一次并向更便宜的一侧（端点方向唯一）。左右两侧分别先做“向左”的一批、再做“向右”的一批，能完成所有合并，总代价恰为 $\text{base}-w_s$ 。

综上取最小即 $\text{base}-\max_i w_i$ 。

参考代码

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

int main()
{
    int n;
    cin >> n;
    vector<i64> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    a[1] = 1e18;
    b[n] = 1e18;
    vector<i64> pre(n + 10), suf(n + 10);
    pre[1] = min(a[1], b[1]);
    suf[n] = min(a[n], b[n]);
    for (int i = 2; i <= n; i++) pre[i] = pre[i - 1] + min(a[i], b[i]);
    for (int i = n - 1; i >= 1; i--) suf[i] = suf[i + 1] + min(a[i], b[i]);
    i64 mx = min(suf[2], pre[n - 1]);
    for (int i = 2; i < n; i++) { mx = min(mx, pre[i - 1] + suf[i + 1]); }
    cout << mx << endl;
}

T2

题解

将相邻格子的高度差记为 $d(u,v)=|h_u-h_v|$ ，二分阈值 $T$ 并做判定：把所有边改成 $w_T(u,v)=\mathbf{1}{d(u,v)>T}$ （ $d\le T$ 记 0、 $d>T$ 记 1），在四联通网格上用 0!-!1 BFS 计算从起点到终点所需的“1 边”最少条数 $\mathrm{dist}*T$ ；若 $\mathrm{dist}*T\le K$ 则该 $T$ 可行，否则不可行；利用可行性关于 $T$ 的单调性在区间 $[0,D*{\max}]$ （ $D*{\max}$ 为相邻可通行格的最大高度差）上二分最小可行 $T$ ，若在 $D_{\max}$ 仍不可行则输出 $-1$ ；复杂度 $O(nm\log D_{\max})$ 、空间 $O(nm)$ 。

参考代码

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

const int INF = 0x3f3f3f3f;

int n, m, K;
vector<string> g;                    // 1-based: g[1..n][1..m]
vector<vector<long long> > H;        // 1-based: H[1..n][1..m]
int sx, sy, tx, ty;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

bool inb(int x, int y) {
    return (1 <= x && x <= n && 1 <= y && y <= m);
}
int getid(int x, int y) {
    return (x - 1) * m + y;          // 1..n*m
}
void unpack(int u, int &x, int &y) {
    x = (u - 1) / m + 1;
    y = (u - 1) % m + 1;
}

bool check(long long T) {
    vector<int> dist(n * m + 1, INF);
    deque<int> q;

    int s = getid(sx, sy), t = getid(tx, ty);
    dist[s] = 0;
    q.push_back(s);

    while (!q.empty()) {
        int u = q.front(); q.pop_front();
        if (u == t) break;
        int ux, uy; unpack(u, ux, uy);
        for (int k = 0; k < 4; ++k) {
            int vx = ux + dx[k], vy = uy + dy[k];
            if (!inb(vx, vy)) continue;
            if (g[vx][vy] == '#') continue;
            int v = getid(vx, vy);
            long long dif = llabs(H[ux][uy] - H[vx][vy]);
            int w = (dif > T) ? 1 : 0;
            if (dist[u] + w < dist[v] && dist[u] + w <= K) {
                dist[v] = dist[u] + w;
                if (w == 0) q.push_front(v);
                else q.push_back(v);
            }
        }
    }
    return dist[getid(tx, ty)] <= K;
}

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

    cin >> n >> m >> K;

    g.assign(n + 1, string());
    for (int i = 1; i <= n; ++i) {
        string row; cin >> row;
        g[i] = " " + row;            // 1-based 列
    }

    H.assign(n + 1, vector<long long>(m + 1, 0));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> H[i][j];

    cin >> sx >> sy >> tx >> ty;

    long long hi = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) if (g[i][j] == '.') {
            for (int k = 0; k < 4; ++k) {
                int ni = i + dx[k], nj = j + dy[k];
                if (!inb(ni, nj) || g[ni][nj] != '.') continue;
                long long dif = llabs(H[i][j] - H[ni][nj]);
                if (dif > hi) hi = dif;
            }
        }

    if (!check(hi)) {                // 障碍切断
        cout << -1 << '\n';
        return 0;
    }

    long long lo = 0;
    while (lo < hi) {
        long long mid = (lo + hi) >> 1;
        if (check(mid)) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << '\n';
    return 0;
}

T3

题解

关键性质

对任意中序子区间 [L,R]，该子树的根一定是“在层序序列里最先出现（下标最小）且键值落在 [L,R] 的那个结点”。
因为层序总是先访问根，再访问整棵左子树与整棵右子树。

等价转化

把每个键 x 的层序出现次序记作 rank[x]（越小越靠前）。
将中序位置 i 赋权 prio[i]=rank[in[i]]。
在位置序 i=1..n 上构造一棵最小堆笛卡尔树：

这棵树的中序遍历顺序恰是 1..n（对应输入的中序位置）；
最小堆：每个结点的 prio 小于其左右孩子的 prio；
因此在任何区间 [L,R] 内，prio 最小者就是根——与上面的“层序最早者为根”完全一致。

构造好后，把结点下标 i 再映射回键值 in[i]，对这棵树做先序输出即可。

参考代码

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

void dfs(int i, vector<int>& L, vector<int>& R, vector<i64>& v)
{
    cout << v[i] << ' ';
    if (L[i])
    {
        dfs(L[i], L, R, v);
    }
    if (R[i])
    {
        dfs(R[i], L, R, v);
    }
}


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

    int n;
    cin >> n;
    vector<i64> in(n + 1), level(n + 1);
    for (int i = 1; i <= n; i++) cin >> in[i];
    for (int i = 1; i <= n; i++) cin >> level[i];
    map<i64, int> mp;
    for (int i = 1; i <= n; i++)
        mp[level[i]] = i;
    vector<int> mid(n + 1);
    for (int i = 1; i <= n; i++)
    {
        mid[i] = mp[in[i]];
    }
    vector<int> L(n + 1), R(n + 1);

    stack<int> st;
    for (int i = 1; i <= n; i++)
    {
        int l = 0;;
        while (!st.empty() && mid[st.top()] > mid[i])
        {
            l = st.top();
            st.pop();
        }
        L[i] = l;
        if (!st.empty()) R[st.top()] = i;
        st.push(i);
    }
    int rt = -1;
    for(int i = 1;  i <= n ;i ++){
        if(in[i] == level[1] ) rt = i;
    }
    
    dfs(rt, L, R, in);
}

T4

题解

把所有可通行格（含 S）抽成一个最多 20 点的无向图（四联通、屏蔽 #）。规则“离开格子即封冻”等价于：棋子始终走在未封冻顶点上，每走一步把当前顶点加入“封冻集合”。因此状态可表示为 (mask, u)：mask 是已封冻顶点集合（位集），u 是当前所在顶点。转移：可去任一相邻未封冻顶点 v，新状态为 (mask ∪ {u}, v)。这是标准的有向无环图上的对弈 DP（必败/必胜）：

记 win[mask][u]：从该状态当前手是否必胜。
若存在某个邻居 v 使 win[mask ∪ {u}][v] 为假，则当前为真（因为能把对手送进必败）。
否则为假。
起始状态为 (0, S)。若起始为真，枚举四邻中任意一个能把对手送进必败的 v，输出 S -> v 作为首回合必胜走法；否则输出 LOSE。

参考实现

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

int n, m;
vector<string> board;                 // 1-based: board[1..n][1..m]
vector<vector<int> > id_of;          // 1-based: 网格 -> 节点编号（-1 表示不可用）
vector<pair<int,int> > pos;          // 节点编号 -> (x,y)
vector<vector<int> > adj;            // 邻接表（按节点编号）
int V = 0;                           // 可用点数（含 S）
int s_id = -1;                       // 起点编号

// 记忆化：win[mask][u]，用一维数组存：mask*V + u
vector<char> memo;                   // -1 未算，0 必败，1 必胜

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

bool inside(int x, int y) { return 1 <= x && x <= n && 1 <= y && y <= m; }

char solve(int mask, int u) {
    int idx = mask * V + u;
    if (memo[idx] != -1) return memo[idx];

    // 尝试任意一步：去到未封冻邻居 v，且离开 u 后把 u 加入封冻集合
    for (int v : adj[u]) {
        if ((mask >> v) & 1) continue;           // v 已封冻，不能去
        int nmask = mask | (1 << u);             // 离开 u，u 被封冻
        if (!solve(nmask, v))                    // 若能把对手送入必败
            return memo[idx] = 1;                // 当前为必胜
    }
    return memo[idx] = 0;                        // 无法找到使对手必败的走法 -> 当前必败
}

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

    cin >> n >> m;
    board.assign(n + 1, string());
    for (int i = 1; i <= n; ++i) {
        string row; cin >> row;
        board[i] = " " + row;                    // 列 1-based
    }

    id_of.assign(n + 1, vector<int>(m + 1, -1));
    pos.clear();

    // 编号：把可用格（'.' 或 'S'）编号为 0..V-1，并记录 S 的编号
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            if (board[i][j] == '.' || board[i][j] == 'S') {
                id_of[i][j] = V++;
                pos.push_back(make_pair(i, j));
                if (board[i][j] == 'S') s_id = id_of[i][j];
            }
        }

    // 无可走步（S 周围全阻或孤点）处理会由 DP 自然给出 LOSE
    adj.assign(V, vector<int>());
 
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            if (id_of[i][j] == -1) continue;
            int u = id_of[i][j];
            for (int k = 0; k < 4; ++k) {
                int ni = i + dx[k], nj = j + dy[k];
                if (!inside(ni, nj)) continue;
                if (id_of[ni][nj] == -1) continue;
                int v = id_of[ni][nj];
                adj[u].push_back(v);
            }
        }
 
    int total_states = (1 << V) * V;
    memo.assign(total_states, -1);
 
    int start_mask = 0;
    char start_win = solve(start_mask, s_id);

    if (!start_win) {
        cout << "LOSE\n";
        return 0;
    }
 
    for (int v : adj[s_id]) {
        if ((start_mask >> v) & 1) continue;
        int nmask = start_mask | (1 << s_id);
        if (!solve(nmask, v)) {
            pair<int,int> S = pos[s_id];
            pair<int,int> T = pos[v];
            cout << "WIN\n";
            cout << S.first << " " << S.second << " " << T.first << " " << T.second << "\n";
            return 0;
        }
    }
 
    cout << "LOSE\n";
    return 0;
}

T5

题解

设 dp[l][r] 表示把子串 s[l..r]（闭区间，0-based）全部删除所需的最少步数。转移：

先手段：把 s[l] 单独删掉，再处理右侧
$dp[l][r] \le 1 + dp[l+1][r].$
更优的可能：若存在 p∈(l..r] 且 s[p]=s[l]，可以把 s[l] 与 s[p] 放在同一次删除里（那次删除是以这两个相同字符为两端的回文子串；在此之前需先把中间段 s[l+1..p-1] 全清空）。于是
$dp[l][r]\le dp[l+1][p-1]+dp[p+1][r].$

边界：dp[i][i]=1；若整段本身是回文，显然 dp[l][r]=1。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N = 610;
int dp[N][N];
int main(){
    string a;
    cin>>a;
    int n = a.size();
    a = " "+a;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dp[i][j]=1e9;
        }
    }
    for(int i=1;i<=n;i++){
        dp[i][i]=1;
        if(i+1<=n){
            if(a[i]!=a[i+1])dp[i][i+1]=2;
            else dp[i][i+1]=1;
        }
    }
    for(int len=3;len<=n;len++){
        for(int l=1;l+len-1<=n;l++){
            int r = l+len-1;
            if(a[l]==a[r])dp[l][r]=dp[l+1][r-1];
            for(int k=l;k<=r-1;k++){
                dp[l][r]=min(dp[l][k]+dp[k+1][r],dp[l][r]);
            }
        }
    }
    cout<<dp[1][n];
    return 0;
}

T6

题解

设

$f[t][i] ;=; \min_{0 \le j < i}\Big( f[t-1][j] + \mathrm{cost}(j+1,, i) \Big),$

表示把前 $i$ 个元素切成恰好 $t$ 段的最小代价。最终答案为 $f[k][n]$ 。

其中

$\mathrm{cost}(L,R) = \sum_x \binom{c_x(L,R)}{2},$

等价于区间内所有相等下标对 $(p,q)$ 的个数（ $L \le p < q \le R,\ a_p=a_q$ ）。

代价维护

用一个可移动窗口 $[L,R]$ 维护当前区间代价 curCost，配一个频次数组 cnt[v]：

加入值 $v$ ：curCost += cnt[v]，然后 cnt[v]++。
删除值 $v$ ：先 cnt[v]--，然后 curCost -= cnt[v]。

这样把窗口从 $[L,R]$ 调整到任意 $[L',R']$ 的过程中，总代价可在摊还 $O(1)$ 时间更新。

分治优化

对固定的 $t$ ，需要求解

$f[t][i] ;=; \min_{j<i},{, f[t-1][j] + \mathrm{cost}(j+1,, i) ,}.$

记 $w(j,i)=\mathrm{cost}(j+1,i)$ 。该代价满足四边形不等式/Monge 性，故最优断点具有单调性：

$\operatorname{opt}[t][i]\ \le\ \operatorname{opt}[t][i+1].$

据此用分治优化：在区间 $[L,R]$ 的中点 $m$ 仅在 $[optL,,optR]$ 扫 $j$ ，递归到两侧时分别缩小搜索区间。
配合“可移动窗口”，在枚举 $j$ 的过程中把窗口依次从 $[j+1,m]$ 挪到下一个候选，保证整体效率。

初始层与边界

$t=1$ ：直接线性扩展窗口得到 $\mathrm{cost}(1,i)$ 作为 $f[1][i]$ 。
不可行状态： $i<t$ 无法切成 $t$ 段，置为 $+\infty$ 。
基础： $f[0][0]=0$ ，其余 $f[0][i>0]=+\infty$ 。

复杂度

$\text{时间 } O(k,n\log n), \qquad \text{空间 } O(n+\max a_i).$

参考代码

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

static const int MAXN = 200000 + 5;
static const int MAXA = 200000 + 5;
const long long INF = (long long)4e18;

int n, K;
int a[MAXN];

// 频次数组与当前窗口 [curL, curR] 的代价
long long curCost;
int cnt[MAXA];
int curL, curR;

inline void reset_window() {
    memset(cnt, 0, sizeof(int) * (MAXA));
    curCost = 0;
    curL = 1; curR = 0; // 空窗口
}

inline void add_pos(int pos) {
    int v = a[pos];
    curCost += cnt[v];
    ++cnt[v];
}
inline void remove_pos(int pos) {
    int v = a[pos];
    --cnt[v];
    curCost -= cnt[v];
}

inline void move_to(int L, int R) {
    while (curL > L) add_pos(--curL);
    while (curR < R) add_pos(++curR);
    while (curL < L) remove_pos(curL++);
    while (curR > R) remove_pos(curR--);
}

// DP 数组：prev 为 t-1 段，cur 为 t 段
long long dp_prev[MAXN], dp_cur[MAXN];

void solve_layer(int t, int L, int R, int optL, int optR) {
    if (L > R) return;
    int mid = (L + R) >> 1;

    // j 至少为 t-1，保证能切出 t 段；j < mid
    int start = max(t - 1, optL);
    int finish = min(mid - 1, optR);

    long long bestVal = INF;
    int bestK = -1;

    for (int j = start; j <= finish; ++j) {
        move_to(j + 1, mid); // 让窗口变成 [j+1, mid]
        long long cand = dp_prev[j] + curCost;
        if (cand < bestVal) {
            bestVal = cand;
            bestK = j;
        }
    }
    dp_cur[mid] = bestVal;

    if (L == R) return;
    // 单调性：opt(L..mid) 不超过 bestK；opt(mid..R) 不小于 bestK
    solve_layer(t, L, mid - 1, optL, (bestK == -1 ? start : bestK));
    solve_layer(t, mid + 1, R, (bestK == -1 ? finish : bestK), optR);
}

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

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

    // t = 0：只允许切 0 段 -> 只有 i=0 有意义
    dp_prev[0] = 0;
    for (int i = 1; i <= n; ++i) dp_prev[i] = INF;

    // 先把 t=1 的答案线性预处理：cost(1, i)
    reset_window();
    for (int i = 1; i <= n; ++i) {
        move_to(1, i);
        dp_cur[i] = curCost;
    }
    dp_cur[0] = INF;
    for (int i = 0; i <= n; ++i) dp_prev[i] = dp_cur[i];

    // 继续做 t = 2..K 的分治优化
    for (int t = 2; t <= K; ++t) {
        // 对于 i < t 不可能划成 t 段，置 INF
        for (int i = 0; i < t; ++i) dp_cur[i] = INF;
        reset_window();
        // 经典分治：答案定义在区间 [t..n]，最优断点落在 [t-1..i-1]
        solve_layer(t, t, n, t - 1, n - 1);
        // 滚动
        for (int i = 0; i <= n; ++i) dp_prev[i] = dp_cur[i];
    }

    cout << dp_prev[n] << '\n';
    return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 7

༺ཌༀཉི༒白·羊༒༃ༀད༻
前排，笑点解析：T1code没放c++代码框

6天前来自上海
1
- Arthur2013
  回复༺ཌༀཉི༒白·羊༒༃ༀད༻
  这官方题解越看越像AI写的。
  
  昨天来自上海
  1
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复Arthur2013
  这种注释不是AI
  
  19小时前来自上海
  1
- Arthur2013
  回复༺ཌༀཉི༒白·羊༒༃ༀད༻
  反正我看着像
  
  13小时前来自上海
  0
Lost
byd 你不会评级建议别评级了，你搬 CF868F 这么经典的题就算了还把莫队维护决策单调性 dp 评绿是几个意思

6天前来自山东
1
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复Lost
  zc
  
  6天前来自上海
  0
- cjdstttttt
  回复Lost
  好评兄弟好评
  
  6天前来自广东
  0
- 宋雨琦的狗
  回复Lost
  弱弱的问一句，这是评难了还是评简单了？
  
  5天前来自天津
  0
AC是最好的
热知识：T4直接输出LOSE能拿52分

12小时前来自福建
0
Xylophone
原来官方你记得有加精这个项目啊

4天前来自广东
0
Xylophone
袜，四边形不等式评绿的也来了

4天前来自广东
0
ask_silently
题解一股 AI 味，T6 马蜂明显跟前面不同，自己没有正确的对题目难度进行评价，T5 原题：https://codeforces.com/problemset/problem/607/B，T6 原题：https://codeforces.com/problemset/problem/868/F。

6天前来自河南
0
- Xylophone
  回复ask_silently
  原题界也有自己的盒武器
  
  4天前来自广东
  0
- ༺ཌༀཉི༒白·羊༒༃ༀད༻
  回复ask_silently
  @AC君
  
  19小时前来自上海
  0
cjdstttttt
合味道

依旧梦到什么定什么

6天前来自广东
0