GESP 7级
P10265 [GESP样题 七级] 迷宫统计¶
提示1-看清“直接”
30分做法，\(n\le 10\)。
另外30分做法，\(n\le 100\)。
看全部数据范围，\(n\le 1000\)。
这里只问直接到达，不需要搜索路径。
提示2-看哪一行、哪一列
第 \(m\) 行表示从 \(m\) 出发，第 \(m\) 列表示到达 \(m\)。
自己到自己也要计数。
最后输出的是两个数量之和，不是去重后的数量。
正在读第i行、第j列的输入x时，只需维护两个计数。对角线也分别属于这一行和这一列：
代码-满分-边读边统计
\(O(n^{2})\) 时间，\(O(1)\) 额外空间。输入本身就有 \(n^{2}\) 个数，无需另写部分分。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, out = 0, in = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1, x; j <= n; j++) {
cin >> x;
if (i == m) out += x;
if (j == m) in += x;
}
}
cout << out << ' ' << in << ' ' << out + in;
return 0;
}
P10287 [GESP样题 七级] 最长不下降子序列¶
提示1-先看特殊性质
30分做法，\(n\le 1000\)，图是一条链。
另外30分做法，点权\(\le 2\)。
看全部数据范围，\(n,m\le 10^{5}\)，点权\(\le 10\)。
链上就是普通的最长不下降子序列，可以用平方级 DP。
注意链的顺序不一定是编号顺序。
提示2-点权只有十种
走到同一个点时，只需记录：最后选的点权是几，最多选了几个点。
设 \(\operatorname{dp}_{u,v}\) 表示走到 \(u\)，最后选的权值为 \(v\) 的最大长度。
\(v=0\) 表示还没选。
提示3-选或不选
按拓扑顺序处理 \(u\)。
可以跳过 \(u\)，也可以从最后权值不超过 \(a_{u}\) 的状态中选上 \(u\)。
再把所有状态传给后继。
不可达状态设为 -1，允许从任意点开始。
轮到拓扑序中的u时，先找末值不超过a[u]的最佳状态。只接上一轮状态，当前节点恰好选一次：
代码-30分-小图 DP
\(O(n(n+m))\) 时间，\(O(n+m)\) 空间。链上 \(m=n-1\)，即 \(O(n^{2})\)，覆盖 30 分子任务。只有可达的点才能接在同一条路径上。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
vector<int> g[N];
int a[N], deg[N], dp[N];
bool vis[N];
int order[N];
int main() {
int n, m;
cin >> n >> m;
fill(a, a + n + 1, 0);
fill(deg, deg + n + 1, 0);
int len = 0;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
g[u].push_back(v);
deg[v]++;
}
queue<int> q;
for (int u = 1; u <= n; u++) if (deg[u] == 0) q.push(u);
while (!q.empty()) {
int u = q.front();
q.pop();
order[len++] = u;
for (int v : g[u]) {
deg[v]--;
if (deg[v] == 0) q.push(v);
}
}
// dp[u]：最后选中u的最长不下降子序列长度。
fill(dp, dp + (n + 1), 1);
int ans = 1;
for (int z = 0; z < len; z++) {
int u = order[z];
ans = max(ans, dp[u]);
fill(vis, vis + (n + 1), 0);
q.push(u);
vis[u] = true;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int v : g[x]) if (!vis[v]) {
vis[v] = true;
q.push(v);
// 中间点可以跳过，但下一个选中的点必须能从u到达。
if (a[u] <= a[v]) dp[v] = max(dp[v], dp[u] + 1);
}
}
}
cout << ans;
return 0;
}
代码-满分-拓扑 DP
\(O(10(n+m))\) 时间，\(O(10n+m)\) 空间。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int> g[N];
int a[N], deg[N];
int dp[N][11];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
fill(a, a + (n + 1), 0);
fill(deg, deg + (n + 1), 0);
for (int u = 1; u <= n; u++) {
cin >> a[u];
for (int v = 0; v <= 10; v++) dp[u][v] = -1;
dp[u][0] = 0;
}
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
g[u].push_back(v);
deg[v]++;
}
queue<int> q;
for (int u = 1; u <= n; u++) if (!deg[u]) q.push(u);
int ans = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
int best = 0;
for (int v = 0; v <= a[u]; v++) best = max(best, dp[u][v]);
dp[u][a[u]] = max(dp[u][a[u]], best + 1);
for (int v = 0; v <= 10; v++) ans = max(ans, dp[u][v]);
for (int to : g[u]) {
for (int v = 0; v <= 10; v++) dp[to][v] = max(dp[to][v], dp[u][v]);
deg[to]--;
if (deg[to] == 0) q.push(to);
}
}
cout << ans;
return 0;
}
P10110 [GESP202312 七级] 商品交易¶
提示1-先看范围
30分做法，\(N\le 10\)、\(M\le 20\)。
70分做法，\(N\le 1000\)、\(M\le 10^{4}\)。
看全部数据范围，\(N\le 10^{5}\)、\(M\le 2\times 10^{5}\)。
小图可以用邻接矩阵搜索，大图要用邻接表。
提示2-价值差会怎样
走过 \(a\to u\to b\)，价值差相加后，中间商品的价值会抵消。
无论走哪条路线，总花费都是 \(v_b-v_a\) 加上交易次数。
提示3-只求最少次数
把每次交易看成一条有向边，用 BFS 求最少边数。
不要把交易当成双向的。
价值差可能很大，用 long long 算答案。
BFS中d[a]为0，其余初始-1。沿一条允许交易的边u到v，第一次到达就得到最少交易次数：
代码-70分-邻接矩阵 BFS
\(O(N^{2}+M)\) 时间，\(O(N^{2})\) 空间。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
long long value[N];
int d[N];
bool g[N][N];
int main() {
int n, m, a, b;
cin >> n >> m >> a >> b;
fill(value, value + (n), 0);
for (int z = 0; z < n; z++) cin >> value[z];
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
g[u][v] = true;
}
fill(d, d + (n), -1);
queue<int> q;
d[a] = 0;
q.push(a);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v = 0; v < n; v++) if (g[u][v] && d[v] == -1) {
d[v] = d[u] + 1;
q.push(v);
}
}
if (d[b] == -1) cout << "No solution";
else cout << value[b] - value[a] + d[b];
return 0;
}
代码-满分-邻接表 BFS
\(O(N+M)\) 时间与空间。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int> g[N];
long long value[N];
int d[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, a, b;
cin >> n >> m >> a >> b;
fill(value, value + (n), 0);
for (int z = 0; z < n; z++) cin >> value[z];
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
g[u].push_back(v);
}
fill(d, d + (n), -1);
queue<int> q;
d[a] = 0;
q.push(a);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : g[u]) if (d[v] == -1) {
d[v] = d[u] + 1;
q.push(v);
}
}
if (d[b] == -1) cout << "No solution";
else cout << value[b] - value[a] + d[b];
return 0;
}
P10111 [GESP202312 七级] 纸牌游戏¶
提示1-先看范围
30分做法，\(N\le 15\)。
60分做法，\(N\le 100\)。
看全部数据范围，\(N\le 1000\)，\(a_{i},b_{i}\le 10^{6}\)。
逐轮枚举三种牌有 \(3^{N}\) 种计划，\(N=15\) 时可拿部分分。
提示2-罚分跟什么有关
换牌扣多少分，取决于这是第几次换牌，不是当前第几轮。
设 \(\operatorname{dp}_{t,c}\) 为上一轮结束时，换过 \(t\) 次、最后出 \(c\) 的最高分。
提示3-继续还是换牌
继续出 \(c\)，不增加换牌次数。
从另一张牌换到 \(c\)，次数加一并扣相应的 \(b\)。
每轮再加上本轮得分。
滚动数组后，时间 \(O(N^{2})\)，空间 \(O(N)\)。
外层已经固定本轮i、旧状态t和last，正在试新牌card。nt是实际换牌总次数，罚的是第nt次的分：
代码-30分-枚举出牌
\(O(3^{N})\) 时间，\(O(N)\) 空间。
#include <bits/stdc++.h>
using namespace std;
int n;
long long a[20], b[20];
int c[20];
long long ans = 0;
long long gain(int i, int card) {
if (card == c[i]) return a[i];
return (card + 2) % 3 == c[i] ? 2 * a[i] : 0;
}
void dfs(int i, int last, int changes, long long score) {
if (i == n) {
ans = max(ans, score);
return;
}
for (int card = 0; card < 3; card++) {
int t = changes + (i > 0 && card != last);
long long cost = t > changes ? b[t] : 0;
dfs(i + 1, card, t, score + gain(i, card) - cost);
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 1; i < n; i++) cin >> b[i];
for (int i = 0; i < n; i++) cin >> c[i];
dfs(0, -1, 0, 0);
cout << ans;
return 0;
}
代码-满分-换牌次数 DP
\(O(N^{2})\) 时间，\(O(N)\) 空间。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
const long long NEG = -(1LL << 60);
long long a[N], b[N], dp[N][3], ndp[N][3];
int c[N];
long long gain(int i, int card) {
if (card == c[i]) return a[i];
return (card + 2) % 3 == c[i] ? 2 * a[i] : 0;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 1; i < n; i++) cin >> b[i];
for (int i = 0; i < n; i++) cin >> c[i];
for (int t = 0; t < n; t++)
for (int card = 0; card < 3; card++) dp[t][card] = NEG;
for (int card = 0; card < 3; card++) dp[0][card] = gain(0, card);
for (int i = 1; i < n; i++) {
for (int t = 0; t < n; t++)
for (int card = 0; card < 3; card++) ndp[t][card] = NEG;
for (int t = 0; t < i; t++) for (int last = 0; last < 3; last++) {
if (dp[t][last] == NEG) continue;
for (int card = 0; card < 3; card++) {
int nt = t + (card != last);
long long cost = card != last ? b[nt] : 0;
ndp[nt][card] = max(ndp[nt][card], dp[t][last] + gain(i, card) - cost);
}
}
for (int t = 0; t < n; t++)
for (int card = 0; card < 3; card++) dp[t][card] = ndp[t][card];
}
long long ans = 0;
for (int t = 0; t < n; t++)
for (int card = 0; card < 3; card++) ans = max(ans, dp[t][card]);
cout << ans;
return 0;
}
P10378 [GESP202403 七级] 交流问题¶
提示1-先看范围
30分做法，\(n\le 17\)、\(m\le 50\)。
60分做法，\(n\le 500\)、\(m\le 2000\)。
看全部数据范围，\(n\le 10^{5}\)、\(m\le 2\times 10^{5}\)。
\(n\le 17\) 时，可以枚举每个人属于哪所学校。
提示2-朋友必须分两边
把交流关系连成无向边。
沿边给两端染不同颜色，得到每个连通块的两类同学。
题目保证交流合法，不会出现染色矛盾。
提示3-每块可以单独翻转
一个连通块两种颜色有 \(x\)、\(y\) 人。
哪种颜色是 \(B\) 校，都有可能。
最少贡献 \(\min(x,y)\)，最多贡献 \(\max(x,y)\)。
各块相加。
孤立点也要单独处理。
一个连通块染色完成后，cnt[0]和cnt[1]记录两边人数。给哪边贴B校标签可以独立选择：
代码-30分-枚举学校
\(O(2^{n}(n+m))\) 时间，\(O(n+m)\) 空间。
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
pair<int, int> edges[N];
int main() {
int n, m;
cin >> n >> m;
for (int z = 0; z < m; z++) {
int &u = edges[z].first, &v = edges[z].second;
cin >> u >> v;
u--;
v--;
}
int low = n, high = 0;
for (int mask = 0; mask < (1 << n); mask++) {
bool ok = true;
for (int z = 0; z < m; z++) {
int u = edges[z].first, v = edges[z].second;
if (((mask >> u) & 1) == ((mask >> v) & 1)) {
ok = false;
break;
}
}
if (!ok) continue;
int cnt = 0;
for (int i = 0; i < n; i++) cnt += (mask >> i) & 1;
low = min(low, cnt);
high = max(high, cnt);
}
cout << low << ' ' << high;
return 0;
}
代码-满分-二分图染色
\(O(n+m)\) 时间与空间。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int> g[N];
int color[N];
int cnt[2];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
fill(color, color + (n + 1), -1);
int low = 0, high = 0;
for (int s = 1; s <= n; s++) if (color[s] == -1) {
cnt[0] = cnt[1] = 0;
queue<int> q;
q.push(s);
color[s] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
cnt[color[u]]++;
for (int v : g[u]) if (color[v] == -1) {
color[v] = color[u] ^ 1;
q.push(v);
}
}
low += min(cnt[0], cnt[1]);
high += max(cnt[0], cnt[1]);
}
cout << low << ' ' << high;
return 0;
}
P10379 [GESP202403 七级] 俄罗斯方块¶
提示1-先看特殊性质
30分做法，\(n,m\le 20\)，方块不超过 \(5\times 5\)。
另外30分做法，\(n,m\le 500\)，方块都是横条或竖条。
看全部数据范围，\(n,m\le 500\)。
条形方块只需记录高和宽。
长度相同的横条、竖条仍是不同形状。
提示2-先找到每一块
用 BFS 找出同色连通块，收集所有格子的坐标。
平移以后，坐标会一起变化。
怎样让同一种形状得到同一份记录？
提示3-让坐标从零开始
分别减去最小行号、最小列号，再排序。
把坐标列表放进 set 去重。
每块格子数不同，坐标列表保留vector；形状去重保留set，比开一个大二维数组存所有形状更直接。
这样只消除了平移，颜色不用记录，旋转后的形状不会被误合并。
cells收集当前块的坐标，up、l分别是最小行、最小列。先统一平移，再排序，位置不同但形状相同的块就得到相同记录：
代码-30分-条形子任务
令 \(B\) 为方块数，时间 \(O(nm+B\log B)\)，空间 \(O(nm)\)。仅适用于条形子任务。
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int a[N][N];
bool vis[N][N];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) cin >> a[i][j];
}
set<pair<int, int>> shapes;
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (!vis[i][j]) {
int up = i, down = i, l = j, r = j;
queue<pair<int, int>> q;
q.push({i, j});
vis[i][j] = true;
while (!q.empty()) {
int x = q.front().first, y = q.front().second;
q.pop();
up = min(up, x);
down = max(down, x);
l = min(l, y);
r = max(r, y);
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && a[nx][ny] == a[i][j]) {
vis[nx][ny] = true;
q.push({nx, ny});
}
}
}
shapes.insert({down - up + 1, r - l + 1});
}
cout << shapes.size();
return 0;
}
代码-满分-坐标归一化
令 \(K=nm\)，时间 \(O(K\log K)\)，空间 \(O(K)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int a[N][N];
bool vis[N][N];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) cin >> a[i][j];
}
set<vector<pair<int, int>>> shapes;
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (!vis[i][j]) {
vector<pair<int, int>> cells;
int up = i, l = j;
queue<pair<int, int>> q;
q.push({i, j});
vis[i][j] = true;
while (!q.empty()) {
int x = q.front().first, y = q.front().second;
q.pop();
cells.push_back({x, y});
up = min(up, x);
l = min(l, y);
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && a[nx][ny] == a[i][j]) {
vis[nx][ny] = true;
q.push({nx, ny});
}
}
}
for (int k = 0; k < (int)cells.size(); k++) {
cells[k].first -= up;
cells[k].second -= l;
}
sort(cells.begin(), cells.end());
shapes.insert(cells);
}
cout << shapes.size();
return 0;
}
P10723 [GESP202406 七级] 黑白翻转¶
提示1-先看特殊性质
30分做法，树是一条链。
另外30分做法，恰有两个黑点。
看全部数据范围，\(n\le 10^{5}\)。
链上只需填满最左、最右黑点之间的白点。
两个黑点时，只需填满它们之间的路径。
提示2-哪些白点用不到
原来的黑点不能删除，它们之间的路径也必须保留。
没有黑点的末端分支，可以整个剪掉。
提示3-不断剪白色叶子
把白色叶子放入队列，删除后，新的白色叶子继续入队。
剩下的白点就是必须翻转的点。
如果原来一个黑点也没有，翻转任意一个点即可，答案为 1。
删除一个白叶子u后，只改变未删除邻居v的度数。v也变成白叶子时马上入队并标记，避免重复入队：
代码-30分-链形子任务
\(O(n)\) 时间与空间。按树上的真实顺序找两端黑点。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int> g[N];
int a[N];
int main() {
int n;
cin >> n;
fill(a, a + (n + 1), 0);
int black = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
black += a[i];
}
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
if (!black) {
cout << 1;
return 0;
}
int u = 1;
while (g[u].size() > 1) u++;
int prev = 0, pos = 0, first = -1, last = -1;
while (u) {
if (a[u]) {
if (first == -1) first = pos;
last = pos;
}
int next = 0;
for (int v : g[u]) if (v != prev) next = v;
prev = u;
u = next;
pos++;
}
cout << last - first + 1 - black;
return 0;
}
代码-满分-剪去白色叶子
\(O(n)\) 时间与空间。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int> g[N];
int a[N], deg[N];
bool removed[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
fill(a, a + (n + 1), 0);
fill(deg, deg + (n + 1), 0);
fill(removed, removed + (n + 1), 0);
int black = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
black += a[i];
}
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
deg[u]++;
deg[v]++;
}
if (!black) {
cout << 1;
return 0;
}
queue<int> q;
for (int u = 1; u <= n; u++) if (!a[u] && deg[u] <= 1) {
q.push(u);
removed[u] = true;
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : g[u]) if (!removed[v]) {
deg[v]--;
if (!a[v] && deg[v] <= 1) {
removed[v] = true;
q.push(v);
}
}
}
int ans = 0;
for (int u = 1; u <= n; u++) if (!removed[u] && !a[u]) ans++;
cout << ans;
return 0;
}
P10724 [GESP202406 七级] 区间乘积¶
提示1-先看范围
20分做法，\(n\le 10^{5}\)，\(a_{i}\le 2\)。
另外40分做法，\(n\le 100\)，\(a_{i}\le 30\)。
看全部数据范围，\(n\le 10^{5}\)，\(a_{i}\le 30\)。
乘积很快会溢出。
平方数的每个质因子，出现次数有什么特点？
提示2-只记录奇偶
平方数中，每个质因子的次数都是偶数。
30 以内只有 10 个质数，可用 10 个二进制位记录奇偶。
区间相乘，对应这些位做异或。
只有 1、2 时，只需记录 2 的次数奇偶。
提示3-变成前缀计数
区间异或为 0，等价于两端的前缀异或相同。
边扫描边统计相同前缀出现次数。
先放入空前缀 0，答案用 long long。
masks[x]记录x的质因数次数奇偶。读到一个新数时，先统计旧前缀，再把新前缀加入计数：
代码-40分-小范围子任务
\(O(n^{2}+10n)\) 时间，\(O(n)\) 空间；仅用于 \(n\le 100\) 的子任务。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N];
int prime[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int getmask(int x) {
int mask = 0;
for (int i = 0; i < 10; i++) while (x % prime[i] == 0) {
x /= prime[i];
mask ^= 1 << i;
}
return mask;
}
int main() {
int n;
cin >> n;
fill(a, a + (n), 0);
for (int z = 0; z < n; z++) {
int &x = a[z];
cin >> x;
x = getmask(x);
}
long long ans = 0;
for (int l = 0; l < n; l++) {
int mask = 0;
for (int r = l; r < n; r++) {
mask ^= a[r];
ans += mask == 0;
}
}
cout << ans;
return 0;
}
代码-满分-前缀异或
\(O(10n)\) 时间，\(O(2^{10})\) 空间。
#include <bits/stdc++.h>
using namespace std;
const int N = 1024;
int prime[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int masks[31];
long long cnt[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
for (int x = 1; x <= 30; x++) {
int v = x;
for (int i = 0; i < 10; i++) while (v % prime[i] == 0) {
v /= prime[i];
masks[x] ^= 1 << i;
}
}
int n, prefix = 0;
cin >> n;
long long ans = 0;
cnt[0] = 1;
for (int i = 0, x; i < n; i++) {
cin >> x;
prefix ^= masks[x];
ans += cnt[prefix];
cnt[prefix]++;
}
cout << ans;
return 0;
}
P11248 [GESP202409 七级] 矩阵移动¶
原题解由陈奕涵提供，以下整理了提示与示范代码。
提示1-先看范围
30分做法，\(n,m\le 10\)，\(x=1\)。
另外30分做法，\(n,m\le 500\)，\(x\le 30\)。
看全部数据范围，\(n,m\le500\)，\(x\le 300\)，所有网格面积之和\(\le 2.5\times 10^{5}\)。
小网格可以枚举路径，记下经过多少个 1 和 ?。
提示2-问号不一定全选
设 \(\operatorname{dp}_{i,j,k}\) 为走到 \((i,j)\)、恰好修改 \(k\) 个问号时的最高分。
遇到 ? 可以不改，也可以花一次修改机会加一分。
不要把“经过的问号数”限制为 \(x\)。
提示3-从哪里走来
每个格子只会从上方或左方走来，取较大的分数，再处理当前字符。
按行滚动，最后取所有 \(k\le x\) 的最大值。
不可达状态要设成负无穷。
处理格子(i,j)和已修改k次的状态，dp[j]来自上方，dp[j-1]来自左方。先合并前驱，再把本格的贡献加上：
代码-30分-枚举路径
\(O(2^{n+m})\) 时间，\(O(n+m+nm)\) 空间。仅用于小网格子任务。
#include <bits/stdc++.h>
using namespace std;
int n, m, x, ans;
string g[15];
void dfs(int i, int j, int ones, int questions) {
ones += g[i][j] == '1';
questions += g[i][j] == '?';
if (i == n - 1 && j == m - 1) {
ans = max(ans, ones + min(x, questions));
return;
}
if (i + 1 < n) dfs(i + 1, j, ones, questions);
if (j + 1 < m) dfs(i, j + 1, ones, questions);
}
int main() {
int t;
cin >> t;
while (t--) {
cin >> n >> m >> x;
for (int i = 0; i < n; i++) cin >> g[i];
ans = 0;
dfs(0, 0, 0, 0);
cout << ans;
if (t > 0) cout << '\n';
}
return 0;
}
代码-满分-滚动数组
\(O(nmx)\) 时间，\(O(mx+nm)\) 空间。
#include <bits/stdc++.h>
using namespace std;
const int NEG = -1000000000;
const int N = 505, M = 305;
string g[N];
int dp[N][M], cur[M];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n, m, x;
cin >> n >> m >> x;
x = min(x, n + m - 1);
fill(g, g + (n), string());
for (int z = 0; z < n; z++) cin >> g[z];
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= x; k++) dp[j][k] = NEG;
}
dp[1][0] = 0; // 第一格上方的虚拟起点。
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 0; k <= x; k++) cur[k] = NEG;
for (int k = 0; k <= x; k++) {
int best = max(dp[j][k], dp[j - 1][k]);
if (best == NEG) continue;
cur[k] = max(cur[k], best + (g[i - 1][j - 1] == '1'));
if (g[i - 1][j - 1] == '?' && k < x)
cur[k + 1] = max(cur[k + 1], best + 1);
}
for (int k = 0; k <= x; k++) dp[j][k] = cur[k];
}
}
int ans = 0;
for (int k = 0; k <= x; k++) ans = max(ans, dp[m][k]);
cout << ans;
if (t > 0) cout << '\n';
}
return 0;
}
P11249 [GESP202409 七级] 小杨寻宝¶
原题解由陈奕涵提供，以下整理了提示与示范代码。
提示1-先看范围
20分做法，\(n\le 5\)。
另外20分做法，\(n\le 1000\)。
看全部数据范围，\(n\le 10^{5}\)，每个输入最多 10 组。
小范围可以枚举起点，搜索走出的路径。
题目保证至少有一个宝物。
提示2-走过的路是什么形状
树上没有环。
走进一个分支后，原路返回会重复边，所以走过的只能是一条简单路径。
问题变成：所有宝物能否放在同一条路径上？
提示3-剪去无关的叶子
反复删除没有宝物的叶子。
留下的树，是连接所有宝物所必需的部分。
如果还有度数超过 2 的点，就必须走岔路，答案为 No。
否则是路径，答案为 Yes。
剪完无宝物叶子后，removed为假才是剩下的树。只要其中有一个点的度数超过2，就无法用一条路经过全部宝物：
代码-40分-枚举路径
\(O(n^{2})\) 时间，\(O(n)\) 空间。按树上每个起点搜索，也适用于 \(n\le 1000\) 的子任务。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int> g[N];
int a[N];
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
fill(a, a + (n + 1), 0);
int total = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
total += a[i];
}
for (int z = 0; z < n + 1; z++) g[z].clear();
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
bool ok = false;
for (int s = 1; s <= n && !ok; s++) {
// 栈内记录当前点、父亲、路径上的宝物数。
stack<array<int, 3>> st;
st.push({s, 0, a[s]});
while (!st.empty()) {
array<int, 3> state = st.top();
int u = state[0], p = state[1], cnt = state[2];
st.pop();
if (cnt == total) ok = true;
for (int v : g[u]) if (v != p) st.push({v, u, cnt + a[v]});
}
}
cout << (ok ? "Yes" : "No");
if (t > 0) cout << '\n';
}
return 0;
}
代码-满分-剪叶子
\(O(n)\) 时间与空间，每组数据单独处理。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int> g[N];
int a[N], deg[N];
bool removed[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
fill(a, a + (n + 1), 0);
fill(deg, deg + (n + 1), 0);
for (int z = 0; z < n + 1; z++) g[z].clear();
fill(removed, removed + (n + 1), 0);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
deg[u]++;
deg[v]++;
}
queue<int> q;
for (int u = 1; u <= n; u++) if (!a[u] && deg[u] <= 1) {
removed[u] = true;
q.push(u);
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : g[u]) if (!removed[v]) {
deg[v]--;
if (!a[v] && deg[v] <= 1) {
removed[v] = true;
q.push(v);
}
}
}
bool ok = true;
for (int u = 1; u <= n; u++) if (!removed[u] && deg[u] > 2) ok = false;
cout << (ok ? "Yes" : "No");
if (t > 0) cout << '\n';
}
return 0;
}
P11377 [GESP202412 七级] 武器购买¶
提示1-先看特殊性质
20分做法，\(n\le 10\)，强度、费用都为 1。
另外20分做法，\(n\le 100\)，费用全为 1，\(Q=2\)。
两组数据的费用都为 1：先选强度最大的武器，达到 \(P\) 就停止。
全部 \(n\le 100\)，\(P,Q\le 5\times 10^{4}\)。
提示2-预算不大
总强度可能很大，预算 \(Q\) 却不超过 50000。
设 \(\operatorname{dp}_{c}\) 为恰好花 \(c\) 元，能获得的最大强度。
每件武器都可以选或不选。
提示3-每件只能用一次
费用从大到小更新，避免同一件武器重复购买。
最后从小到大找 \(\operatorname{dp}_{c}\ge P\) 的费用。
找不到就输出 -1。
读到强度p、费用cost的一件武器时，费用c倒序更新。dp[c-cost]为-1表示没有这样的购买方案：
代码-40分-单位费用子任务
\(O(n\log n)\) 时间，\(O(n)\) 空间。费用均为 1 时正确，覆盖前两个子任务；不适用于一般费用。
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int p[N];
int main() {
int t;
cin >> t;
while (t--) {
int n, P, Q;
cin >> n >> P >> Q;
fill(p, p + (n), 0);
for (int i = 0, cost; i < n; i++) cin >> p[i] >> cost;
sort(p, p + (n));
int sum = 0, ans = -1;
for (int i = n - 1; i >= 0; i--) {
sum += p[i];
int cost = n - i;
if (cost > Q) break;
if (sum >= P) {
ans = cost;
break;
}
}
cout << ans;
if (t > 0) cout << '\n';
}
return 0;
}
代码-满分-01 背包
\(O(nQ)\) 时间，\(O(Q)\) 空间。
#include <bits/stdc++.h>
using namespace std;
const int N = 50005;
int dp[N];
int main() {
int t;
cin >> t;
while (t--) {
int n, P, Q;
cin >> n >> P >> Q;
fill(dp, dp + (Q + 1), -1);
dp[0] = 0;
for (int i = 0, p, cost; i < n; i++) {
cin >> p >> cost;
for (int c = Q; c >= cost; c--) if (dp[c - cost] != -1)
dp[c] = max(dp[c], dp[c - cost] + p);
}
int ans = -1;
for (int c = 0; c <= Q; c++) if (dp[c] >= P) {
ans = c;
break;
}
cout << ans;
if (t > 0) cout << '\n';
}
return 0;
}
P11378 [GESP202412 七级] 燃烧¶
提示1-先看范围
20分做法，\(n\le 10\)。
另外20分做法，\(n\le 100\)。
看全部数据范围，\(n\le 10^{5}\)，点权\(\le 10^{6}\)。
小范围枚举起点，每次搜索，时间 \(O(n^{2})\)。
相等权值不能传火。
提示2-从小权值开始算
设 \(f_{u}\) 为从 \(u\) 点火能烧到的点数。
\(u\) 能烧到哪些邻居？只能是权值更小的邻居，先把它们的 \(f\) 算好。
提示3-为什么可以直接相加
删掉 \(u\) 后，各个邻居属于不同分支，它们烧到的点不会重叠。
所以 \(f_u\) 等于 \(1\) 加上所有更小邻居的 \(f\) 之和。
按权值升序计算，取最大值。
order已按点权升序排好，u是当前点。先算自己，再加更小邻居的完整答案；相等时不能传火：
代码-40分-枚举起点
\(O(n^{2})\) 时间，\(O(n)\) 空间。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int> g[N];
int a[N];
int main() {
int n;
cin >> n;
fill(a, a + (n + 1), 0);
for (int u = 1; u <= n; u++) cin >> a[u];
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
int ans = 0;
for (int s = 1; s <= n; s++) {
stack<int> st;
st.push(s);
int cnt = 0;
while (!st.empty()) {
int u = st.top();
st.pop();
cnt++;
for (int v : g[u]) if (a[v] < a[u]) st.push(v);
}
ans = max(ans, cnt);
}
cout << ans;
return 0;
}
代码-满分-按权值排序 DP
\(O(n\log n)\) 时间，\(O(n)\) 空间。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int> g[N];
int a[N], order[N], f[N];
bool cmp(int u, int v) {
return a[u] < a[v];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for (int u = 1; u <= n; u++) cin >> a[u];
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 0; i < n; i++) order[i] = i + 1;
sort(order, order + n, cmp);
int ans = 1;
for (int i = 0; i < n; i++) {
int u = order[i];
f[u] = 1;
for (int v : g[u]) if (a[v] < a[u]) f[u] += f[v];
ans = max(ans, f[u]);
}
cout << ans;
return 0;
}
P11964 [GESP202503 七级] 图上移动¶
提示1-先看范围
20分做法，\(k=1\)。
另外20分做法，\(n,m\le 50\)。
看全部数据范围，\(n,m\le 500\)，\(k\le 20\)，采用捆绑测试。
\(k=1\) 时统计不同邻居，小图可以逐个起点做布尔 DP。
提示2-恰好，不是至多
\(\operatorname{cur}_{u}\) 表示这一轮能否在 \(u\)。
下一轮把所有相邻点标记为可达。
每轮先清空新数组。
同一个点只计一次，不要用永久 visited 禁止再次到达。
提示3-同时算很多起点
用 bitset 保存一个点当前可以到达的点集。
bitset是固定长度的二进制集合，set(i)标记编号i，按位或合并集合，count()统计标记数。集合本身固定为500位，外层也使用静态数组。
走多一步的点集，是所有邻居上一轮点集的并集。
无向图中两边都要合并。
下面是基础布尔DP中的一条无向边u、v，cur记恰好走了上一轮步数的点。ndp必须每轮先清空，不能在cur上直接改：
代码-满分-基础布尔 DP
\(O(nk(n+m))\) 时间，\(O(n+m)\) 空间。\(n,m\le 500\)、\(k\le 20\) 时可处理完整范围；下面的 bitset 版本进一步加速。
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
bool cur[N];
bool ndp[N];
pair<int, int> edges[N];
int main() {
int n, m, k;
cin >> n >> m >> k;
for (int z = 0; z < m; z++) {
int &u = edges[z].first, &v = edges[z].second;
cin >> u >> v;
u--;
v--;
}
for (int s = 0; s < n; s++) {
fill(cur, cur + (n), 0);
fill(ndp, ndp + (n), 0);
cur[s] = true;
for (int step = 1; step <= k; step++) {
fill(ndp, ndp + (n), false);
for (int z = 0; z < m; z++) {
int u = edges[z].first, v = edges[z].second;
if (cur[u]) ndp[v] = true;
if (cur[v]) ndp[u] = true;
}
for (int z = 0; z < n; z++) cur[z] = ndp[z];
cout << count(cur, cur + (n), true);
if (step < k) cout << ' ';
else if (s + 1 < n) cout << '\n';
}
}
return 0;
}
代码-满分-bitset 集合 DP
\(O\left(k(n+m)\left\lceil\frac{n}{W}\right\rceil+nk\right)\) 时间，\(O\left(n\left\lceil\frac{n}{W}\right\rceil+nk+m\right)\) 个机器字，\(W\) 为机器字长。
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
pair<int, int> edges[N];
int ans[N][25];
bitset<500> cur[N], ndp[N];
int main() {
int n, m, k;
cin >> n >> m >> k;
for (int z = 0; z < m; z++) {
int &u = edges[z].first, &v = edges[z].second;
cin >> u >> v;
u--;
v--;
}
// 每一位表示一个点是否可达，固定五百位，用静态数组保存各点的集合。
for (int i = 0; i < n; i++) cur[i].set(i);
for (int step = 0; step < k; step++) {
for (int i = 0; i < n; i++) ndp[i].reset();
for (int z = 0; z < m; z++) {
int u = edges[z].first, v = edges[z].second;
ndp[u] |= cur[v];
ndp[v] |= cur[u];
}
for (int i = 0; i < n; i++) cur[i] = ndp[i];
for (int i = 0; i < n; i++) ans[i][step] = cur[i].count();
}
for (int i = 0; i < n; i++) {
for (int step = 0; step < k; step++) {
cout << ans[i][step];
if (step + 1 < k) cout << ' ';
}
if (i + 1 < n) cout << '\n';
}
return 0;
}
P11965 [GESP202503 七级] 等价消除¶
提示1-先看范围
20分做法，只有 \(a\)、\(b\)。
另外20分做法，长度\(\le 2000\)。
看全部数据范围，长度\(\le 2\times 10^{5}\)，采用捆绑测试。
能删空，就说明每种字母的数量都是什么数？
提示2-记录字母次数的奇偶
每种字母出现偶数次，就能两两删光。
用 26 个二进制位记录奇偶。
只有 \(a\)、\(b\) 时，状态仅有 4 种。
小范围可以枚举区间并维护这个状态。
提示3-相同的前缀可以配对
两个前缀状态相同，中间子串每种字母的次数就是偶数。
用哈希表统计之前出现过多少个相同状态，先放入空前缀。
理论上有 \(2^{26}\) 种状态，但实际前缀至多 \(n+1\) 个，因此这里保留哈希表，避免开很大的静态计数数组。
答案用 long long。
mask初始为0，cnt[0]先放一个空前缀。当前字母改变它对应位的奇偶，计数顺序与区间乘积相同：
代码-20分-长度子任务
\(O(n^{2})\) 时间，\(O(n)\) 空间。仅用于长度\(\le 2000\) 的子任务。
代码-满分-前缀状态计数
哈希表期望 \(O(n)\) 时间，\(O(n)\) 空间。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
string s;
cin >> n >> s;
unordered_map<int, long long> cnt;
cnt.reserve(2 * n + 1);
cnt[0] = 1;
int mask = 0;
long long ans = 0;
for (char c : s) {
mask ^= 1 << (c - 'a');
ans += cnt[mask];
cnt[mask]++;
}
cout << ans;
return 0;
}
P13017 [GESP202506 七级] 线图¶
提示1-先看范围
60分做法，\(n,m\le 500\)。
看全部数据范围，\(n,m\le 10^{5}\)。
小范围可以枚举两条边，检查是否有公共端点。
提示2-围着一个点数
原图中一个点连接了 \(d\) 条边。
任意选两条，都会在线图中形成一条边。
这个点贡献 \(\frac{d(d-1)}{2}\)。
把每个点的贡献相加。
提示3-会不会重复
没有重边，两条不同边最多共用一个端点，所以不会重复统计。
答案可能超过 int，用 long long，乘法前也要转成 long long。
读边时，两端度数都加一。处理完输入后，对每个点u累加它能配成的边对；乘法先提升到long long：
代码-60分-枚举边对
\(O(n+m^{2})\) 时间，\(O(m)\) 空间。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
pair<int, int> e[N];
int main() {
int n, m;
cin >> n >> m;
for (int z = 0; z < m; z++) cin >> e[z].first >> e[z].second;
long long ans = 0;
for (int i = 0; i < m; i++) for (int j = i + 1; j < m; j++) {
int u = e[i].first, v = e[i].second;
int x = e[j].first, y = e[j].second;
ans += u == x || u == y || v == x || v == y;
}
cout << ans;
return 0;
}
代码-满分-统计度数
\(O(n+m)\) 时间，\(O(n)\) 空间。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int deg[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
fill(deg, deg + (n + 1), 0);
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
deg[u]++;
deg[v]++;
}
long long ans = 0;
for (int u = 1; u <= n; u++) ans += 1LL * deg[u] * (deg[u] - 1) / 2;
cout << ans;
return 0;
}
P13018 [GESP202506 七级] 调味平衡¶
提示1-先看范围
40分做法，\(n\le 10\)，\(a_{i},b_{i}\le 10\)。
另外20分做法，\(n\le 50\)，\(a_{i},b_{i}\le 10\)。
看全部数据范围，\(n\le 100\)，\(a_{i},b_{i}\le 500\)。
\(n\le 10\) 可以枚举子集。
后面的范围要把选法合并。
提示2-只关心酸甜差
选一份食材，酸甜差增加 \(a_{i}-b_{i}\)，总味道增加 \(a_{i}+b_{i}\)。
设 \(\operatorname{dp}_{d}\) 为酸甜差为 \(d\) 时的最大总味道，最后取 \(\operatorname{dp}_{0}\)。
提示3-差值也可能是负数
所有差值的绝对值之和最多 50000，用偏移量存负下标。
每件食材用新数组更新一次，别重复选。
只有 \(\operatorname{dp}_{0}=0\)，其他状态初始不可达。
处理第i份食材时，先把dp复制到ndp表示不选，再从旧dp转移。D是偏移量，d和nd分别为原差值和新差值：
代码-40分-枚举子集
\(O(n2^{n})\) 时间，\(O(n)\) 空间。
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int a[N], b[N];
int main() {
int n;
cin >> n;
fill(a, a + (n), 0);
fill(b, b + (n), 0);
for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
int ans = 0;
for (int mask = 0; mask < (1 << n); mask++) {
int A = 0, B = 0;
for (int i = 0; i < n; i++) if (mask >> i & 1) {
A += a[i];
B += b[i];
}
if (A == B) ans = max(ans, A + B);
}
cout << ans;
return 0;
}
代码-满分-差值背包
令 \(D=\sum_{i=1}^{n}|a_i-b_i|\)，时间 \(O(n(D+1))\)，空间 \(O(D+1)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int NEG = -1000000000;
int a[N], b[N];
int dp[100005];
int ndp[100005];
int main() {
int n;
cin >> n;
fill(a, a + (n), 0);
fill(b, b + (n), 0);
int D = 0;
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i];
D += abs(a[i] - b[i]);
}
fill(dp, dp + (2 * D + 1), NEG);
dp[D] = 0;
for (int i = 0; i < n; i++) {
for (int z = 0; z <= 2 * D; z++) ndp[z] = dp[z];
int delta = a[i] - b[i];
for (int d = -D; d <= D; d++) {
if (dp[d + D] == NEG) continue;
int nd = d + delta;
if (-D <= nd && nd <= D)
ndp[nd + D] = max(ndp[nd + D], dp[d + D] + a[i] + b[i]);
}
for (int z = 0; z < 2 * D + 1; z++) dp[z] = ndp[z];
}
cout << dp[D];
return 0;
}
P14077 [GESP202509 七级] 连通图¶
提示1-先看范围
40分做法，\(n,m\le 100\)。
看全部数据范围，\(n,m\le 10^{5}\)。
先数清楚原图分成了几块。
孤立点也算一块。
提示2-一条边能连接几块
新增一条边，最多让块数减少 1。
若有 \(c\) 个连通块，至少要 \(c-1\) 条边。
任选一块，连向其他各块，就能做到。
提示3-怎样数块
小范围用邻接矩阵 BFS。
大范围用邻接表或并查集。
自环不会连接两块，重复边也不会让答案多减一次。
并查集开始每点独立，blocks为n。把边的两端先找代表；只有代表不同，连通块数才减少一次：
代码-40分-邻接矩阵 BFS
\(O(n^{2}+m)\) 时间，\(O(n^{2})\) 空间。
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
bool vis[100005];
bool g[N][N];
int main() {
int n, m;
cin >> n >> m;
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
g[u][v] = g[v][u] = true;
}
fill(vis, vis + (n + 1), 0);
int blocks = 0;
for (int s = 1; s <= n; s++) if (!vis[s]) {
blocks++;
queue<int> q;
q.push(s);
vis[s] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v = 1; v <= n; v++) if (g[u][v] && !vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
cout << blocks - 1;
return 0;
}
代码-满分-并查集
\(O(n+m\alpha(n))\) 时间，\(O(n)\) 空间。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int p[N], sz[N];
int find(int x) {
while (p[x] != x) {
p[x] = p[p[x]];
x = p[x];
}
return x;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i <= n; i++) {
p[i] = i;
sz[i] = 1;
}
int blocks = n;
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
u = find(u);
v = find(v);
if (u == v) continue;
if (sz[u] < sz[v]) swap(u, v);
p[v] = u;
sz[u] += sz[v];
blocks--;
}
cout << blocks - 1;
return 0;
}
P14078 [GESP202509 七级] 金币收集¶
提示1-先看范围
40分做法，\(n\le 8\)。
另外30分做法，\(n,x_{i},t_{i}\le 100\)。
看全部数据范围，\(n\le 10^{5}\)，\(x_{i},t_{i}\le 10^{9}\)。
先按时间排序，小范围枚举前一枚收集的金币，做 \(O(n^{2})\) DP，可覆盖前70分。
提示2-两枚金币能接起来吗
从 \((x_1,t_1)\) 到 \((x_2,t_2)\)，需要 \(x_2\ge x_1\)，且 \(x_2-x_1\le t_2-t_1\)。
把后一个条件移项，变成 \(t_2-x_2\ge t_1-x_1\)。
提示3-变成两个数不下降
令 \(y=t-x\)。
先删掉 \(y<0\) 的金币，因为从起点就赶不到。
按 \(x\) 升序、再按 \(y\) 升序排序，求 \(y\) 的最长不下降子序列。
用 upper_bound，允许相等。
同时同地的多枚金币可以都拿。
tail[len-1]是当前最长长度对应的最小结尾，len初始为0。已按x、y升序后，处理一枚金币的y时找第一个严格大于它的位置：
代码-70分-金币 DP
\(O(n^{2})\) 时间，\(O(n)\) 空间。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
pair<long long, long long> coins[N];
int dp[N];
int main() {
int n;
cin >> n;
int cnt = 0; // coins保存时间和位置。
for (int i = 0; i < n; i++) {
long long x, t;
cin >> x >> t;
if (x <= t) coins[cnt++] = {t, x};
}
sort(coins, coins + cnt);
int sz = cnt, ans = 0;
fill(dp, dp + (sz), 1);
for (int i = 0; i < sz; i++) {
long long t = coins[i].first, x = coins[i].second;
for (int j = 0; j < i; j++) {
long long pt = coins[j].first, px = coins[j].second;
if (x >= px && x - px <= t - pt) dp[i] = max(dp[i], dp[j] + 1);
}
ans = max(ans, dp[i]);
}
cout << ans;
return 0;
}
代码-满分-最长不下降子序列
\(O(n\log n)\) 时间，\(O(n)\) 空间。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
pair<long long, long long> coins[N];
long long tail[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int cnt = 0;
for (int i = 0; i < n; i++) {
long long x, t;
cin >> x >> t;
if (t >= x) coins[cnt++] = {x, t - x};
}
sort(coins, coins + cnt);
int len = 0;
for (int i = 0; i < cnt; i++) {
long long y = coins[i].second;
int pos = upper_bound(tail, tail + len, y) - tail; // 找第一个大于y的位置，允许相等。
tail[pos] = y;
if (pos == len) len++;
}
cout << len;
return 0;
}
P14921 [GESP202512 七级] 城市规划¶
提示1-先看范围
40分做法，\(n\le 300\)。
看全部数据范围，\(n,m\le 2000\)。
Floyd 的 \(O(n^{3})\) 适合小范围。
大图边很少，而且每条边长度都是 1。
提示2-每个城市都试一次
从一个城市 BFS，就能求出它到其他城市的最短距离。
其中最大的距离，就是这个城市的难度。
提示3-处理并列
按编号从小到大枚举起点。
只有难度严格变小时才更新答案。
总时间 \(O(n(n+m))\)，这里约是千万级操作，能处理完整范围。
从候选城市s做完BFS后，最大距离就是score。按编号升序试s，只有严格变小才更新，才能保留并列中的最小编号：
代码-40分-Floyd
\(O(n^{3}+m)\) 时间，\(O(n^{2})\) 空间。
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000;
const int N = 305;
int d[N][N];
int main() {
int n, m;
cin >> n >> m;
for (int u = 1; u <= n; u++) {
for (int v = 1; v <= n; v++) d[u][v] = INF;
}
for (int u = 1; u <= n; u++) d[u][u] = 0;
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
d[u][v] = min(d[u][v], 1);
d[v][u] = min(d[v][u], 1);
}
for (int k = 1; k <= n; k++) for (int u = 1; u <= n; u++)
for (int v = 1; v <= n; v++) d[u][v] = min(d[u][v], d[u][k] + d[k][v]);
int best = INF, ans = 1;
for (int u = 1; u <= n; u++) {
int score = 0;
for (int v = 1; v <= n; v++) score = max(score, d[u][v]);
if (score < best) {
best = score;
ans = u;
}
}
cout << ans;
return 0;
}
代码-满分-逐点 BFS
\(O(n(n+m))\) 时间，\(O(n+m)\) 空间。
#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
vector<int> g[N];
int d[N];
int main() {
int n, m;
cin >> n >> m;
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
int best = n + 1, ans = 1;
for (int s = 1; s <= n; s++) {
fill(d, d + (n + 1), -1);
queue<int> q;
d[s] = 0;
q.push(s);
int score = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
score = max(score, d[u]);
for (int v : g[u]) if (d[v] == -1) {
d[v] = d[u] + 1;
q.push(v);
}
}
if (score < best) {
best = score;
ans = s;
}
}
cout << ans;
return 0;
}
P14922 [GESP202512 七级] 学习小组¶
提示1-先看特殊性质
40分做法，所有 \(c_{i}=0\)。
看全部数据范围，\(n\le 300\)，\(a_{i},c_{i}\le 10^{4}\)。
\(c\) 全为 0 时，只需考虑每组人数。
设 \(f_{i}\) 为分完 \(i\) 人的最高分，枚举最后一组人数即可。
提示2-哪些组能贡献差值
单人组的最大值和最小值相同，差值为 0。
假设有 \(q\) 个至少两人的小组，最多能得到多少差值之和？
提示3-让两头的人配成组
把 \(c\) 排序。
用最大的 \(q\) 人当各组最大值，最小的 \(q\) 人当各组最小值。
其他人填进这些组或单独成组，不会改变差值。
差值之和就是最大的 \(q\) 个 \(c\) 之和减去最小的 \(q\) 个 \(c\) 之和。
提示4-还要决定每组人数
设 \(\operatorname{dp}_{i,q}\) 为分完 \(i\) 人、其中 \(q\) 组至少有两人时，基础分的最大值。
枚举最后一组人数 \(k\)，加 \(a_{k}\)。
\(k\ge 2\) 时 \(q\) 加一。
最后加上 \(q\) 对极值的差值，取最大值。
正在算i人、q个多人组，枚举最后一组人数k。若k至少为2，前面就少一个多人组；前态必须可达：
代码-40分-只算基础分
\(O(n^{2})\) 时间，\(O(n)\) 空间。仅适用于所有 \(c_{i}=0\) 的子任务。
#include <bits/stdc++.h>
using namespace std;
const int N = 305;
int c[N], a[N], dp[N];
int main() {
int n;
cin >> n;
fill(c, c + (n), 0);
fill(a, a + (n + 1), 0);
fill(dp, dp + (n + 1), 0);
for (int i = 0; i < n; i++) cin >> c[i];
for (int k = 1; k <= n; k++) cin >> a[k];
for (int i = 1; i <= n; i++)
for (int k = 1; k <= i; k++) dp[i] = max(dp[i], dp[i - k] + a[k]);
cout << dp[n];
return 0;
}
代码-满分-人数与组数 DP
\(O(n^{3})\) 时间，\(O(n^{2})\) 空间。
#include <bits/stdc++.h>
using namespace std;
const long long NEG = -(1LL << 60);
const int N = 305;
int c[N], a[N];
long long dp[N][N];
int main() {
int n;
cin >> n;
fill(c, c + (n), 0);
fill(a, a + (n + 1), 0);
for (int i = 0; i < n; i++) cin >> c[i];
for (int k = 1; k <= n; k++) cin >> a[k];
sort(c, c + (n));
for (int i = 0; i <= n; i++) {
for (int q = 0; q <= n / 2; q++) dp[i][q] = NEG;
}
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int q = 0; q <= i / 2; q++) {
for (int k = 1; k <= i; k++) {
int last = q - (k >= 2);
if (last < 0 || last > (i - k) / 2) continue;
if (dp[i - k][last] != NEG)
dp[i][q] = max(dp[i][q], dp[i - k][last] + a[k]);
}
}
}
long long ans = dp[n][0], bonus = 0;
for (int q = 1; q <= n / 2; q++) {
bonus += c[n - q] - c[q - 1];
ans = max(ans, dp[n][q] + bonus);
}
cout << ans;
return 0;
}
P15802 [GESP202603 七级] 拆分¶
提示1-先看范围
40分做法，\(n\le 50\)。
看全部数据范围，\(n\le 10^{6}\)，最多 \(10^{4}\) 组。
小范围用 DP：枚举拆出的第一份 \(k\)，乘上剩下部分的最佳乘积。
先比较真实乘积，最后才取模。
提示2-大数拆小会更好吗
一份 \(k\ge 5\) 时，拆成 3 和 \(k-3\)，乘积会变大。
1 通常不划算，4 可以拆成 \(2+2\)。
所以重点考虑 2 和 3。
三个 2 不如两个 3。
提示3-尽量用 3，处理余数
\(n\le 3\) 时不拆。
其他情况尽量拆成 3。
余 1 时，把最后的 \(3+1\) 改成 \(2+2\)。
余 2 时保留一个 2。
用快速幂计算取模结果。
余1时不能留一个单独的1，我把最后一个3和这个1合成4。这里power是按模快速幂：
代码-40分-乘积 DP
预处理 \(O(50^{2})\)，每组 \(O(1)\)；空间 \(O(50)\)。\(n\le 50\) 的真实最大乘积能放进 long long。
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000000LL;
long long dp[55];
int main() {
dp[0] = 1;
for (int n = 1; n <= 50; n++)
for (int k = 1; k <= n; k++) dp[n] = max(dp[n], k * dp[n - k]);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << dp[n] % MOD;
if (t > 0) cout << '\n';
}
return 0;
}
代码-满分-贪心与快速幂
每组 \(O(\log n)\) 时间，\(O(1)\) 空间。
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000000LL;
long long power(long long a, int b) {
long long result = 1;
while (b) {
if (b & 1) result = result * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return result;
}
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
if (n <= 3) {
cout << n;
if (t > 0) cout << '\n';
continue;
}
if (n % 3 == 0) cout << power(3, n / 3);
else if (n % 3 == 1) cout << power(3, n / 3 - 1) * 4 % MOD;
else cout << power(3, n / 3) * 2 % MOD;
if (t > 0) cout << '\n';
}
return 0;
}
P15803 [GESP202603 七级] 物流网络¶
提示1-先看范围
\(n,m\le 5000\)，费用和景观评分\(\le 10^{9}\)。
题目没有给出部分分分组。
不是“随便免一条路”：免的路必须拥有整条路径的最高景观评分。
费用总和用 long long。
提示2-先选免费道路
假设免费的是 \((u,v)\)，景观评分为 \(b\)。
其他道路的评分都必须\(\le b\)。
只用这些道路，求 1 到 \(u\)、\(v\) 到 \(n\) 的最小费用，两段相加。
反方向也试一次。
提示3-按评分逐步加边
把道路按 \(b\) 从小到大加入图。
分别维护从 1、从 \(n\) 出发的最短路。
新增道路后，只把距离变小的端点放入堆，再继续 Dijkstra，不用每次从头算。
提示4-同分道路一起处理
评分相同的道路先全部加入，更新完两份距离，再逐条尝试免费。
此时图里没有评分更高的道路，免费条件就满足了。
评分相同的道路全部加入并更新两份距离后，再试其中一条边u、v免费。费用w不再加入，且两段都必须可达：
代码-满分-增量最短路
保守时间界 \(O(m(n+m)\log(n+m))\)，空间 \(O(n+m)\)。通过复用距离减少重复搜索；没有另设部分分。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> State;
const int N = 5005;
const ll INF = 1LL << 60;
struct Edge {
int u, v;
ll w, b;
} e[N];
vector<pair<int, ll> > g[N];
ll d1[N], dn[N];
bool cmp(Edge x, Edge y) {
return x.b < y.b;
}
void relax(int v, ll value, ll d[], priority_queue<State, vector<State>, greater<State> > &q) {
if (value < d[v]) {
d[v] = value;
q.push(make_pair(value, v));
}
}
void update(ll d[], priority_queue<State, vector<State>, greater<State> > &q) {
while (!q.empty()) {
ll distance = q.top().first;
int u = q.top().second;
q.pop();
if (distance != d[u]) continue;
for (int i = 0; i < (int)g[u].size(); i++) {
int v = g[u][i].first;
ll w = g[u][i].second;
relax(v, distance + w, d, q);
}
}
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) cin >> e[i].u >> e[i].v >> e[i].w >> e[i].b;
if (n == 1) {
cout << 0;
return 0;
}
sort(e, e + m, cmp);
for (int i = 1; i <= n; i++) d1[i] = dn[i] = INF;
d1[1] = 0;
dn[n] = 0;
ll ans = INF;
for (int l = 0; l < m; ) {
int r = l;
while (r < m && e[r].b == e[l].b) r++;
// 小根堆保存新变短的距离；堆内元素数会变化，因此保留priority_queue。
priority_queue<State, vector<State>, greater<State> > q1, qn;
for (int i = l; i < r; i++) {
int u = e[i].u, v = e[i].v;
ll w = e[i].w;
g[u].push_back(make_pair(v, w));
g[v].push_back(make_pair(u, w));
if (d1[u] != INF) relax(v, d1[u] + w, d1, q1);
if (d1[v] != INF) relax(u, d1[v] + w, d1, q1);
if (dn[u] != INF) relax(v, dn[u] + w, dn, qn);
if (dn[v] != INF) relax(u, dn[v] + w, dn, qn);
}
update(d1, q1);
update(dn, qn);
for (int i = l; i < r; i++) {
int u = e[i].u, v = e[i].v;
if (d1[u] != INF && dn[v] != INF) ans = min(ans, d1[u] + dn[v]);
if (d1[v] != INF && dn[u] != INF) ans = min(ans, d1[v] + dn[u]);
}
l = r;
}
cout << (ans == INF ? -1 : ans);
return 0;
}
P17014 [GESP202606 七级] 染色¶
提示1-先看特殊性质
40分做法，各组 \(n\) 之和\(\le 500\)。
看全部数据范围，最多 100 组，\(n\) 之和\(\le 10^{5}\)。
关键不是小范围，而是每个点度数恰好为 2：每个连通块都是一个环。
提示2-沿环交替染色
偶数环可以用两种颜色交替染。
奇数环回到起点时会冲突，需要第三种颜色。
只要有一个奇数环，答案就是 3。
否则答案是 2。
提示3-数每个环的长度
BFS 找出每个连通块，数点数即可。
注意多组数据，每组重新建图。
BFS找出一个连通块后，cnt是这个环的点数。只要发现奇环，就必须用第三种颜色：
代码-40分-邻接矩阵染色
\(O(n^{2})\) 时间与空间。小范围直接尝试两种颜色。
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int color[100005];
bool g[N][N];
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
memset(g, 0, sizeof g);
for (int i = 0, u, v; i < n; i++) {
cin >> u >> v;
g[u][v] = g[v][u] = true;
}
fill(color, color + (n + 1), -1);
bool ok = true;
for (int s = 1; s <= n; s++) if (color[s] == -1) {
queue<int> q;
q.push(s);
color[s] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v = 1; v <= n; v++) if (g[u][v]) {
if (color[v] == -1) {
color[v] = color[u] ^ 1;
q.push(v);
}
else if (color[v] == color[u]) ok = false;
}
}
}
cout << (ok ? 2 : 3);
if (t > 0) cout << '\n';
}
return 0;
}
代码-满分-统计环长
每组 \(O(n)\) 时间与空间。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int> g[N];
bool vis[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int z = 0; z < n + 1; z++) g[z].clear();
fill(vis, vis + (n + 1), 0);
for (int i = 0, u, v; i < n; i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
int ans = 2;
for (int s = 1; s <= n; s++) if (!vis[s]) {
queue<int> q;
q.push(s);
vis[s] = true;
int cnt = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
cnt++;
for (int v : g[u]) if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
if (cnt % 2) ans = 3;
}
cout << ans;
if (t > 0) cout << '\n';
}
return 0;
}
P17015 [GESP202606 七级] 消消乐¶
提示1-先看范围
40分做法，\(n\le 50\)、\(a_{i}\le 1000\)。
看全部数据范围，\(n\le 100\)、\(a_{i}\le 10^{9}\)。
枚举删除顺序有 \(n!\) 种，\(n=50\) 也做不了。
\(O(n^{3})\) 的区间 DP 已能处理全部范围，得分用 long long。
提示2-先删谁不好想，最后删谁呢
设位置 \(k\) 是区间 \([l,r]\) 中最后删除的数。
删 \(k\) 前，左半段、右半段都删空了。
此时 \(k\) 的邻居一定是区间外的 \(a_{l-1}\)、\(a_{r+1}\)。
提示3-左右分别算
设 \(f_{l,r}\) 为保留区间外两侧邻居时，删空 \([l,r]\) 的最高分。
枚举最后删的位置 \(k\)，取最大值：
空区间为 \(0\)，补 \(a_0=a_{n+1}=0\)。
按区间长度递增处理[l,r]，k枚举最后删的位置。左右已删空，当前只取区间外两侧的邻居：
代码-满分-区间 DP
\(O(n^{3})\) 时间，\(O(n^{2})\) 空间。小范围与完整范围使用同一种算法。
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
long long a[N], f[N][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 len = 1; len <= n; len++) for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
for (int k = l; k <= r; k++)
f[l][r] = max(f[l][r], f[l][k - 1] + f[k + 1][r] + a[l - 1] + a[r + 1]);
}
cout << f[1][n];
return 0;
}
P17459 [GESP202609 七级] 必经之路¶
提示1-先看范围
40分做法，\(n\le 100\)、\(m\le 200\)。
看全部数据范围，\(n\le 1000\)、\(m\le 2000\)。
这个范围允许逐个点检查。
图可能有环，不能直接做拓扑 DP。
提示2-假装删掉这个点
如果删去 \(u\) 后，仍能从某个合法起点走到某个合法终点，就有一条路绕过 \(u\)。
如果所有这样的路都断了，\(u\) 就是必经点。
提示3-起终点按原图确定
从原图所有合法起点一起 BFS，跳过被删除的点。
原图终点仍可达就不必经。
不要删点后重新计算起终点，否则会凭空增加新路径。
BFS只能从原图起点出发。ban是这次假装删除的点，原来终点只要还有一个可达，就不是必经点：
代码-40分-邻接矩阵搜索
\(O(n^{3}+m)\) 时间，\(O(n^{2})\) 空间。
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int in[1005], out[1005], ans[1005];
bool vis[1005];
bool g[N][N];
int main() {
int n, m;
cin >> n >> m;
int cnt = 0;
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
g[u][v] = true;
in[v]++;
out[u]++;
}
for (int ban = 1; ban <= n; ban++) {
queue<int> q;
fill(vis, vis + (n + 1), 0);
for (int s = 1; s <= n; s++) if (!in[s] && s != ban) {
vis[s] = true;
q.push(s);
}
bool reachable = false;
while (!q.empty()) {
int u = q.front();
q.pop();
if (!out[u]) {
reachable = true;
break;
}
for (int v = 1; v <= n; v++) if (g[u][v] && v != ban && !vis[v]) {
vis[v] = true;
q.push(v);
}
}
if (!reachable) ans[cnt++] = ban;
}
cout << cnt;
if (cnt > 0) cout << '\n';
for (int i = 0; i < (int)cnt; i++) {
if (i > 0) cout << ' ';
cout << ans[i];
}
return 0;
}
代码-满分-删点与多源 BFS
\(O(n(n+m))\) 时间，\(O(n+m)\) 空间。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int in[N], out[N], ans[N];
vector<int> g[N];
bool vis[N];
int main() {
int n, m;
cin >> n >> m;
int cnt = 0;
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
g[u].push_back(v);
in[v]++;
out[u]++;
}
for (int ban = 1; ban <= n; ban++) {
fill(vis, vis + (n + 1), 0);
queue<int> q;
for (int s = 1; s <= n; s++) if (!in[s] && s != ban) {
vis[s] = true;
q.push(s);
}
bool reachable = false;
while (!q.empty()) {
int u = q.front();
q.pop();
if (!out[u]) {
reachable = true;
break;
}
for (int v : g[u]) if (v != ban && !vis[v]) {
vis[v] = true;
q.push(v);
}
}
if (!reachable) ans[cnt++] = ban;
}
cout << cnt;
if (cnt > 0) cout << '\n';
for (int i = 0; i < (int)cnt; i++) {
if (i > 0) cout << ' ';
cout << ans[i];
}
return 0;
}
P17460 [GESP202609 七级] 括号序列¶
给定一个长度为n的括号字符串，可以删除任意多个字符，保留字符的顺序。
求有多少种选取下标的方式，能够得到合法括号序列。
即使得到的字符串相同，只要选取的下标不同，就分别计数。
空子序列也是合法括号序列，答案对10^9取模。
提示1-先看数据范围
40分做法，\(n\le400\)。
看全部数据范围，\(n\le2000\)。
没有其他特殊性质分组。
每个字符都可以选或不选，共有 \(2^{n}\) 种选法，直接枚举太慢。
先想一个 \(O(n^{3})\) 的方法拿部分分，再尝试优化到 \(O(n^{2})\)。
提示2-部分分：找到配对的右括号
一个非空合法序列，可以拆成 (A)B，其中 \(A\)、\(B\) 也都合法。
如果选了第一个左括号，能不能枚举与它配对的右括号，再分别统计里面和后面的选法？
设 \(f_{l,r}\) 为区间 \([l,r]\) 中的合法子序列数量，空区间记为 \(1\)。
- 不选位置 \(l\)：有 \(f_{l+1,r}\) 种。
- 选位置 \(l\)：它必须是
(。枚举配对的)的位置 \(k\)，贡献为 \(f_{l+1,k-1}\times f_{k+1,r}\)。
把这些方案相加即可。
两个区间端点加上一个配对位置，时间复杂度为 \(O(n^{3})\)。
提示3-满分：还差几个右括号
从左往右读一个合法序列，右括号不能比左括号多，最后两者数量要相等。
假设已经选了几个字符，还需要知道整个字符串吗？
只需知道：有几个左括号还没配对。
记这个数量为 \(j\)。
设 \(\operatorname{dp}_{i,j}\) 为处理前 \(i\) 个字符后，还有 \(j\) 个左括号没配对的选法数量。
过程中不允许出现多余的右括号。
提示4-当前字符选不选
每个字符都有两种选择：
- 不选：\(j\) 不变。
- 选
(：\(j\) 加一。 - 选
)：\(j\) 减一，但必须先有 \(j>0\)。
开始时 \(\operatorname{dp}_{0,0}=1\)，表示什么都不选。
最后取 \(\operatorname{dp}_{n,0}\)：所有左括号都配好了，空子序列也已经算在里面。
\(i\)、\(j\) 都最多到 \(n\)，时间复杂度为 \(O(n^{2})\)。
只保存前后两层，空间复杂度为 \(O(n)\)。
提示5-别漏算，也别多算
(() 的两个左括号，都能与最后的右括号组成 ()。
选的下标不同，要算两种。
再加空子序列，答案为 \(3\)。
全是左括号、全是右括号，或者右括号全在左括号前面，都只有空子序列，答案为 \(1\)。
每次计算都对 \(10^{9}\) 取模。
部分分代码有乘法，要用 long long。
每轮先清空ndp。旧状态j表示还未配对的左括号数；以下示范不选，以及选一个右括号，选左括号的分支见完整代码：
代码-40分-区间动态规划
适用于 \(n\le400\)。时间复杂度 \(O(n^{3})\)，空间复杂度 \(O(n^{2})\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 405;
const long long MOD = 1000000000LL;
long long f[N][N];
int main() {
int n;
string s;
cin >> n >> s;
s = " " + s;
// 空区间只有空子序列这一种方案。
for (int l = 1; l <= n + 1; l++) {
f[l][l - 1] = 1;
}
for (int len = 1; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
f[l][r] = f[l + 1][r]; // 不选位置l。
if (s[l] != '(') continue;
for (int k = l + 1; k <= r; k++) {
if (s[k] == ')') {
long long ways = f[l + 1][k - 1] * f[k + 1][r] % MOD;
f[l][r] = (f[l][r] + ways) % MOD;
}
}
}
}
cout << f[1][n];
return 0;
}
代码-满分-余额动态规划与滚动数组
适用于 \(n\le2000\)。时间复杂度 \(O(n^{2})\)，空间复杂度 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
const int MOD = 1000000000;
int dp[N], ndp[N];
void add(int &a, int b) {
a += b;
if (a >= MOD) a -= MOD;
}
int main() {
int n;
string s;
cin >> n >> s;
dp[0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= n; j++) ndp[j] = 0;
for (int j = 0; j <= i; j++) {
add(ndp[j], dp[j]); // 不选当前字符。
if (s[i] == '(') {
add(ndp[j + 1], dp[j]);
}
else if (j > 0) {
add(ndp[j - 1], dp[j]);
}
}
for (int j = 0; j <= n; j++) dp[j] = ndp[j];
}
cout << dp[0];
return 0;
}