GESP 6级
P10250 [GESP样题 六级] 下楼梯¶
提示1-看最后一步
看全部数据范围，\(n\le 60\)。
我先不管前面怎么走，只看最后一步：它只能走 1、2 或 3 个台阶。
提示2-把三种情况相加
最后一步走几级确定后，前面就是一个更小的同类问题。
我把三种情况的方案数相加，得到 \(\operatorname{dp}_{i}\)。
\(\operatorname{dp}_{0}=1\)：什么也不走，也有一种方案。
答案用 long long。
比如正在算第i级，先试最后一步走j级。前面已有的方案接上这一步：
代码-满分
时间 \(O(n)\)，空间 \(O(n)\)。
P10262 [GESP样题 六级] 亲朋数¶
提示1-先想暴力
看全部数据范围，\(L\le 10^{6}\)，\(2\le p\le 128\)。
我先想枚举每个子串，但百万长度肯定做不完。
再看 \(p\) 只有 128，我会试着按余数分组，而不是保存子串的数值。
提示2-按余数分组
我把以同一位置结尾的子串放在一起看：新子串要么只有当前数字，要么是在旧子串后面接上这个数字。
旧余数为 \(r\)，接上 \(x\) 后，新余数就是 \((10r+x)\bmod p\)。
提示3-只留上一层
转移只用到上一位置，我就不存整张表，只留 \(\operatorname{last}\)、\(\operatorname{cur}\) 两层。
每层把余数为 0 的数量加入答案。
子串数量最多为 \(\frac{L(L+1)}{2}\)，所以答案用 long long。
读到数字x后，先清空cur，再放入只有当前一位的子串。下面才把上一轮所有余数接上x：
代码-满分-滚动数组
时间 \(O(Lp)\)，空间 \(O(p)\)，不必保存百万行状态。
#include <bits/stdc++.h>
using namespace std;
const int M = 130;
int last[M], cur[M];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int p;
string s;
cin >> p >> s;
// 我只用到上一层的余数统计，不需要保存整张二维表。
long long ans = 0;
for (char c : s) {
int x = c - '0';
fill(cur, cur + p, 0);
cur[x % p] = 1;
for (int r = 0; r < p; r++) {
cur[(r * 10 + x) % p] += last[r];
}
ans += cur[0];
for (int r = 0; r < p; r++) last[r] = cur[r];
}
cout << ans;
return 0;
}
B3873 [GESP202309 六级] 小杨买饮料¶
提示1-小范围枚举
40分做法，\(n\le 20\)，\(L\)、容量\(\le 100\)。
70分做法，容量\(\le 100\)。
看全部数据范围，\(n\le 500\)，\(L\le 2000\)，价格、容量\(\le 10^{6}\)。
每瓶只有买或不买两种选择，我会先用子集枚举解决 \(n\le 20\) 的情况，再想大范围怎么合并状态。
提示2-容量超过 L 还需要区分吗
容量太大，不能按所有容量开数组。
我注意到：只要达到 \(L\)，买到多少都算够了。
于是把超过 \(L\) 的容量都记成 \(L\)，\(\operatorname{dp}_{j}\) 只记录达到这个容量的最小费用。
提示3-每瓶只能买一次
我最怕同一瓶被算两次，所以容量从大到小更新。
\(\operatorname{dp}_{0}=0\)，其余状态先设为不可达。
这里的j从L倒着枚举，volume和cost是当前瓶的容量、价格。超过目标的容量统一落到L：
代码-40分-枚举子集
时间 \(O(n2^{n})\)，空间 \(O(n)\)，只适用于 \(n\le 20\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 25;
const long long INF = 1LL << 60;
int cost[N], volume[N];
int main() {
int n, target;
cin >> n >> target;
for (int i = 0; i < n; i++) cin >> cost[i] >> volume[i];
long long ans = INF;
// 每瓶只有买和不买两种选择，我先把所有集合试一遍。
for (int mask = 0; mask < (1 << n); mask++) {
long long sum = 0, money = 0;
for (int i = 0; i < n; i++) {
if ((mask >> i) & 1) {
sum += volume[i];
money += cost[i];
}
}
if (sum >= target) ans = min(ans, money);
}
if (ans == INF) cout << "no solution";
else cout << ans;
return 0;
}
代码-满分-容量封顶的 01 背包
时间 \(O(nL)\)，空间 \(O(L)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
const long long INF = 1LL << 60;
long long dp[N];
int main() {
int n, target;
cin >> n >> target;
fill(dp, dp + target + 1, INF);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
int cost, volume;
cin >> cost >> volume;
// 达到目标后就不用区分容量；我倒序更新，避免一瓶买两次。
for (int j = target; j >= 0; j--) {
if (dp[j] == INF) continue;
int nxt = min(target, j + volume);
dp[nxt] = min(dp[nxt], dp[j] + cost);
}
}
if (dp[target] == INF) cout << "no solution";
else cout << dp[target];
return 0;
}
B3874 [GESP202309 六级] 小杨的握手问题¶
提示1-先写两层循环
30分做法，\(n\le 100\)。
看全部数据范围，\(n\le 3\times 10^{5}\)。
我先把握手翻译成一句话：前面的人学号更小，就计一次。
这样两层循环就能解决小范围。
提示2-归并时成批统计
逐对比较太慢，我就想：能不能一次数出一批？把两段按降序排好后，左边当前数若更小，左边剩下的数就全都更小。
归并时一次加上这批数量，答案用 long long。
归并时两段都已降序。若左边当前数还小于右边当前数，左段从i到mid的数就都能与它握手：
代码-30分-两层循环
时间 \(O(n^{2})\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int a[N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
long long ans = 0;
// 我先按入场顺序逐对检查，确认什么时候发生握手。
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (a[i] < a[j]) ans++;
}
}
cout << ans;
return 0;
}
代码-满分-归并统计
时间 \(O(n\log n)\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 300005;
int a[N], tmp[N];
long long ans;
void merge_sort(int l, int r) {
if (l >= r) return;
int mid = (l + r) / 2;
merge_sort(l, mid);
merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r) {
if (a[i] < a[j]) {
// 左段已经降序排好，我发现剩下的数都更小，可以一起计数。
ans += mid - i + 1;
tmp[k++] = a[j++];
} else {
tmp[k++] = a[i++];
}
}
while (i <= mid) tmp[k++] = a[i++];
while (j <= r) tmp[k++] = a[j++];
for (int i = l; i <= r; i++) a[i] = tmp[i];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
merge_sort(1, n);
cout << ans;
return 0;
}
P10108 [GESP202312 六级] 闯关游戏¶
提示1-先看只有一条通道
20分做法，\(m=1\)。
40分做法，\(n\le 20\)、\(m\le 2\)。
看全部数据范围，\(n\le 10^{4}\)、\(m\le 100\)。
只有一条通道时，我直接按唯一的路线走。
有多条通道时，到同一关可能走出不同分数，我只保留最高的那个。
提示2-分数可能为负
我看到分数可能是负的，就不能把每个状态都初始化成 0：那等于凭空多了一条没走过的路。
\(\operatorname{dp}_{0}=0\)，其余设为负无穷。
离开 \(i\) 时加 \(b_{i}\)，到达或越过 \(n\) 都记为通关。
处理关卡i时，先确认dp[i]可达。选择第j条通道，得分记在离开的关卡上：
代码-满分
时间 \(O(nm)\)，空间 \(O(n+m)\)。同一套转移即可覆盖所有范围。
#include <bits/stdc++.h>
using namespace std;
const int N = 10005, M = 105;
const long long NEG = -(1LL << 60);
int a[M], b[N];
long long dp[N];
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
// 分数可能为负，我不能让没到过的关卡凭空拥有0分。
fill(dp, dp + n + 1, NEG);
dp[0] = 0;
for (int i = 0; i < n; i++) {
if (dp[i] == NEG) continue;
for (int j = 0; j < m; j++) {
int nxt = min(n, i + a[j]);
dp[nxt] = max(dp[nxt], dp[i] + b[i]);
}
}
cout << dp[n];
return 0;
}
P10109 [GESP202312 六级] 工作沟通¶
提示1-沿父亲往上找
50分做法，\(n\le 50\)。
看全部数据范围，\(n\le 300\)，\(q\le 100\)。
我先列出谁能管理一个员工：他自己、父亲、父亲的父亲……沿父亲链就能找全。
规模只有 300，不必急着用复杂算法。
提示2-统计共同祖先
每个参与者都给自己的祖先加一次计数，我就能找出所有共同祖先，再取编号最大的。
我会再读一遍输出要求：这里要最大编号，不能直接当成最近公共祖先。
对于本次合作的一个员工u，我沿父亲链逐个计数，直到根的父亲-1。每次询问前清空cnt：
代码-满分-统计祖先
每次询问 \(O(mn)\)，空间 \(O(n)\)。规模较小，无需复杂的倍增算法。
#include <bits/stdc++.h>
using namespace std;
const int N = 305;
int parent[N], cnt[N];
int main() {
int n, q;
cin >> n;
parent[0] = -1;
for (int i = 1; i < n; i++) cin >> parent[i];
cin >> q;
for (int t = 0; t < q; t++) {
int m;
cin >> m;
fill(cnt, cnt + n, 0);
for (int i = 0; i < m; i++) {
int u;
cin >> u;
// 我把这个员工能找到的领导全部记一次，包括他自己。
while (u != -1) {
cnt[u]++;
u = parent[u];
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
if (cnt[i] == m) ans = i;
}
if (t > 0) cout << '\n';
cout << ans;
}
return 0;
}
P10376 [GESP202403 六级] 游戏¶
提示1-终点可以合并
20分做法，\(a=b=c=1\)，\(n\le 30\)。
40分做法，\(c=1\)，\(n\le 1000\)。
看全部数据范围，\(n\le 2\times 10^{5}\)。
我先看游戏什么时候结束：减到不大于 \(c\) 就停。
既然后面都不能再操作，这些终点可以合并到一个状态 \(\operatorname{dp}_{c}\)。
提示2-终点不再转移
数值只会变小，我就从 \(n\) 往下算，只处理 \(i>c\)。
两种操作分别转移到 \(\max(c,i-a)\)、\(\max(c,i-b)\)。
这里我会特别检查 \(a=b\)：题目仍把它们算作两种操作。
\(n=c\) 时，不操作也是一种方案。
在i大于c的倒序循环里，两种操作分别累加。你看，哪怕a和b相同，也要加两次：
代码-满分
时间 \(O(n)\)，空间 \(O(n)\)，每次相加后取模。
#include <bits/stdc++.h>
using namespace std;
const int N = 200005, MOD = 1000000007;
int dp[N];
int main() {
int n, a, b, c;
cin >> n >> a >> b >> c;
dp[n] = 1;
// 我让转移停在c，不能从终点继续走，否则会多算操作。
for (int i = n; i > c; i--) {
int x = max(c, i - a);
int y = max(c, i - b);
dp[x] = (dp[x] + dp[i]) % MOD;
dp[y] = (dp[y] + dp[i]) % MOD;
}
cout << dp[c];
return 0;
}
P10377 [GESP202403 六级] 好斗的牛¶
提示1-数据很小
20分做法，\(n=2\)。
另外20分做法，\(n=3\)。
80分做法，\(n\le 8\)。
看全部数据范围，\(n\le 9\)，攻击范围\(\le 1000\)。
看到最多只有 9 头牛，我会先考虑枚举排列。
先定左右顺序，再想这个顺序下怎么放得最紧。
提示2-固定顺序后怎么放
相邻两头牛不能互相攻击，我分别看左牛的右范围和右牛的左范围，距离就至少是 \(\max(b_u,a_v)+1\)。
更远的牛只会离得更远，所以检查相邻牛就够了。
首尾外面不用留空棚。
正在把牛i放到第pos个位置时，order[pos-1]是它左边的牛。已有长度为length，这一步只增加两牛间的距离：
代码-20分-两头牛
只适用于 \(n=2\)，比较两种左右顺序。
代码-满分-枚举排列
时间 \(O(n\cdot n!)\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 15, INF = 1000000000;
int a[N], b[N], order[N];
bool used[N];
int n, ans = INF;
void dfs(int pos, int length) {
if (pos > n) {
ans = min(ans, length);
return;
}
for (int i = 1; i <= n; i++) {
if (used[i]) continue;
int nxt = length;
// 顺序定好后，我只给相邻牛留出刚好安全的距离。
if (pos > 1) nxt += max(b[order[pos - 1]], a[i]) + 1;
used[i] = true;
order[pos] = i;
dfs(pos + 1, nxt);
used[i] = false;
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
dfs(1, 1);
cout << ans;
return 0;
}
P10721 [GESP202406 六级] 计算得分¶
提示1-特殊性质能简化吗
20分做法，价格随段长不增。
另外40分做法，\(n\le 3\)。
看全部数据范围，\(n\le 20\)，\(m\le 10^{5}\)，\(a_{i}\le 1000\)。
我先看价格不增的特殊性质：合并一段不会比拆成多个 abc 更划算，单独计分就够了。
一般价格下，这个办法不一定对。
提示2-枚举最后一段
遇到“若干段不能重叠”，我会先盯住最后一段。
\(\operatorname{dp}_{i}\) 表示前 \(i\) 个字符的最高分。
可以跳过当前字符，也可以从后往前每次检查一个 abc。
检查失败就停，最多检查 \(n\) 次。
外层正在算前i个字符，k是末段abc的个数。确认该段完整匹配后，只能接前l-1个字符的答案：
代码-20分-每个 abc 单独计分
时间 \(O(m)\)，空间 \(O(m)\)。只保证覆盖价格不增的子任务。
#include <bits/stdc++.h>
using namespace std;
const int N = 25;
int a[N];
int main() {
int n, m;
string s;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> m >> s;
// 价格不增时，我把每个abc分开算，合并不会赚得更多。
int ans = 0;
for (int i = 0; i + 2 < m; i++) {
if (s[i] == 'a' && s[i + 1] == 'b' && s[i + 2] == 'c') {
ans += a[1];
}
}
cout << ans;
return 0;
}
代码-满分-前缀 DP
时间 \(O(mn)\)，空间 \(O(m+n)\)。新段前的状态是 \(\operatorname{dp}_{l-1}\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005, M = 25;
int a[M], dp[N];
int main() {
int n, m;
string s;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> m >> s;
s = ' ' + s;
for (int i = 1; i <= m; i++) {
dp[i] = dp[i - 1];
for (int k = 1; k <= n; k++) {
int l = i - 3 * k + 1;
if (l < 1) break;
if (s[l] != 'a' || s[l + 1] != 'b' || s[l + 2] != 'c') break;
// 我把最后一段单独拿出来，前面的字符只能算到l-1。
dp[i] = max(dp[i], dp[l - 1] + a[k]);
}
}
cout << dp[m];
return 0;
}
P10722 [GESP202406 六级] 二叉树¶
提示1-先看两类部分分
20分做法，父亲为 \(i-1\)，是一条链。
另外40分做法，\(n,q\le 1000\)。
看全部数据范围，\(n,q\le 10^{5}\)。
我先按题意每次翻转整棵子树，能拿到小树的分。
链上的子树是后缀，这也提醒我：操作可以先记在起点。
提示2-只需要奇偶性
同一个节点翻转两次就恢复，我只需要记奇偶。
把操作记在子树根上，再把父亲的累计翻转传给孩子。
异或正好表示这个奇偶变化。
我用队列从根往下走，长链也不用担心递归太深。
根的累计翻转先确定，再依次访问孩子。对当前父子u、v，要把父亲的变化接到孩子本身的操作上：
代码-40分-逐次翻转
时间 \(O(nq)\)，空间 \(O(n)\)。覆盖 \(n,q\le 1000\) 的子任务。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
vector<int> child[N];
int main() {
int n, q;
string s;
cin >> n;
for (int i = 2; i <= n; i++) {
int p;
cin >> p;
child[p].push_back(i);
}
cin >> s >> q;
// 小树我先照题意做：每次把选中节点的整棵子树翻一遍。
while (q--) {
int root;
cin >> root;
queue<int> q;
q.push(root);
while (!q.empty()) {
int u = q.front();
q.pop();
s[u - 1] = (s[u - 1] == '0' ? '1' : '0');
for (int v : child[u]) q.push(v);
}
}
cout << s;
return 0;
}
代码-满分-累计翻转
时间 \(O(n+q)\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int> child[N];
int flip[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, queries;
string s;
cin >> n;
for (int i = 2; i <= n; i++) {
int p;
cin >> p;
child[p].push_back(i);
}
cin >> s >> queries;
while (queries--) {
int u;
cin >> u;
flip[u] ^= 1;
}
queue<int> q;
q.push(1);
while (!q.empty()) {
int u = q.front();
q.pop();
if (flip[u]) s[u - 1] = (s[u - 1] == '0' ? '1' : '0');
for (int v : child[u]) {
// 我只关心翻转奇偶，孩子还要接上从父亲传来的变化。
flip[v] ^= flip[u];
q.push(v);
}
}
cout << s;
return 0;
}
P11246 [GESP202409 六级] 小杨和整数拆分¶
提示1-这是求最少个数
看全部数据范围，\(n\le 10^{5}\)。
我先把状态的含义说清：\(\operatorname{dp}_{i}\) 是凑出 \(i\) 最少要几个平方数，不是有多少种拆法。
提示2-枚举最后一个平方数
我先假设最后放的是 \(j^2\)，去掉它，剩下的就是 \(i-j^2\)。
所以枚举所有 \(j^2\)，取最小值：
\(\operatorname{dp}_0=0\)，同一个平方数可以重复用。
从小到大算i，先设一个足够大的初值。内层试所有不超过i的平方数，dp[0]为0：
代码-满分
时间 \(O(n\sqrt{n})\)，空间 \(O(n)\)。
P11247 [GESP202409 六级] 算法学习¶
提示1-先选每类最有用的题
前两个子任务各 30 分，均有 \(n\le 9\)。
看全部数据范围，\(m,n,k,b_{i}\le 10^{5}\)。
我先暂时放下排列顺序。
每类都优先选提升最多的题，就能求出这一类至少要做几题。
总提升不够 \(k\)，直接无解。
提示2-题选够了，能排开吗
题够了还不一定能排开。
我拿最多的一类做检查：若有 \(\operatorname{mx}\) 题，就需要其他类至少 \(\operatorname{mx}-1\) 题来隔开。
设必选题总数为 \(\operatorname{sum}\)，能排开的条件就是 \(\operatorname{mx}\le \operatorname{sum}-\operatorname{mx}+1\)。
提示3-不够就补隔板
如果隔板不够，我会补选其他类的题，直到它们达到 \(\operatorname{mx}-1\) 题。
这样总数就是 \(2\operatorname{mx}-1\)。
其他类全部题目都不够时，才是真的无解。
这里不必实际排出顺序。
total是各类必选题之和，most是其中最多的一类，kind记录这类编号。下面只是在必选题都够分之后，决定隔板是否够用：
代码-60分-枚举选题集合
时间 \(O((n+m)2^{n})\)，空间 \(O(n+m)\)。覆盖两个 \(n\le 9\) 子任务。
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
const int INF = 1000000000;
int a[N], b[N], cnt[N], score[N];
int main() {
int m, n, k;
cin >> m >> n >> k;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
int ans = INF;
for (int mask = 0; mask < (1 << n); mask++) {
fill(cnt, cnt + m + 1, 0);
fill(score, score + m + 1, 0);
int total = 0, most = 0;
for (int i = 0; i < n; i++) {
if ((mask >> i) & 1) {
cnt[a[i]]++;
score[a[i]] += b[i];
total++;
}
}
bool ok = true;
for (int i = 1; i <= m; i++) {
if (score[i] < k) ok = false;
most = max(most, cnt[i]);
}
// 选够题后，我还要检查最多的一类能不能被其他题隔开。
if (ok && most <= total - most + 1) ans = min(ans, total);
}
cout << (ans == INF ? -1 : ans);
return 0;
}
代码-满分-分类贪心
时间 \(O(n\log n+m)\)，空间 \(O(n+m)\)。补选题只用作隔开相同知识点。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N];
vector<int> problem[N];
bool cmp(int x, int y) {
return x > y;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int m, n, k;
cin >> m >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
int b;
cin >> b;
problem[a[i]].push_back(b);
}
int total = 0, most = 0, kind = 0;
bool ok = true;
for (int i = 1; i <= m; i++) {
sort(problem[i].begin(), problem[i].end(), cmp);
long long score = 0;
int need = 0;
for (int b : problem[i]) {
if (score >= k) break;
score += b;
need++;
}
if (score < k) ok = false;
total += need;
if (need > most) {
most = need;
kind = i;
}
}
int ans = -1;
if (ok) {
if (most <= total - most + 1) ans = total;
// 必选题不够当隔板，我再检查其他类全部题目是否够用。
else if (n - (int)problem[kind].size() >= most - 1) ans = 2 * most - 1;
}
cout << ans;
return 0;
}
P11375 [GESP202412 六级] 树上游走¶
提示1-中途可能很大
40分做法，\(n\le 50\)、\(s\le 10\)。
看全部数据范围，\(n\le 10^{6}\)、\(s\le 10^{12}\)。
我会先直接乘 2、除 2 来模拟小范围。
但“最后编号小”并不保证“中途编号小”，连续往下走可能让整数溢出。
提示2-用二进制表示节点
我换成二进制看看：去左儿子就是末尾加 0，去右儿子就是加 1，向上就是删末位。
于是用字符串保存路径，最后才转回整数。
根的二进制是 1，不能把它删空。
path是根到当前位置的二进制编号，首位1不能删。处理一个操作c时，不再对可能溢出的整数乘二：
代码-40分-直接模拟
时间 \(O(n)\)，空间 \(O(n)\)。\(n\le 50\)、\(s\le 10\) 时，中间值能用 long long 保存。
代码-满分-二进制路径
时间 \(O(n+\log s)\)，空间 \(O(n+\log s)\)，中途不会发生整数溢出。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
long long pos;
string s, path;
cin >> n >> pos >> s;
while (pos > 0) {
path.push_back(char('0' + pos % 2));
pos /= 2;
}
reverse(path.begin(), path.end());
// 我把编号换成二进制路径，向下添一位，向上删一位。
for (char c : s) {
if (c == 'U') {
if (path.size() > 1) path.pop_back();
} else {
path.push_back(c == 'L' ? '0' : '1');
}
}
long long ans = 0;
for (char c : path) ans = ans * 2 + c - '0';
cout << ans;
return 0;
}
P11376 [GESP202412 六级] 运送物资¶
提示1-先拆开一辆车的代价
前两个子任务各 20 分，均有站点容量为 1。
看全部数据范围，\(n,m\le 10^{5}\)，\(x\le 10^{8}\)，次数、容量\(\le 10^{5}\)。
我先写出一辆车放在 \(p\) 的代价，再展开：\(2bx+2(a-b)p\)。
第一项固定，真正影响位置选择的是 \(a-b\)。
提示2-谁应该靠左
我试着交换两辆车的位置，发现 \(a-b\) 越大的车越应该靠左。
这样排序的理由就有了。
正差值从左分，负差值从右分，都先安排绝对差值大的车。
提示3-别忘了站点容量
分配时我把站点看成有多个车位的格子：满了就一直往下找，不能只跳过一个。
总容量保证足够。
总路程可能接近 \(2\times 10^{18}\)，乘法一开始就要用 long long。
站点已按位置升序排列。安排左侧的一辆车t前，可能有连续多个站已满，所以这里必须用while：
代码-满分-排序分配
时间 \(O(n\log n+m\log m)\)，空间 \(O(n+m)\)。容量为 1 也使用同一算法。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
struct Station {
int pos, capacity;
};
struct Truck {
int a, b;
};
Station station[N];
Truck left_truck[N], right_truck[N];
int left_count, right_count;
bool cmp(Station a, Station b) {
return a.pos < b.pos;
}
bool cmp_left(Truck a, Truck b) {
return a.a - a.b > b.a - b.b;
}
bool cmp_right(Truck a, Truck b) {
return a.b - a.a > b.b - b.a;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, x;
cin >> n >> m >> x;
for (int i = 0; i < n; i++) cin >> station[i].pos >> station[i].capacity;
sort(station, station + n, cmp);
for (int i = 0; i < m; i++) {
Truck t;
cin >> t.a >> t.b;
if (t.a >= t.b) left_truck[left_count++] = t;
else right_truck[right_count++] = t;
}
// 交换两辆车的位置后，我发现差值大的更应该靠近A。
sort(left_truck, left_truck + left_count, cmp_left);
sort(right_truck, right_truck + right_count, cmp_right);
long long ans = 0;
int l = 0, r = n - 1;
for (int i = 0; i < left_count; i++) {
Truck t = left_truck[i];
while (station[l].capacity == 0) l++;
int p = station[l].pos;
ans += 2LL * t.a * p + 2LL * t.b * (x - p);
station[l].capacity--;
}
for (int i = 0; i < right_count; i++) {
Truck t = right_truck[i];
while (station[r].capacity == 0) r--;
int p = station[r].pos;
ans += 2LL * t.a * p + 2LL * t.b * (x - p);
station[r].capacity--;
}
cout << ans;
return 0;
}
P11962 [GESP202503 六级] 树上漫步¶
提示1-先从每个点搜索
40分做法，\(n\le 1000\)。
看全部数据范围，\(n\le 2\times 10^{5}\)。
我先从每个点 BFS，统计偶数距离，得到一个能验证的小范围办法。
走零步也合法，所以自己要算进去。
提示2-来回走不会改变奇偶
重复走路看起来很麻烦，但树上绕出去还要沿原路回来，多走的步数总是偶数。
于是只用看距离的奇偶。
我从根按深度奇偶分两组，同组之间距离为偶数。
每个点的答案就是自己那组的人数。
从u第一次走到v，深度奇偶恰好改变一次。统计完两类人数cnt后，节点i只取自己所属类的数量：
代码-40分-逐点 BFS
时间 \(O(n^{2})\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
vector<int> g[N];
int dist[N];
int main() {
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
// 我先逐个起点搜索，把距离为偶数的终点数出来。
for (int start = 1; start <= n; start++) {
fill(dist, dist + n + 1, -1);
queue<int> q;
q.push(start);
dist[start] = 0;
int ans = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
if (dist[u] % 2 == 0) ans++;
for (int v : g[u]) {
if (dist[v] != -1) continue;
dist[v] = dist[u] + 1;
q.push(v);
}
}
if (start > 1) cout << ' ';
cout << ans;
}
return 0;
}
代码-满分-按奇偶分组
时间 \(O(n)\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
vector<int> g[N];
int color[N], cnt[2];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
fill(color, color + n + 1, -1);
queue<int> q;
q.push(1);
color[1] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
cnt[color[u]]++;
for (int v : g[u]) {
if (color[v] != -1) continue;
// 每走一条边奇偶就变一次，我用两种颜色记录这个规律。
color[v] = color[u] ^ 1;
q.push(v);
}
}
for (int i = 1; i <= n; i++) {
if (i > 1) cout << ' ';
cout << cnt[color[i]];
}
return 0;
}
P11963 [GESP202503 六级] 环线¶
提示1-枚举起点和长度
20分做法，\(n\le 200\)。
40分做法，\(n\le 2000\)。
看全部数据范围，\(n\le 2\times 10^{5}\)，\(|a_{i}|\le 10^{9}\)。
我先固定起点，再把行程一站一站延长。
边走边累加，不用每次重新求和，平方级就能拿到 40分。
提示2-跨过首尾怎么处理
不跨首尾时，我想到普通最大子段和。
跨首尾时，两头都选了，中间有一段没选。
我就反过来找这段：总和减去最小子段和，同时保留普通最大子段和来比较。
提示3-必须至少选一个
最后我会拿全负数试一下：总和减掉整个数组，会得到不合法的空段。
全负时直接选最大的单个数。
其余情况比较两种答案，计算用 long long。
扫描到新值x，max_end和min_end分别记以当前位置结尾的最大、最小非空段和。要么接在前段后面，要么从x重新开始：
代码-40分-枚举环段
时间 \(O(n^{2})\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
const long long NEG = -(1LL << 60);
long long a[N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
long long ans = NEG;
// 我固定起点逐站延长，每次只加新经过的一站。
for (int start = 0; start < n; start++) {
long long sum = 0;
for (int len = 1; len <= n; len++) {
sum += a[(start + len - 1) % n];
ans = max(ans, sum);
}
}
cout << ans;
return 0;
}
代码-满分-最大与最小子段和
时间 \(O(n)\)，额外空间 \(O(1)\)。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
long long x;
cin >> n >> x;
long long total = x, max_end = x, min_end = x;
long long best = x, worst = x;
for (int i = 2; i <= n; i++) {
cin >> x;
total += x;
max_end = max(x, max_end + x);
min_end = min(x, min_end + x);
best = max(best, max_end);
worst = min(worst, min_end);
}
long long ans = best;
// 我用全负数检查边界：不能把整个数组减掉，选出空段。
if (best >= 0) ans = max(ans, total - worst);
cout << ans;
return 0;
}
P13015 [GESP202506 六级] 学习小组¶
提示1-只关心各组人数
40分做法，\(n\le 10\)。
看全部数据范围，\(n\le 1000\)，\(a_{i}\le 10^{4}\)。
我先看价值由什么决定：只看人数，不看具体是谁。
所以不用安排同学名单，只需要决定每组几个人。
提示2-最后一组有几人
假设最后一组有 \(j\) 人，前面的 \(i-j\) 人也在做同一个分组问题。
于是 \(\operatorname{dp}_{i}\) 从 \(\operatorname{dp}_{i-j}+a_{j}\) 中取最大值。
这就是我找到转移的方法。
外层人数i从1递增。假设最后一组有j人，前i-j人的最佳分值已经算好，dp[0]为0：
代码-满分-人数 DP
时间 \(O(n^{2})\)，空间 \(O(n)\)。同一种组大小可以重复使用。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int a[N], dp[N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
// 我只决定最后一组有几人，剩余同学的最优值已经算好了。
for (int j = 1; j <= i; j++) {
dp[i] = max(dp[i], dp[i - j] + a[j]);
}
}
cout << dp[n];
return 0;
}
P13016 [GESP202506 六级] 最大因数¶
提示1-父亲是什么
60分做法，\(x,y\le 1000\)。
看全部数据范围，\(q\le 1000\)，\(x,y\le 10^{9}\)。
我先拿 12 试一试：它的父亲是 6，也就是除以最小质因数 2。
一般整数也满足这个规律。
两数不同时，让较大的那个往上走，直到相遇，就能求距离。
提示2-每次重新试除太慢
每上跳一次都重新找因数有些浪费。
我把质因数从小到大列出来，依次除掉，就能一次得到整条祖先链。
然后比较两条链，每次推进数值较大的那条。
每次除掉的质因数至少为2，\(10^9\) 以内的祖先链不超过31个节点，用长度35的静态数组就够了。
静态数组path按从大到小保存祖先，len记录已存项数。试到质因数p后，每除一次就是沿父亲边上跳一次：
代码-60分-逐次找父亲
每次上跳都试除找最小质因数。适用于 \(x,y\le 1000\)。
#include <bits/stdc++.h>
using namespace std;
int parent(int x) {
// 我从小到大找因数，第一个因数就是最小质因数。
for (int p = 2; p <= x / p; p++) {
if (x % p == 0) return x / p;
}
return 1;
}
int main() {
int q;
cin >> q;
for (int t = 0; t < q; t++) {
int x, y;
cin >> x >> y;
int ans = 0;
while (x != y) {
if (x > y) x = parent(x);
else y = parent(y);
ans++;
}
if (t > 0) cout << '\n';
cout << ans;
}
return 0;
}
代码-满分-一次分解得到祖先链
每次询问时间 \(O(\sqrt{x}+\sqrt{y})\)，空间 \(O(\log\max(x,y))\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 35;
int a[N], b[N];
int get_path(int x, int path[]) {
int len = 0;
path[len++] = x;
for (int p = 2; p <= x / p; p++) {
// 我依次除掉最小质因数，每除一次就往父亲走一步。
while (x % p == 0) {
x /= p;
path[len++] = x;
}
}
if (x > 1) path[len++] = 1;
return len;
}
int main() {
int q;
cin >> q;
for (int t = 0; t < q; t++) {
int x, y;
cin >> x >> y;
get_path(x, a);
get_path(y, b);
int i = 0, j = 0;
while (a[i] != b[j]) {
if (a[i] > b[j]) i++;
else j++;
}
if (t > 0) cout << '\n';
cout << i + j;
}
return 0;
}
P14075 [GESP202509 六级] 划分字符串¶
提示1-枚举最后一段
40分做法，\(n\le 1000\)。
看全部数据范围，\(n\le 10^{5}\)，\(a_{i}\le 10^{9}\)。
我先抓住最后一段：假设它从 \(j\) 开始、在 \(i\) 结束，前面就交给 \(\operatorname{dp}_{j-1}\)。
这样不会和前面的段重叠。
提示2-为什么只找 26 次
两层循环看着像平方级，但我再看字符范围：只有 26 种小写字母，合法的一段最多长 26。
从 \(j=i\) 往前找，重复就停，用 \(\operatorname{dp}_{j-1}+a_{i-j+1}\) 更新。
单个字符不能漏，答案用 long long。
代码把字符串下标从1开始存。固定右端点i，j从i向前走；used记录这一段已出现的字母，遇到重复就停止：
代码-满分-前缀 DP
时间 \(O(26n)\)，空间 \(O(n)\)。小写字母限制使这套算法直接覆盖全部数据。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N];
long long dp[N];
bool used[26];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
string s;
cin >> n >> s;
for (int i = 1; i <= n; i++) cin >> a[i];
s = ' ' + s;
for (int i = 1; i <= n; i++) {
fill(used, used + 26, false);
// 我从单个字符开始向前扩展，遇到重复后，更长的段也不合法。
for (int j = i; j >= 1; j--) {
int c = s[j] - 'a';
if (used[c]) break;
used[c] = true;
dp[i] = max(dp[i], dp[j - 1] + a[i - j + 1]);
}
}
cout << dp[n];
return 0;
}
P14076 [GESP202509 六级] 货物运输¶
提示1-先看链
30分做法，\(n\le 8\)。
另外30分做法，树是一条链。
看全部数据范围，\(n\le 10^{5}\)，边长\(\le 10^{9}\)。
我先在链上画一条路线：两边都要去，但最后停下的那一边不用返回。
我会选择把这次返回省在较远的一边。
提示2-哪些边不用返回
把这个想法放到树上：若回到 1，每条边都走两次。
最后停在 \(v\)，就能省掉 1 到 \(v\) 的一次路程。
所以我先算边长总和的两倍，再减去从 1 出发的最长距离。
计算用 long long。
total记录所有边长之和，farthest记录从1出发的最远距离。最后保留的那条路无需返回：
代码-满分-求离起点最远的点
时间 \(O(n)\)，空间 \(O(n)\)。链与一般树都用同一结论。队列遍历避免长链递归。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<pair<int, int>> g[N];
long long dist[N];
int parent[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
long long total = 0;
cin >> n;
for (int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
total += w;
}
long long farthest = 0;
queue<int> q;
q.push(1);
while (!q.empty()) {
int u = q.front();
q.pop();
farthest = max(farthest, dist[u]);
for (auto edge : g[u]) {
int v = edge.first, w = edge.second;
if (v == parent[u]) continue;
parent[v] = u;
dist[v] = dist[u] + w;
q.push(v);
}
}
// 我先按每条边往返计算，再省掉到最终停点的那一次返回。
cout << 2 * total - farthest;
return 0;
}
P14919 [GESP202512 六级] 路径覆盖¶
提示1-先看小树和链
40分做法，\(n\le 16\)。
另外20分做法，父亲为 \(i-1\)，是一条链。
看全部数据范围，\(n\le 10^{5}\)，代价\(\le 10^{9}\)。
我先看最简单的链：只有一条根到叶子的路径，选代价最小的点就够了。
小树则可以枚举黑点集合。
提示2-一个子树有两种选择
我站在节点 \(u\) 想：染黑自己，下面所有路径都覆盖了。
不染自己，就得让每个孩子的子树分别完成覆盖。
这两种选择的代价分别是 \(c_{u}\) 和孩子答案之和，取小即可。
提示3-叶子必须染黑
我会单独检查叶子：它没有孩子，不能把空的孩子和当成零代价，它必须染黑。
题目保证父亲编号更小，我按编号倒序算，孩子就先算完了。
代价和用 long long。
倒序算节点u时，孩子已经把代价加进sum[u]。叶子没有孩子，但不能因此免费覆盖：
代码-40分-枚举黑点集合
时间 \(O(n^{2} 2^{n})\)，空间 \(O(n)\)。仅适用于 \(n\le 16\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
const long long INF = 1LL << 60;
int parent[N], cost[N];
bool leaf[N];
int main() {
int n;
cin >> n;
fill(leaf, leaf + n + 1, true);
for (int i = 2; i <= n; i++) {
cin >> parent[i];
leaf[parent[i]] = false;
}
for (int i = 1; i <= n; i++) cin >> cost[i];
long long ans = INF;
for (int mask = 0; mask < (1 << n); mask++) {
long long sum = 0;
for (int i = 1; i <= n; i++) {
if ((mask >> (i - 1)) & 1) sum += cost[i];
}
bool ok = true;
// 我从每个叶子往上找，确认这条路径真的遇到了黑点。
for (int i = 1; i <= n && ok; i++) {
if (!leaf[i]) continue;
int u = i;
while (u && !((mask >> (u - 1)) & 1)) u = parent[u];
if (u == 0) ok = false;
}
if (ok) ans = min(ans, sum);
}
cout << ans;
return 0;
}
代码-满分-树形 DP
时间 \(O(n)\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int parent[N], cost[N], children[N];
long long dp[N], sum[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for (int i = 2; i <= n; i++) {
cin >> parent[i];
children[parent[i]]++;
}
for (int i = 1; i <= n; i++) cin >> cost[i];
for (int u = n; u >= 1; u--) {
// 我先处理叶子：它必须染黑，不能套用空的孩子代价和。
if (children[u] == 0) dp[u] = cost[u];
else dp[u] = min(1LL * cost[u], sum[u]);
if (u != 1) sum[parent[u]] += dp[u];
}
cout << dp[1];
return 0;
}
P14920 [GESP202512 六级] 道具商店¶
提示1-金币能作背包容量吗
60分做法，\(k\)、\(c_{i}\le 500\)。
看全部数据范围，\(n\le 500\)，\(k\)、\(c_{i}\le 10^{9}\)，\(a_{i}\le 500\)。
我第一反应是按金币做 01 背包，小范围确实能用。
但 \(k\) 到了十亿，这个维度就开不下了。
提示2-换一个较小的维度
我再找一个小的量：总攻击力最多只有 \(500\times 500\)。
于是把状态反过来，\(\operatorname{dp}_{v}\) 记录得到 \(v\) 点攻击力最少花多少钱。
倒序更新后，找费用不超过 \(k\) 的最大 \(v\)。
费用和用 long long。
当前道具加a点攻击力、花cost金币。total是已读道具攻击力之和，倒序保证本件只用一次；不可达状态不能转移：
代码-60分-按金币背包
时间 \(O(nk)\)，空间 \(O(k)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int dp[N];
int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
int a, cost;
cin >> a >> cost;
// 金币少时，我先用熟悉的01背包，倒序保证每件只买一次。
for (int j = k; j >= cost; j--) {
dp[j] = max(dp[j], dp[j - cost] + a);
}
}
cout << dp[k];
return 0;
}
代码-满分-按攻击力背包
设 \(V\) 为总攻击力，时间 \(O(nV)\)，空间 \(O(V)\)，\(V\le 250000\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 250005;
const long long INF = 1LL << 60;
long long dp[N];
int main() {
int n, k;
cin >> n >> k;
fill(dp, dp + N, INF);
dp[0] = 0;
int total = 0;
for (int i = 1; i <= n; i++) {
int a, cost;
cin >> a >> cost;
total += a;
// 总攻击力比金币小得多，我改为记录每种攻击力的最低花费。
for (int j = total; j >= a; j--) {
if (dp[j - a] == INF) continue;
dp[j] = min(dp[j], dp[j - a] + cost);
}
}
int ans = 0;
for (int i = 0; i <= total; i++) {
if (dp[i] <= k) ans = i;
}
cout << ans;
return 0;
}
P15800 [GESP202603 六级] 选数¶
提示1-从选中的最后一个点转移
40分做法，\(n\le 1000\)。
看全部数据范围，\(n\le 10^{5}\)，\(a_{i}\le 10^{9}\)，\(0\le b_{i}\le n\)。
我先写一个直接的转移：枚举前一个选中的位置 \(j\)，检查它能不能接到 \(i\)。
小范围先用它验证思路。
提示2-从后往前看
从前往后看，要找很多前驱。
我换到从后往前看，当前点就只有选和不选两种决定。
不选 \(i\)，得到 \(\operatorname{dp}_{i+1}\)。
选 \(i\)，得到 \(a_{i}+\operatorname{dp}_{\operatorname{next}}\)。
提示3-间隔为零也不能重复选
这里我会专门试 \(b_{i}=0\)：下标仍要严格递增，不能又选自己。
所以 \(\operatorname{next}=\min(n+1,i+\max(1,b_i))\)，\(\operatorname{dp}_{n+1}=0\) 表示后面没有数可选。
答案用 long long。
外层i从n倒着走。nxt至少是i+1，即使b[i]为0，也不会把自己再次选中：
代码-40分-枚举前一个位置
时间 \(O(n^{2})\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int a[N], b[N];
long long dp[N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
long long ans = 0;
for (int i = 1; i <= n; i++) {
dp[i] = a[i];
// 我先检查前一个选中的位置是否允许跳到这里。
for (int j = 1; j < i; j++) {
if (i >= j + b[j]) dp[i] = max(dp[i], dp[j] + a[i]);
}
ans = max(ans, dp[i]);
}
cout << ans;
return 0;
}
代码-满分-后缀 DP
时间 \(O(n)\)，空间 \(O(n)\)。允许全为 0，此时选任意一个位置也能得到最优值 0。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N], b[N];
long long dp[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
for (int i = n; i >= 1; i--) {
// 即使间隔为0，我也得走到下一个下标，不能重复选自己。
int next = min(n + 1, i + max(1, b[i]));
dp[i] = max(dp[i + 1], a[i] + dp[next]);
}
cout << dp[1];
return 0;
}
P15801 [GESP202603 六级] 完全二叉树¶
提示1-按层检查有没有空位
40分做法，\(n\le 500\)。
看全部数据范围，\(n\le 10^{5}\)。
我先按层从左到右观察完全二叉树：一旦出现空位，后面就不能再有节点。
逐棵 BFS 可以解决小范围。
提示2-大树要合并左右结果
逐棵检查会重复看同一批节点，我就想让孩子把检查结果告诉父亲。
除了是否完全，还要知道高度和是否每层都满。
空树高度为 0，视为满且完全，叶子也能直接按同一规则判断。
提示3-只有两种接法
我画图看最后一层该往哪边放：左右等高时，左边必须满、右边可以完全。
左边高一层时，左边可以完全、右边必须满。
其他高度关系都不行。
我先处理孩子再处理父亲，不假设编号就是遍历顺序。
倒序遍历order时，先读出左右孩子l、r。空树0号的full与complete都为真，高度为0。两种接法分别写，别把或误写成且：
代码-40分-逐棵 BFS
时间 \(O(n^{2})\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int left_child[N], right_child[N];
bool check(int root) {
queue<int> q;
q.push(root);
bool empty = false;
while (!q.empty()) {
int u = q.front();
q.pop();
if (u == 0) {
empty = true;
continue;
}
// 我按层扫描，空位之后又出现节点，就不可能是完全二叉树。
if (empty) return false;
q.push(left_child[u]);
q.push(right_child[u]);
}
return true;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> left_child[i] >> right_child[i];
int ans = 0;
for (int i = 1; i <= n; i++) {
if (check(i)) ans++;
}
cout << ans;
return 0;
}
代码-满分-合并左右子树
时间 \(O(n)\)，空间 \(O(n)\)。先记录遍历顺序，再倒序计算，避免长链递归。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int order[N];
int left_child[N], right_child[N], height[N];
bool full[N], complete[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> left_child[i] >> right_child[i];
int len = 0;
order[len++] = 1;
for (int i = 0; i < len; i++) {
int u = order[i];
if (left_child[u]) order[len++] = left_child[u];
if (right_child[u]) order[len++] = right_child[u];
}
full[0] = complete[0] = true;
int ans = 0;
for (int i = n - 1; i >= 0; i--) {
int u = order[i], l = left_child[u], r = right_child[u];
height[u] = max(height[l], height[r]) + 1;
full[u] = full[l] && full[r] && height[l] == height[r];
// 我画了最后一层的两种接法，再把它们分别写成判断条件。
complete[u] = (full[l] && complete[r] && height[l] == height[r])
|| (complete[l] && full[r] && height[l] == height[r] + 1);
if (complete[u]) ans++;
}
cout << ans;
return 0;
}
P17012 [GESP202606 六级] 条形蛋糕¶
提示1-不要只选单价最高的
看全部数据范围，\(n\le 1000\)，\(p_{i}\le 10^{5}\)。
我会先试按单价贪心，但选完后可能还剩一截，补上它的价格也要算。
只比较单价，没把整个方案考虑全。
提示2-最后切下多长一块
我改成看最后切下的一块：长度为 \(j\) 时，剩余长度 \(i-j\) 的最高售价已经由 \(\operatorname{dp}_{i-j}\) 记录。
用 \(\operatorname{dp}_{i-j}+p_{j}\) 更新。
它和学习小组是同一个模型，同种长度可以重复切。
外层枚举总长度i，内层枚举最后一块长度j。整块不切也在j等于i时被考虑，dp[0]为0：
代码-满分-长度 DP
时间 \(O(n^{2})\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int price[N], dp[N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> price[i];
for (int i = 1; i <= n; i++) {
// 我枚举最后一块的长度，把剩余蛋糕交给已经算出的答案。
for (int j = 1; j <= i; j++) {
dp[i] = max(dp[i], dp[i - j] + price[j]);
}
}
cout << dp[n];
return 0;
}
P17013 [GESP202606 六级] 满二叉树¶
提示1-满二叉树要每层都满
40分做法，\(n\le 500\)。
看全部数据范围，\(n\le 10^{5}\)。
我先用一棵左右叶子不在同层的树试定义：即使每个非叶节点都有两个孩子，也不一定满。
还要每层都满，单个叶子也算。
提示2-左右子树也必须满
整棵树要每层都满，左右子树就必须都满，而且一样高。
我只让孩子传回这两个信息，父亲就能判断。
空树高度为 0、视为满。
先算孩子，再算父亲，叶子自然满足条件。
先算左右孩子，再算父亲u。空树0号视为满，下面两项缺一不可：
代码-40分-逐棵检查叶子深度
时间 \(O(n^{2})\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int left_child[N], right_child[N];
bool check(int root) {
queue<pair<int, int>> q;
q.push({root, 1});
int leaf_depth = -1;
while (!q.empty()) {
int u = q.front().first, depth = q.front().second;
q.pop();
int l = left_child[u], r = right_child[u];
if (l == 0 && r == 0) {
if (leaf_depth == -1) leaf_depth = depth;
// 我同时检查叶子是否在同层，只有两个孩子还不够。
if (leaf_depth != depth) return false;
} else {
if (l == 0 || r == 0) return false;
q.push({l, depth + 1});
q.push({r, depth + 1});
}
}
return true;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> left_child[i] >> right_child[i];
int ans = 0;
for (int i = 1; i <= n; i++) {
if (check(i)) ans++;
}
cout << ans;
return 0;
}
代码-满分-子树 DP
时间 \(O(n)\)，空间 \(O(n)\)。按遍历顺序倒序计算，不依赖节点编号大小。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int order[N];
int left_child[N], right_child[N], height[N];
bool full[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> left_child[i] >> right_child[i];
int len = 0;
order[len++] = 1;
for (int i = 0; i < len; i++) {
int u = order[i];
if (left_child[u]) order[len++] = left_child[u];
if (right_child[u]) order[len++] = right_child[u];
}
full[0] = true;
int ans = 0;
for (int i = n - 1; i >= 0; i--) {
int u = order[i], l = left_child[u], r = right_child[u];
height[u] = max(height[l], height[r]) + 1;
// 我检查左右都满而且一样高，才能确认当前子树每层都满。
full[u] = full[l] && full[r] && height[l] == height[r];
if (full[u]) ans++;
}
cout << ans;
return 0;
}
P17457 [GESP202609 六级] 数组划分¶
提示1-非负数可以直接拆
40分做法，\(0\le a_{i}\le 50\)。
看全部数据范围，\(n\le 2000\)，\(-100\le a_{i}\le 100\)。
我先合并两个非负的段看看：\((x+y)^{2}\) 比 \(x^{2}+y^{2}\) 多了 \(2xy\)。
合并不会更好，所以非负子任务每个数单独一段即可。
提示2-负数会改变结论
再试 1 和 -1，合并后代价从 2 变成 0。
这个例子提醒我，有负数时不能沿用刚才的贪心。
我改成前缀 DP，枚举最后一段从哪里开始。
提示3-用前缀和算段和
最后一段若是 \(j+1\) 到 \(i\)，我用前缀和马上得到段和 \(s_{i}-s_{j}\)。
用 \(\operatorname{dp}_{j}+(s_{i}-s_{j})^{2}\) 更新。
\(n\) 只有 2000，平方级足够，不必再找复杂优化。
平方用 long long。
sum是前缀和，dp[0]为0。外层i递增，内层j枚举最后一段前的位置；先算段和，再平方：
代码-40分-每个数单独一段
时间 \(O(n)\)，额外空间 \(O(1)\)，仅适用于所有元素非负。
代码-满分-枚举最后一段
时间 \(O(n^{2})\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
const long long INF = 1LL << 60;
long long sum[N], dp[N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
sum[i] = sum[i - 1] + x;
}
for (int i = 1; i <= n; i++) {
dp[i] = INF;
// 负数可能抵消，我不再贪心，而是试遍最后一段的起点。
for (int j = 0; j < i; j++) {
long long value = sum[i] - sum[j];
dp[i] = min(dp[i], dp[j] + value * value);
}
}
cout << dp[n];
return 0;
}
P17458 [GESP202609 六级] 分树规划¶
提示1-40分：先真的试着删边
40分做法，\(2\le n\le500\)。
看全部数据范围，\(2\le n\le2\times10^4\)。
先别急着想优化，我先枚举删哪条边。搜索时跳过这条边，数出其中一块有 \(k\) 个节点，另一块就是 \(n-k\) 个。
这次删边的差值是 \(|k-(n-k)|=|n-2k|\)。试完所有边，取最小值。
每次搜索要扫一遍树，共有 \(n-1\) 条边，所以是 \(O(n^2)\)。大范围慢在反复统计同一批节点。
提示2-怎样不删边，也知道一块有多大
我任选节点 \(1\) 为根，给每个节点确定父亲。
对于非根节点 \(u\)，删去它和父亲之间的边后，\(u\) 及其所有后代恰好分成一块，也就是以 \(u\) 为根的子树。
为什么不会从别处绕回父亲？因为树上两点之间只有一条路径。
所以我只需要求每个节点的子树大小 \(sz_u\)，就能算出对应删边的差值 \(|n-2sz_u|\)。每个非根节点对应一条边，既不漏，也不重复。
提示3-子树大小怎样从孩子往上算
咱们先画一棵6个节点的树：\(1\) 的孩子是 \(2,3\)；\(2\) 的孩子是 \(4,5\)；\(3\) 的孩子是 \(6\)。
叶子 \(4,5,6\) 的子树都只有自己，大小为 \(1\)。
节点 \(2\) 的子树大小为 \(1+1+1=3\)，节点 \(3\) 的为 \(1+1=2\)。这里第一个 \(1\) 是节点自己，不能漏掉。
删边 \(1\text{—}2\)，两块就是 \(3\) 个和 \(6-3=3\) 个，差值为 \(0\)；删边 \(1\text{—}3\)，则是 \(2\) 个和 \(4\) 个，差值为 \(2\)。
我把这个计算推广到每个节点：自己的 \(1\)，加上所有孩子的子树大小。你看，得先算孩子，再算父亲，顺序不能反过来。
提示4-代码为什么倒着遍历order
代码先从根出发，把节点放进 order，同时记录 parent。父亲一定先放进去，孩子后放进去；节点编号本身不保证这个顺序。
再倒着处理 order，孩子就一定先于父亲处理。每个节点先记大小为 \(1\)，处理完它时，把完整的子树大小加给父亲。
例如节点 \(4,5\) 都处理完后，节点 \(2\) 的大小已经累加到 \(3\)，这时才能计算删去它的父亲边会得到什么结果。
这里先看两句局部代码，sz[u]开始时是 \(1\)。倒着处理到节点 \(u\) 时，孩子已经把大小交给它了：
第一行算删父亲边的差值，第二行把自己的整棵子树交给父亲。这两句接在一起，才不会漏掉后代。
根没有父亲边，所以倒序循环不处理 order[0]。这样只遍历两遍树，时间降到 \(O(n)\)，也避免长链递归过深。
提示5-静态数组怎样存边和遍历顺序
每条边要能双向走，所以输入一条边，要存两个方向。这里用静态邻接表：h[u]是节点u的第一条出边编号，e[j]是终点，ne[j]是下一条出边编号；编号 \(0\) 表示没有边。
下面是遍历节点u的邻居的局部写法。别被数组名绕住了，它做的事就是逐个取出邻居v：
for (int j = h[u]; j != 0; j = ne[j]) {
int v = e[j];
if (v == parent[u]) continue;
parent[v] = u;
order[len++] = v;
}
order也是静态数组，len记录已放入多少个节点。父亲先放入，孩子后放入，倒过来算就行。
树最多 \(20000\) 个节点、\(19999\) 条边，边数组留出两个方向的容量。这里不用额外添加输入加速。
代码-40分-枚举删边
时间 \(O(n^{2})\)，空间 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int h[N], e[N * 2], ne[N * 2], idx;
int from[N], to[N];
bool used[N];
int q[N];
void add(int u, int v) {
idx++;
e[idx] = v;
ne[idx] = h[u];
h[u] = idx;
}
int main() {
int n;
cin >> n;
for (int i = 1; i < n; i++) {
cin >> from[i] >> to[i];
add(from[i], to[i]);
add(to[i], from[i]);
}
int ans = n;
// 我先逐条试删边，再数一侧的节点，作为小范围办法。
for (int i = 1; i < n; i++) {
int a = from[i], b = to[i], count = 0;
fill(used, used + n + 1, false);
int hh = 0, tt = 0;
q[tt++] = a;
used[a] = true;
while (hh < tt) {
int u = q[hh++];
count++;
for (int j = h[u]; j != 0; j = ne[j]) {
int v = e[j];
if ((u == a && v == b) || (u == b && v == a)) continue;
if (used[v]) continue;
used[v] = true;
q[tt++] = v;
}
}
ans = min(ans, abs(n - 2 * count));
}
cout << ans;
return 0;
}
代码-满分-统计子树大小
时间 \(O(n)\)，空间 \(O(n)\)。先遍历，再倒序累计子树大小。
#include <bits/stdc++.h>
using namespace std;
const int N = 20005;
int h[N], e[N * 2], ne[N * 2], idx;
int parent[N], sz[N], order[N];
void add(int u, int v) {
idx++;
e[idx] = v;
ne[idx] = h[u];
h[u] = idx;
}
int main() {
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
int len = 1;
order[0] = 1;
for (int i = 0; i < len; i++) {
int u = order[i];
sz[u] = 1;
for (int j = h[u]; j != 0; j = ne[j]) {
int v = e[j];
if (v == parent[u]) continue;
parent[v] = u;
order[len++] = v;
}
}
int ans = n;
for (int i = n - 1; i > 0; i--) {
int u = order[i];
// 孩子已经把大小加给了我，此时sz[u]就是完整的子树大小。
ans = min(ans, abs(n - 2 * sz[u]));
// 我处理完自己的子树，再把大小交给父亲。
sz[parent[u]] += sz[u];
}
cout << ans;
return 0;
}