GESP C++ 六级必备编程程序（核心模板）

info

对应 GESP 六级知识块：全部六大块（树 / 基于树的编码 / 搜索算法 / 简单动态规划 / 面向对象 / 栈和队列）。

本章目标：把历次 GESP C++ 六级（2023.09–2025.12）编程真题反复考到的题型，提炼成 11 个可背、可套的"核心模板"。考场上两道编程题（各 25 分）基本就是这些模板的组合或微调——背熟它们，编程题拿满 50 分就是水到渠成的事。

真题题型规律（来自历年编程题统计）：

真题场次	编程题 1	编程题 2
2023.09	小杨买饮料（BFS 最短路）	小杨的握手问题
2023.12	闯关游戏（树 + DP）	工作沟通（循环队列）
2024.03	游戏（一维 DP 计数）	好斗的牛（DFS 全排列枚举）
2024.06	计算得分（一维 DP）	二叉树（树的建树 + 子树操作）
2024.09	小杨和整数拆分（DP）	算法学习（贪心 + 约束）
2024.12	树上游走（完全二叉树遍历）	运送物资（哈夫曼编码）
2025.03	树上漫步	环线
2025.06	学习小组	最大因数

知识块到模板的映射

💡 怎么背：本章每个模板都包含「考点 + 完整可编译代码 + 要点」。建议先照抄跑通，再遮住代码默写，最后对着真题名回想用哪个模板。下面 11 个模板按知识块分组。

一、栈和队列（知识块 6）

模板 T1：数组栈 + 括号匹配

考什么：栈的 push/pop/peek、括号匹配（2024.06 选择题用栈做十进制转二进制就是同一套路）。

#include <iostream>
#include <string>
using namespace std;

const int N = 100005;
int stk[N], top = 0;          // top 指向栈顶元素的下一个位置

void push(int x) { stk[top++] = x; }
void pop()       { --top; }
int  peek()      { return stk[top - 1]; }
bool empty()     { return top == 0; }

// 括号匹配：合法返回 true
bool check(const string& s) {
    top = 0;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') push(c);
        else {
            if (empty()) return false;
            char t = peek(); pop();
            if ((c == ')' && t != '(') ||
                (c == ']' && t != '[') ||
                (c == '}' && t != '{')) return false;
        }
    }
    return empty();
}

int main() {
    string s; cin >> s;
    cout << (check(s) ? "YES" : "NO") << endl;
    return 0;
}

要点：

top 约定为"下一个空位"，入栈 stk[top++]=x，出栈 --top，取顶 stk[top-1]。
括号匹配关键：遇到右括号时，栈顶必须是对应的左括号，否则非法；最后栈必须为空。

模板 T2：循环队列（数组实现）

考什么：循环队列的判空、判满、入队、出队（2023.12「工作沟通」就是循环队列调度）。

#include <iostream>
using namespace std;

const int CAP = 1005;
int q[CAP];
int front = 0, rear = 0;       // front 指向队头，rear 指向下一个空位

bool empty() { return front == rear; }
bool full()  { return (rear + 1) % CAP == front; }   // 牺牲一个单元区分空/满
void push(int x) {
    if (full()) return;          // 或根据题目要求报错
    q[rear] = x;
    rear = (rear + 1) % CAP;
}
void pop() {
    if (empty()) return;
    front = (front + 1) % CAP;
}
int  head() { return q[front]; }
int  size() { return (rear - front + CAP) % CAP; }

int main() {
    push(10); push(20); pop();
    cout << head() << " " << size() << endl;   // 20 1
    return 0;
}

要点：

判满公式：(rear + 1) % CAP == front（经典考点，选择题必出）。
下标用取模 % CAP 实现"绕回"，所以叫循环队列。

二、树（知识块 1）

模板 T3：父亲数组建二叉树 + 四种遍历

考什么：由父亲关系建树、先/中/后序、层序（2024.06「二叉树」子树颜色反转、2024.12「树上游走」层序路径，都用这套）。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int N = 100005;
int leftChild[N], rightChild[N];
int root = 1;

// father[i] 表示编号 i+1 的点的父亲（题目通常第 2 行给 n-1 个父亲）
void build(int n, int father[]) {
    for (int i = 1; i <= n; i++) leftChild[i] = rightChild[i] = 0;
    for (int i = 2; i <= n; i++) {
        int f = father[i - 1];
        if (leftChild[f] == 0) leftChild[f] = i;   // 先左后右
        else rightChild[f] = i;
    }
}

void preorder(int u) {                 // 先序：根 左 右
    if (u == 0) return;
    cout << u << " "; preorder(leftChild[u]); preorder(rightChild[u]);
}
void inorder(int u) {                  // 中序：左 根 右
    if (u == 0) return;
    inorder(leftChild[u]); cout << u << " "; inorder(rightChild[u]);
}
void postorder(int u) {                // 后序：左 右 根
    if (u == 0) return;
    postorder(leftChild[u]); postorder(rightChild[u]); cout << u << " ";
}
void levelorder(int u) {               // 层序（BFS）
    queue<int> qu; qu.push(u);
    while (!qu.empty()) {
        int cur = qu.front(); qu.pop();
        cout << cur << " ";
        if (leftChild[cur]) qu.push(leftChild[cur]);
        if (rightChild[cur]) qu.push(rightChild[cur]);
    }
}

// 子树颜色反转（2024.06 真题核心操作）：DFS 遍历子树并取反
void flip(int u, int col[], int ans[]) {
    if (u == 0) return;
    ans[u] = col[u] ^ 1;               // 0 变黑、1 变白
    flip(leftChild[u], col, ans);
    flip(rightChild[u], col, ans);
}

要点：

建树时先占左孩子，再占右孩子，保证结构唯一。
完全二叉树可用数组下标：leftChild[i]=2*i，rightChild[i]=2*i+1（从 1 开始编号）。
子树操作统一用 DFS 遍历实现。

三、基于树的编码（知识块 2）

模板 T4：哈夫曼树（建树 + 带权路径 WPL + 编码）

考什么：哈夫曼树构造（贪心合并最小两个）、WPL、前缀编码（2024.12「运送物资」压缩效率）。

#include <iostream>
#include <queue>
#include <vector>
#include <map>
using namespace std;

struct Node {
    int w, id;                  // id>0 表示叶子，负表示合并节点
    Node *left, *right;
    Node(int w, int id) : w(w), id(id), left(nullptr), right(nullptr) {}
};
struct Cmp {
    bool operator()(Node* a, Node* b) { return a->w > b->w; }   // 小根堆
};

// 返回哈夫曼树根；leaves 为各叶子权值
Node* buildHuffman(const vector<int>& leaves) {
    priority_queue<Node*, vector<Node*>, Cmp> pq;
    for (int w : leaves) pq.push(new Node(w, 1));
    while (pq.size() > 1) {
        Node* a = pq.top(); pq.pop();
        Node* b = pq.top(); pq.pop();
        Node* m = new Node(a->w + b->w, -1);
        m->left = a; m->right = b;
        pq.push(m);
    }
    return pq.top();
}

// 带权路径长度：叶子深度 × 权值求和
int wpl(Node* u, int depth) {
    if (!u) return 0;
    if (u->id > 0) return u->w * depth;
    return wpl(u->left, depth + 1) + wpl(u->right, depth + 1);
}

// 生成编码（左 0 右 1）
void encode(Node* u, string code, map<int,string>& res) {
    if (!u) return;
    if (u->id > 0) { res[u->id] = code; return; }
    encode(u->left,  code + "0", res);
    encode(u->right, code + "1", res);
}

int main() {
    vector<int> leaves = {3, 4, 5, 6};
    Node* root = buildHuffman(leaves);
    cout << "WPL = " << wpl(root, 0) << endl;   // 36
    return 0;
}

要点：

贪心合并：每次取权值最小的两个节点合并，重复到只剩一棵树。
最优 WPL = 所有叶子 权值 × 深度 之和；哈夫曼编码是前缀码（任意编码都不是别的编码的前缀）。
注意：3,4,5,6 的最优 WPL 是 36（不是 43），合并顺序是 3+4=7、5+6=11、7+11=18。

模板 T11：格雷码（镜像反射法 + 二进制互转）

考什么：生成 n 位格雷码、二进制 ↔ 格雷码转换（选择题高频，如「000,001,011,010,110,111,101,100」）。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 生成 n 位格雷码序列
vector<string> grayCode(int n) {
    vector<string> res = {"0", "1"};
    for (int i = 2; i <= n; i++) {
        vector<string> nxt;
        for (string s : res) nxt.push_back("0" + s);          // 原序列前加 0
        for (int j = res.size() - 1; j >= 0; j--)             // 镜像前加 1
            nxt.push_back("1" + res[j]);
        res = nxt;
    }
    return res;
}

// 二进制 b 转格雷码
int toGray(int b) { return b ^ (b >> 1); }
// 格雷码 g 转二进制
int fromGray(int g) {
    int b = g;
    while (g >>= 1) b ^= g;
    return b;
}

int main() {
    for (string s : grayCode(3)) cout << s << " ";   // 8 个 3 位格雷码
    cout << "\n5 的格雷码 = " << toGray(5) << endl;  // 7
    return 0;
}

要点：

核心性质：相邻两个格雷码只有一位不同（含首尾）。
转换公式记死：G = B ^ (B >> 1)；逆向逐位异或还原。

四、搜索算法（知识块 3）

模板 T5：DFS 全排列枚举（好斗的牛）

考什么：数据规模小（N ≤ 9~12）时，用 DFS 枚举所有排列/组合（2024.03「好斗的牛」）。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, ans = 1e9;
vector<int> a, b;            // 每头牛左、右所需空棚数
vector<int> order;           // 当前排列
vector<bool> used;

void dfs(int step) {
    if (step == n) {                          // 排完所有牛
        int sum = 1;                          // 第一头牛占 1 个棚
        for (int i = 1; i < n; i++) {
            // 相邻两牛间距 = max(上头牛右范围, 这头牛左范围)
            sum += max(b[order[i - 1]], a[order[i]]) + 1;
        }
        ans = min(ans, sum);
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            used[i] = true;
            order.push_back(i);
            dfs(step + 1);
            order.pop_back();
            used[i] = false;                 // 回溯
        }
    }
}

int main() {
    cin >> n;
    a.resize(n); b.resize(n); used.assign(n, false);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    dfs(0);
    cout << ans << endl;
    return 0;
}

要点：

DFS 枚举排列三段式：选 i → 标记 → 递归 → 撤销标记（回溯）。
相邻间距公式：max(前牛右范围, 后牛左范围) + 1。

模板 T6：BFS 层序遍历 / 无权最短路

考什么：层序遍历、图的最短路径（2023.09「小杨买饮料」BFS 最短路）。

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int N = 1005;
int g[N][N];          // 邻接矩阵：g[u][v]=1 表示有边
int dist[N];
int n, m;

void bfs(int s) {
    memset(dist, -1, sizeof(dist));
    queue<int> q;
    q.push(s); dist[s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v = 1; v <= n; v++) {
            if (g[u][v] && dist[v] == -1) {     // 有边且未访问
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        g[u][v] = g[v][u] = 1;
    }
    bfs(1);
    cout << dist[n] << endl;     // 1 到 n 的最短路长度
    return 0;
}

要点：

BFS 用队列，第一次访问到某点时的距离就是最短距离（无权图）。
树/图的层序遍历本质就是 BFS。

五、简单动态规划（知识块 4）

模板 T7：一维 DP —— 不相邻元素最大和（打家劫舍）

考什么：状态定义 + 转移方程（2024.03 选择题原样考过，真题「计算得分」也属此类）。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long rob(const vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    if (n == 1) return nums[0];
    vector<long long> dp(n);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    for (int i = 2; i < n; i++)
        dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]);   // 选或不选第 i 个
    return dp[n - 1];
}

要点：

状态：dp[i] = 前 i 个元素中不相邻的最大和。
转移：dp[i] = max(dp[i-1], nums[i] + dp[i-2])——要么不选 i（继承 dp[i-1]），要么选 i（加 dp[i-2]）。
DP 四步：定义状态 → 写转移 → 定边界 → 计算。

模板 T8：一维 DP —— 计数类（游戏）

考什么：统计方案数、对大质数取模（2024.03「游戏」真题）。

#include <iostream>
using namespace std;

const int N = 200005;
const int MOD = 1e9 + 7;
long long f[N * 2];          // 偏移 N，避免下标为负

int main() {
    int n, a, b, c;
    cin >> n >> a >> b >> c;
    // f[i] = 出现数字 i 时的不同操作序列数
    f[N + n] = 1;
    for (int i = n; i > c; i--) {
        f[N + i - a] = (f[N + i - a] + f[N + i]) % MOD;
        f[N + i - b] = (f[N + i - b] + f[N + i]) % MOD;
    }
    long long ans = 0;
    for (int i = 0; i <= c; i++) ans = (ans + f[N + i]) % MOD;
    cout << ans << endl;
    return 0;
}

要点：

计数 DP 常见写法：f[状态] = (f[状态] + f[上一状态]) % MOD。
下标可能为负时，整体加偏移量 N（如 f[N+i] 对应逻辑上的 i）。

模板 T9：0/1 背包（简单背包问题）

考什么：选若干物品使价值最大（考纲明确要求"简单背包"，选择题用背包思路）。

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1005;
int w[N], v[N];
long long dp[N];             // 一维优化

int main() {
    int n, W;
    cin >> n >> W;
    for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
    for (int i = 1; i <= n; i++)
        for (int j = W; j >= w[i]; j--)          // 必须逆序！
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    cout << dp[W] << endl;
    return 0;
}

要点：

一维数组必须逆序遍历容量（保证每个物品只选一次）。
状态：dp[j] = 容量 j 时能获得的最大价值；转移：dp[j] = max(dp[j], dp[j-w[i]] + v[i])。

六、面向对象（知识块 5）

模板 T10：类 + 封装 + 继承 + 多态（虚函数）

考什么：定义类、构造函数、继承、多态（基类指针调派生类方法，2024.09「算法学习」、多次选择题考封装/继承/多态）。

#include <iostream>
using namespace std;

class Shape {                      // 基类
public:
    virtual double area() { return 0; }   // 虚函数 → 多态
    virtual ~Shape() {}                   // 虚析构，安全释放
};

class Rectangle : public Shape {         // 继承
    double w, h;
public:
    Rectangle(double w, double h) : w(w), h(h) {}   // 构造初始化列表
    double area() override { return w * h; }        // 重写
};

class Triangle : public Shape {
    double base, height;
public:
    Triangle(double b, double h) : base(b), height(h) {}
    double area() override { return 0.5 * base * height; }
};

int main() {
    Shape* shapes[2];
    shapes[0] = new Rectangle(4, 5);
    shapes[1] = new Triangle(4, 5);
    for (int i = 0; i < 2; i++) {
        cout << "area = " << shapes[i]->area() << endl;  // 多态：各自算各自
        delete shapes[i];
    }
    return 0;
}

要点：

三大特性：封装（类隐藏内部、提供接口）、继承（class B : public A）、多态（virtual + 基类指针调派生类）。
构造函数用初始化列表 : w(w), h(h) 最规范。
基类析构函数最好声明为 virtual，用基类指针 delete 时能正确释放派生类。

七、考场套用速查表

题目长这样	用哪个模板
给一堆括号 / 进制转换要倒序输出	T1 栈
排队、环形缓冲、任务调度	T2 循环队列
给父亲关系建树、翻转子树、求路径	T3 二叉树
求最短编码、压缩效率、WPL	T4 哈夫曼
n 位格雷码 / 相邻一位不同	T11 格雷码
数据小、求所有排列里的最优	T5 DFS 枚举
最短路、层序、 Flood Fill	T6 BFS
选/不选相邻、最大和	T7 一维 DP
统计方案数、取模	T8 一维 DP
装物品求最大价值	T9 背包
定义类、继承、多态输出	T10 面向对象

🎯 最后叮嘱：两道编程题，第一题往往偏"模拟/搜索/树"，第二题偏"DP"。进场先读题，在速查表里定位模板，把对应代码骨架默写上去，再按题意补输入输出。背完这 11 个，编程题必过。

八、默写自测

自测 1：循环队列判满公式是什么？

答：(rear + 1) % CAP == front。通过"牺牲一个存储单元"来区分队空（front == rear）与队满。选择题几乎必考。

自测 2：哈夫曼树 WPL 怎么算？叶子 3,4,5,6 的最优 WPL 是多少？

答：WPL = Σ(叶子权值 × 深度)。合并顺序 3+4=7、5+6=11、7+11=18，所有叶子深度均为 2，WPL = (3+4+5+6)×2 = 36。注意：36 才是最小带权路径，43 不是最优。

自测 3：0/1 背包一维数组为什么必须逆序遍历容量？

答：逆序保证每个物品在更新时，所依赖的 dp[j-w[i]] 还是"上一轮（没装当前物品）"的值，即每个物品只被考虑一次。若正序则会重复使用同一物品（变成完全背包）。

自测 4：DFS 枚举排列的三段式是哪三步？

答：选当前元素 → 标记已用并递归 → 递归返回后撤销标记（回溯）。对应代码 used[i]=true; order.push_back(i); dfs(step+1); order.pop_back(); used[i]=false;。

自测 5：C++ 多态靠什么实现？基类指针调派生类方法的前提是什么？

答：靠 virtual 虚函数。基类把要重写的方法声明为 virtual，派生类用 override 重写；通过**基类指针（或引用）**指向派生类对象时，调用才会动态绑定到派生类版本。