Hello！大家好，我是Zac！今天刚考完六级，感觉这一次放水了，我们简单看一下两道编程题，让后我再讲讲我的思路。

UPDATE 7.1

更新了满二叉树的思路和代码。

第一题

这道题题目大概意思就是：

有一个长度为 n 的蛋糕，有 n 种分法，一块长度为 i 的蛋糕可以卖 p[i] 元，将这块吗蛋糕切成若干块整数长度的蛋糕，求他们的最大利润。

思路

拿到这道题，我们不难看出，这是一道非常典型的完全背包问题，n 就是背包容量，i 是大小，p[i] 就是利润。知道了这些，我们只需套模板即可，注意：1 <= n <= 1000, 1 <= p[i] <= ?（忘了，开long long吧）。

AC Code：

#include <bits/stdc++.h>
using namespace std;
int n, p[1010];
long long dp[1010];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            dp[j] = max(dp[j], dp[j - i] + p[i]);
        }
    }
    cout << dp[n] << endl;
    return 0;
}

第二题

这道题题目大概意思就是：

给定一个n，表示一个二叉树中有n（1 <= n <= 10^5) 个节点，输入n行，每行两个数，表示节点i的左儿子和右儿子，如果为0则表示这个字节点为空。求这个树的满二叉树子树的数量。

思路

对于每个节点 u，需要维护两个信息：

• h[u]：以 u 为根的子树的高度

• f[u]：以 u 为根的子树是否为满二叉树

接下来，我们看判定逻辑：

一、一个节点 u 的子树是满二叉树，当且仅当：

1. 左子树和右子树都是满二叉树（f[l[u]] && f[r[u]]）

2. 左子树和右子树的高度相同（h[l[u]] == h[r[u]]）

二、对于空节点（u == 0）：

• 高度为 0

• 视为满二叉树（方便父节点判断）

三、对于叶子节点（左右孩子都为空）：

• 左子树和右子树都是空树，高度都为 0

• 满足上述两个条件，所以是满二叉树

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
int l[N], r[N];
int h[N];
bool f[N];
int ans;
void dfs(int u) {
    if (!u) {
        h[u] = 0;
        f[u] = true;
        return;
    }
    dfs(l[u]);
    dfs(r[u]);
    if (f[l[u]] && f[r[u]] && h[l[u]] == h[r[u]]) {
        f[u] = true;
        h[u] = h[l[u]] + 1;
        ans++;
    } else {
        f[u] = false;
        h[u] = max(h[l[u]], h[r[u]]) + 1;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
    }
    dfs(1);
    cout << ans << endl;
    return 0;
}

那么以上就是2026年6月 GESP C++ 六级编程题的全部内容了，非常感谢您看到这里，三连关煮，我们下期再见！