❝

本次六级考试可以看作是过往真题的nano版本，两个题目都可以算作是某次过往真题的轻量级版本，如果还考不过，只能赖自己不好好刷真题

条形蛋糕

题目描述

寒假到了，小杨同学打算找一份兼职，顺便体验一下打工人的生活。

小杨同学给一家蛋糕店发送了一份自己的简历，希望可以在寒假来这里帮忙。店长最近正好遇到了一个难题：店里每天会做一条长条蛋糕，但是不同长度的蛋糕块卖出的价格不同，应该怎么分才能使得总售价最大呢？

有趣的是，店长曾经学习过计算机专业。他最近对动态规划算法很感兴趣，于是打算用这个问题考一考小杨同学。

给定一条长度为  的长条蛋糕和一个价格表。该价格表表示长度为  的蛋糕块价格为 ，其中 。

请你设计蛋糕的分割方案，使得总销售价格最大。

注意：每一块蛋糕的长度必须为整数。

输入格式

第一行一个正整数 ，表示长条蛋糕的总长度。

第二行  个正整数 ，表示不同长度蛋糕块的价格。

输出格式

输出一行一个正整数，表示最大总销售价格。

样例输入 

4  1 5 8 9

样例输出 

10

样例输入 

10  1 5 8 9 10 17 17 20 24 30

样例输出 

30

样例解释

对于样例 ，长度为 、、、 的蛋糕价格分别为 、、、。

总长度为  的蛋糕共有以下  种基本切分方案：

、、、、。

对应的总销售价格分别为 、、、、。

因此最大总销售价格为 。

对于样例 ，长度为  的长条蛋糕，直接作为一整块出售时价格最高，最大总销售价格为 。

数据范围

对于  的数据，满足：，。

题解

这种类型的题目在GESP六级考了应该不下于四次了，如果还不会做，只能赖自己没有好好的刷真题，总结;

这是一个非常板子的划分DP或者你也可以认为是完全背包的问题

长度为  的蛋糕，最后一定会被划分成“某一块长度为  的蛋糕”与“剩余长度为  的蛋糕”。

定义：

:表示总长度恰好为  的蛋糕，能够获得的最大售价。

枚举最后一块切出的长度 ：

• 这一块的售价为 ；
• 剩余长度为 ，其最优售价为 。

因此转移为：

初始时：,最后答案就是 。

这个过程也可以看成完全背包：

• 每种蛋糕长度  是一种物品；
• 价格  是价值；
• 每种物品可以使用任意次；
• 总长度恰好装满 。

时间复杂度：。

参考实现

#include<bits/stdc++.h>usingnamespacestd;using ll = longlong;constint N = 1005;int n;ll p[N], dp[N];intmain(){    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for (int i = 1; i <= n; i++) {cin >> p[i];    }for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {            dp[i] = max(dp[i], dp[i - j] + p[j]);        }    }cout << dp[n] << '\n';return0;}

满二叉树

题目描述

给定一棵包含  个结点的有根二叉树，结点依次以  编号，根结点编号为 。

对于结点 ，其左儿子的编号记为 ，右儿子的编号记为 。特别地，如果左儿子不存在，则 ；如果右儿子不存在，则 。

树中每个结点都对应一棵以该结点为根的子树。请你求出给定有根树的所有  棵子树中，有多少棵子树是满二叉树。

满二叉树是指所有叶子的深度均相同，且除叶子外每个结点均有两个儿子的二叉树。

输入格式

第一行输入一个正整数 ，表示有根二叉树的结点数量。

接下来  行，每行两个非负整数 ，表示结点  的左儿子编号和右儿子编号，整数之间以空格分隔。

输出格式

输出一行一个整数，表示所有子树中满二叉树的数量。

样例输入 

4  2 3  4 0  0 0  0 0

样例输出 

2

样例输入 

3  2 3  0 0  0 0

样例输出 

3

数据范围

对于  的测试点，保证 。

对于所有测试点，保证 。

题解

从叶子向上进行树形 DP。

对每个结点 ，维护：

• ok[u]：以  为根的子树是否为满二叉树；
• h[u]：若该子树是满二叉树，它的高度是多少。

先递归处理左右儿子，再判断当前结点。

若  是叶子结点，也就是左右儿子都不存在，那么它本身就是一棵满二叉树，高度为 。

若  恰好只有一个儿子，那么它不可能是满二叉树。

若  有两个儿子 ，则当前子树是满二叉树，当且仅当：

• 左右子树都是满二叉树；
• 左右子树高度相同。

即：

若成立，则：

每个结点只会被 DFS 一次，处理完一个结点后立刻统计它是否为满二叉树即可。

时间复杂度：。期望得分：100分。

参考实现

#include<bits/stdc++.h>usingnamespacestd;using ll = longlong;constint N = 100005;int n, l[N], r[N], h[N], ans;bool ok[N];voiddfs(int u){if(!u) return ;     dfs(l[u]);     dfs(r[u]);if (!l[u] && !r[u]) {        ok[u] = 1;        h[u] = 0;    } elseif (!l[u] || !r[u]) {        ok[u] = 0;    } elseif (ok[l[u]] && ok[r[u]] && h[l[u]] == h[r[u]]) {        ok[u] = 1;        h[u] = h[l[u]] + 1;    } else {        ok[u] = 0;    }    ans += ok[u];}intmain(){    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for (int i = 1; i <= n; i++) {cin >> l[i] >> r[i];    }    dfs(1);cout << ans << '\n';return0;}