本篇文章针对 Codeforces 第 777 场比赛（Round 401 (Div. 2)）的赛题进行逐题分析，涵盖 A 至 E 共五道题目。

题目索引

A B C D E

题目详解

A

难度评级：入门级 题目概要：

现有三张卡片，编号分别为 0、1、2。游戏开始时任选一张作为起始卡牌，随后进行 n 次卡片交换操作。交换规则遵循特定模式：首先交换中间位置与左侧位置的卡片，接着交换中间位置与右侧位置的卡片，随后再次交换中间位置与左侧位置的卡片，如此循环。求最终选定卡牌所处的位置编号。

算法分类：模拟、枚举、构造、数学分析 解题思路： 经过仔细观察，可以发现每经过 6 次交换操作后，整个排列状态会恢复到初始情形。这源于交换模式的周期性特征。因此可以直接通过预先计算或直接模拟来得出答案。

B

难度评级：入门级 题目概要：

存在两名玩家 S 与 M，各自持有长度为 N 的数字序列。每一轮对局中，双方依次打出一张数字，数字较小的一方将接受一次惩罚。若双方数字相同，则均不受惩罚。此外，M 可以预先对自己手中的数字进行重新排列。试求 M 最少需要承受的惩罚次数，以及 S 最多可能承受的惩罚次数。

算法分类：数据结构、贪心策略、排序 解题思路： 首先对相关序列进行排序处理。参考实际博弈场景，可归纳出以下行动准则：

1. 若本轮能够获胜，则打出恰好能够获胜的最小数字
2. 若本轮必然失败，则打出当前手中最小的数字

具体证明从略。设 S 的手牌为 s_i，M 的手牌为 m_i。针对第一个问题，只需满足 s_i ≥ m_i 即可打出 m_i；而针对第二个问题，则需满足 s_i > m_i。

C

难度评级：提高级 题目概要：

给定一个 n×m 的矩阵。对于第 j 列，若满足 ∀i ∈ [1,n-1], a_{i,j} ≤ a_{i+1,j}，则称该列为非下降列。现进行 k 次查询，每次查询给出行区间 [L, R]，询问仅保留该行区间后，矩阵中是否存在非下降列。

算法分类：二分查找、数据结构、动态规划、贪心、双指针 解题思路： 本题与最长非下降子串问题存在内在关联。定义 b_{i,j} 表示以 a_{i,j} 作为末尾的最长非下降子串的起始位置索引（注意并非长度值）。通过预计算每一行对应的最小 b 值，可在 O(1) 时间复杂度内完成单次查询。

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

int n, m, k;
int matrix[200010];
int startPos[200010];
int minStart[200010];

int idx(int row, int col) {
    return row * m + col;
}

int main() {
    fill_n(minStart, 200010, INT_MAX);
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &matrix[idx(i, j)]);
        }
    }
    
    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) {
            int current = matrix[idx(i, j)];
            int previous = matrix[idx(i - 1, j)];
            startPos[idx(i, j)] = (current < previous) ? i : startPos[idx(i - 1, j)];
        }
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            minStart[i] = min(minStart[i], startPos[idx(i, j)]);
        }
    }
    
    scanf("%d", &k);
    while (k--) {
        int left, right;
        scanf("%d%d", &left, &right);
        if (minStart[right] <= left) {
            puts("Yes");
        } else {
            puts("No");
        }
    }
    return 0;
}

D

难度评级：提高级 题目概要：

给定 n 个以 '#' 开头的字符串。允许通过删除任意字符串的任意后缀（甚至可删除整个字符串）进行操作，使得所有字符串按字典序升序排列。求满足条件时最少需要删除的字符总数，并输出操作后的字符串序列。

算法分类：二分查找、贪心策略、字符串处理 解题思路： 本题的实质与排序算法并无直接关联。关键点在于：删除后缀操作会导致字符串的字典序变小。据此，字符串 s_n 保持不变即可。而对于 s_i（1 ≤ i ≤ n-1），可采取贪心策略，使其字典序恰好小于或等于 s_{i+1}。实现时应从后向前遍历处理。

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

int n;
string str[500010];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> str[i];
    }
    
    for (int i = n - 1; i >= 1; i--) {
        int cutPos = -1;
        for (int j = 0; j < (int)str[i].size(); j++) {
            if (j == (int)str[i + 1].size()) {
                cutPos = j;
                break;
            }
            if (str[i][j] < str[i + 1][j]) break;
            if (str[i][j] > str[i + 1][j]) {
                cutPos = j;
                break;
            }
        }
        if (cutPos != -1) {
            str[i].erase(cutPos);
        }
    }
    
    for (int i = 1; i <= n; i++) {
        cout << str[i] << "\n";
    }
    return 0;
}

E

难度评级：省选级 题目概要：

已知 n 个环形零件的各项参数：内径、外径及厚度。现需按照以下规则堆叠圆盘零件，构建尽可能高的塔架。

• 零件需水平放置。从侧面观察为长方形，俯视则为环形结构。
• 零件按照从上到下的顺序堆叠，下方零件的外径应大于等于上方零件的外径。
• 上方零件的外径必须严格大于下方零件的内径（否则上方零件会滑落至下方零件的孔洞中）。

算法分类：枚举、排序、动态规划、堆优化 解题思路： 本题与最长上升子序列问题存在相似之处。首先按照外径 b_i 降序排列所有零件，以便进行状态转移。定义 dp_i 表示以第 i 个零件为塔顶时的最大塔高，状态转移方程为：

dp_i = max{dp_j + h_i} (j < i, b_i > a_j)

采用上述动态规划思路的时间复杂度较高，因此引入堆优化策略。将已处理的状态存入大根堆（按高度 h 排序），持续弹出堆顶直至满足 a ≥ b_i 的条件（因为此时堆顶不合法，后续元素必然更不合法），随后更新答案。时间复杂度为 O(n log n)，可顺利通过测试。

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

struct Ring {
    int inner;
    int outer;
    int height;
};

Ring rings[100010];
int n;
int dp[100010];

bool cmp(const Ring& x, const Ring& y) {
    if (x.outer != y.outer) return x.outer > y.outer;
    return x.inner > y.inner;
}

struct State {
    int inner;
    int height;
    
    bool operator<(const State& other) const {
        return height < other.height;
    }
};

priority_queue<State> heap;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &rings[i].inner, &rings[i].outer, &rings[i].height);
    }
    
    sort(rings + 1, rings + n + 1, cmp);
    
    heap.push({0, 0});
    long long answer = 0;
    
    for (int i = 1; i <= n; i++) {
        while (!heap.empty() && heap.top().inner >= rings[i].outer) {
            heap.pop();
        }
        dp[i] = heap.top().height + rings[i].height;
        heap.push({rings[i].inner, dp[i]});
        answer = max(answer, (long long)dp[i]);
    }
    
    printf("%lld\n", answer);
    return 0;
}

综合评价

本套赛题在 Codeforces 平台中属于较低难度范畴，有望在竞赛现场完成全部题目（仅为理论可能）。

延伸阅读： [1] Sima Qian.The Biography of Sun Wu & Wu Qi[A]Records of the Grand Historian[C].Chang'an:Yang Yun,91BCE:1-2