第 08 周从概率题一路铺到区间 DP 和状态机。代码都不长,容易错的地方集中在三处:乘法有没有溢出、边界有没有取到、以及“状态到底代表什么”。
概率、排序与二分
**kotori 和抽卡(二)**每次抽到 R 卡的概率是 80%,其余 20%。求 n 次单抽中恰好 m 次是 R 的概率,保留四位小数。
n 次里选 m 次为 R,共有 C(n, m) 种位置;每种位置的概率是 0.8^m × 0.2^(n-m)。n ≤ 50,用 double 直接算组合数和幂即可。课件给它的类型标签是“数学期望”,这题实际算的是二项分布的概率。
#include <cstdio>
using namespace std;
int main()
{
int n, m;
scanf("%d%d", &n, &m);
double p = 1.0;
for (int i = n; i >= n - m + 1; --i) p *= i; // n! / (n-m)!
for (int i = m; i >= 2; --i) p /= i; // / m!
for (int i = 0; i < m; ++i) p *= 0.8;
for (int i = 0; i < n - m; ++i) p *= 0.2;
printf("%.4f\n", p);
return 0;
}先算排列数再除以 m!,避免单独写阶乘时中间值过大。组合数最大约 C(50,25) ≈ 1.26 × 10^14,double 的精度足够支撑四位小数。
ruby 和薯条给 n 根薯条的长度,统计有多少对满足 l ≤ |a[i] - a[j]| ≤ r,次序不计。排序后,差值在 [l, r] 内的对数等于“差值 ≤ r 的对数”减去“差值 ≤ l-1 的对数”。
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int n, l, r, a[N];
long long countAtMost(int x) // 差值不超过 x 的无序对
{
int left = 0;
long long ret = 0;
for (int right = 0; right < n; ++right)
{
while (a[right] - a[left] > x) ++left;
ret += right - left; // right 与 [left, right-1] 的每一对
}
return ret;
}
int main()
{
cin >> n >> l >> r;
for (int i = 0; i < n; ++i) cin >> a[i];
sort(a, a + n);
cout << countAtMost(r) - countAtMost(l - 1) << '\n';
return 0;
}排序后固定右端,左端越小差值越大;left 单调右移,不会回退。right - left 统计的是以 right 为较大值的对数,恰好不重不漏。复杂度 O(n log n),排序是瓶颈。
课件的二分写法也对,但每个右端要做两次二分,常数更大;l 最小是 1,countAtMost(l - 1) 的 x 不会小于 0。
**差值(最小差值)**把数组排序,最小绝对差一定出现在相邻两项之间。
#include <algorithm>
#include <climits>
#include <vector>
using namespace std;
class Solution
{
public:
int minDifference(vector<int>& arr)
{
if (arr.size() < 2) return 0;
sort(arr.begin(), arr.end());
long long ret = LLONG_MAX;
for (size_t i = 1; i < arr.size(); ++i)
ret = min(ret, (long long)arr[i] - arr[i - 1]);
return (int)ret;
}
};先排序再比较相邻,O(n log n)。差值可能达到 INT_MAX - INT_MIN ≈ 4.29 × 10^9,超出 int,所以中间用 long long 相减再取最小;直接用 int 相减会溢出成负数,最小值反而变成那个负数。
递推与单向扫描:汉诺塔、非递减串、高音
循环汉诺塔的三根柱子排成一圈,每次只能把盘子搬到相邻柱上。设 x[n] 是把 n 个盘从一根柱子搬到相邻柱的最少步数,y[n] 是搬到对面柱的最少步数。
搬 n 个盘到相邻柱:先把上面 n-1 个搬到对面柱(y[n-1] 步),把最大的搬一格(1 步),再把 n-1 个从对面搬到目标柱,同样是对面距离(y[n-1] 步)。于是 x[n] = 2y[n-1] + 1。
搬 n 个盘到对面柱:先把 n-1 个搬到相邻柱(x[n-1] 步),最大的搬两格(2 步),再把这 n-1 个搬到对面柱(y[n-1] 步)。于是 y[n] = 2y[n-1] + x[n-1] + 2。
#include <iostream>
using namespace std;
const long long MOD = 1000000007;
int main()
{
int n;
cin >> n;
long long x = 1, y = 2; // 1 个盘:搬到相邻柱 1 步,搬到对面 2 步
for (int i = 2; i <= n; ++i)
{
long long nx = (2 * y + 1) % MOD;
long long ny = ((2 * y) % MOD + 2 + x) % MOD;
x = nx;
y = ny;
}
cout << x << ' ' << y << '\n';
return 0;
}n = 2 时输出 5 7,与样例一致。循环里只保留上一轮的 x、y,空间 O(1);n < 10^7,时间 O(n)。每一步取模,2*y + 1 最大约 2 × 10^9,仍在 64 位范围内,用 long long 更稳。
dd 爱科学 1.0把大写字母串改成非递减序列,每次可以改一个字符,求最小改动数。保留最长的非递减子序列不动,其余字符改成合适值即可,答案是 n - LNDS 长度。
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
int main()
{
int n;
string s;
cin >> n >> s;
string tail; // tail[k]:长度为 k+1 的非递减子序列的最小末尾
for (char c : s)
{
auto it = upper_bound(tail.begin(), tail.end(), c); // 第一个 > c
if (it == tail.end()) tail.push_back(c);
else *it = c;
}
cout << n - (int)tail.size() << '\n';
return 0;
}非递减允许相等,所以找第一个严格大于 c 的位置替换;如果换成 lower_bound(第一个 ≥ c),相等就会被当成上升,长度偏大。字母只有 26 种,upper_bound 实际是 O(log 26),整体 O(n)。
kanan 和高音有一段音符,后一个音比前一个音高不超过 8 才能接着唱,低音没有限制。求最长能完整唱的连续片段。
限制是单向的,所以检查 a[j+1] - a[j] <= 8,不取绝对值。从每个位置开始向右扩展,遇到第一个超过 8 的间隔就断开,取最大段长。
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int n, a[N];
int main()
{
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
int ret = 1;
for (int i = 0; i < n; )
{
int j = i;
while (j + 1 < n && a[j + 1] - a[j] <= 8) ++j;
ret = max(ret, j - i + 1);
i = j + 1;
}
cout << ret << '\n';
return 0;
}从 i 出发能连到的最远位置就是 j,再往后一定断;下一段从 j+1 开始,不会漏掉更长的组合。每个位置进出一次,时间 O(n)。样例 1 10 5 1 2 中,1 到 10 的差是 9,第一段只含 1,第二段是 10 5 1 2,长度 4。
搜索:素因子、最短路条数、四个选项
kotori 和素因子给 n 个不同的正整数,每个数取出一个素因子,要求所有取出的素因子互不相同,求最小总和;无解输出 -1。
每个数最多只有几个不同的素因子,直接 DFS 枚举“这个数取哪个素因子”,用 used 标记已经用掉的因子。
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
const int N = 15;
int n, a[N], path, best = 0x3f3f3f3f;
bool used[1010];
bool isPrime(int x)
{
if (x < 2) return false;
for (int i = 2; i <= (int)sqrt(x); ++i)
if (x % i == 0) return false;
return true;
}
void dfs(int pos)
{
if (pos == n) { best = min(best, path); return; }
for (int p = 2; p <= a[pos]; ++p)
if (a[pos] % p == 0 && !used[p] && isPrime(p))
{
used[p] = true;
path += p;
dfs(pos + 1);
path -= p;
used[p] = false;
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
dfs(0);
cout << (best == 0x3f3f3f3f ? -1 : best) << '\n';
return 0;
}n ≤ 10、a[i] ≤ 1000,每个数不同素因子的个数很少,枚举量远小于 10!。best 没被更新过就说明无解。
拜访给 n × m 的城市地图,1 是经理位置、2 是商家位置、-1 不能经过、0 可以经过,求最短路条数。BFS 分层,dist 记最短距离,cnt 记到达该格的最短路条数。
#include <cstring>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
class Solution
{
int n, m, sx, sy, tx, ty;
int dist[15][15], cnt[15][15];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
public:
int countPath(vector<vector<int>>& city, int _n, int _m)
{
n = _n, m = _m;
memset(dist, -1, sizeof dist);
memset(cnt, 0, sizeof cnt);
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
{
if (city[i][j] == 1) sx = i, sy = j;
if (city[i][j] == 2) tx = i, ty = j;
}
queue<pair<int, int>> q;
q.push({sx, sy});
dist[sx][sy] = 0;
cnt[sx][sy] = 1;
while (!q.empty())
{
auto [x, y] = q.front();
q.pop();
for (int k = 0; k < 4; ++k)
{
int nx = x + dx[k], ny = y + dy[k];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (city[nx][ny] == -1) continue;
if (dist[nx][ny] == -1) // 第一次到达
{
dist[nx][ny] = dist[x][y] + 1;
cnt[nx][ny] = cnt[x][y];
q.push({nx, ny});
}
else if (dist[nx][ny] == dist[x][y] + 1) // 同样是最短路
cnt[nx][ny] += cnt[x][y];
}
}
return cnt[tx][ty];
}
};BFS 按距离分层,所有距离为 d 的格子会先于距离 d+1 的格子出队,所以一个格子的所有最短路前驱出队完,它的 cnt 才用于扩展。两个方向都判:第一次到达直接继承,非第一次但距离相同就累加。n、m ≤ 10,路径条数最多 C(18,9) = 48620,int 装得下。
课件的 C++ 把 dist、cnt 做成成员却只在 bfs 里 memset(dist),cnt 依赖对象的默认初始化;同一个对象调用两次 countPath 时,上一次的 cnt 会残留,第二次答案偏大。把两个数组都在入口清零更稳。

四个选项有 12 道题,四个选项各需要出现 cnt[1..4] 次,另有 m 组约束要求两道题答案相同。求填法数。
DFS 逐题填选项,用剩余次数和“相同约束”剪枝:填第 pos 题时,若它与前面某题相同,前面那道题的答案必须等于当前选项。
#include <iostream>
#include <vector>
using namespace std;
int cnt[5], m, x, y;
bool same[13][13];
int ret, path[13];
bool canPlace(int pos, int cur)
{
for (int i = 1; i < pos; ++i)
if (same[pos][i] && path[i] != cur) return false;
return true;
}
void dfs(int pos)
{
if (pos > 12) { ++ret; return; }
for (int i = 1; i <= 4; ++i)
{
if (cnt[i] == 0) continue; // 这个选项已经用完
if (!canPlace(pos, i)) continue; // 与前面同答案的题目冲突
--cnt[i];
path[pos] = i;
dfs(pos + 1);
++cnt[i];
}
}
int main()
{
for (int i = 1; i <= 4; ++i) cin >> cnt[i];
cin >> m;
while (m--)
{
cin >> x >> y;
same[x][y] = same[y][x] = true;
}
dfs(1);
cout << ret << '\n';
return 0;
}选项用完和同答案冲突都是硬约束,提前剪掉。最坏情况是所有选项平均分配且没有约束,约 12! / (3!)^4 ≈ 3.7 × 10^5 种,可以接受。
哈希与模拟:n 皇后、转置、隐藏分数
kotori 和 n 皇后依次放 k 个皇后,t 次询问第 i 个皇后放完后是否存在互相攻击的一对。两皇后攻击等价于同一行、同一列、同一条 45° 或 135° 对角线。
每放一个皇后,检查它的行、列、y - x、y + x 是否已经出现过;第一次出现冲突时记下编号,之后所有 i ≥ 该编号 的询问都回答 Yes。
#include <iostream>
#include <unordered_set>
using namespace std;
typedef long long LL;
int main()
{
int k;
cin >> k;
unordered_set<LL> row, col, d1, d2; // 行 y、列 x、y-x、y+x
int first = 1e9;
for (int i = 1; i <= k; ++i)
{
LL x, y;
cin >> x >> y;
if (first != 1e9) continue;
if (row.count(y) || col.count(x) || d1.count(y - x) || d2.count(y + x))
first = i;
row.insert(y);
col.insert(x);
d1.insert(y - x);
d2.insert(y + x);
}
int t;
cin >> t;
while (t--)
{
int i;
cin >> i;
cout << (i >= first ? "Yes" : "No") << '\n';
}
return 0;
}坐标到 10^9,不能开二维数组,用四个哈希集合。冲突一旦出现,后面的皇后不再需要检查,但输入仍然要读完。平均 O(k + t)。
矩阵转置给 n × m 的矩阵,按列优先输出。
#include <iostream>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
int a[15][15];
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
cin >> a[i][j];
for (int i = 0; i < m; ++i)
{
for (int j = 0; j < n; ++j) cout << a[j][i] << ' ';
cout << '\n';
}
return 0;
}转置后的第 i 行第 j 列等于原矩阵的第 j 行第 i 列,直接交换输出下标即可,不需要真的搬矩阵。时间 O(nm),空间 O(nm)。
疯狂的自我检索者有 n 个评分,其中 m 个还没公开,公开值都在 1 到 5。求最终平均分的最小值和最大值。
已知 n - m 个分数的和 sum。隐藏分数全取 1 时平均分最小,全取 5 时最大。
#include <cstdio>
using namespace std;
int main()
{
int n, m;
scanf("%d%d", &n, &m);
long long sum = 0;
for (int i = 0; i < n - m; ++i)
{
int x;
scanf("%d", &x);
sum += x;
}
printf("%.5f %.5f\n", (double)(sum + m) / n, (double)(sum + 5LL * m) / n);
return 0;
}只有两个极值会影响答案,中间的取值不用枚举。sum 用 64 位,避免分数总和在极端数据下溢出。
动态规划:股票状态机与区间取金币
**买卖股票的最好时机(四)**最多交易 k 次,买入卖出算一笔,同一时间只能持有一股。用“有股票 / 无股票”两个状态:
f[i][j]:第 i 天结束、已完成 j 笔交易、手里有股票的最大收益;g[i][j]:第 i 天结束、已完成 j 笔交易、手里无股票的最大收益。
买入不增加交易笔数,卖出才把 j 加一。
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1010, K = 110;
int n, k, p[N];
int f[N][K], g[N][K];
int main()
{
cin >> n >> k;
for (int i = 0; i < n; ++i) cin >> p[i];
k = min(k, n / 2); // 交易次数不可能超过 n/2
for (int j = 0; j <= k; ++j) f[0][j] = g[0][j] = -0x3f3f3f3f;
f[0][0] = -p[0];
g[0][0] = 0;
for (int i = 1; i < n; ++i)
for (int j = 0; j <= k; ++j)
{
f[i][j] = max(f[i - 1][j], g[i - 1][j] - p[i]); // 继续持有或今天买入
g[i][j] = g[i - 1][j]; // 继续空仓
if (j >= 1) g[i][j] = max(g[i][j], f[i - 1][j - 1] + p[i]); // 今天卖出,笔数加一
}
int ret = 0;
for (int j = 0; j <= k; ++j) ret = max(ret, g[n - 1][j]);
cout << ret << '\n';
return 0;
}第 0 天只能“已经买入”,所以 f[0][0] = -p[0];其余不存在状态用足够小的负数,避免被 max 选中。答案取最后一天、任意交易笔数的空仓最大值,空仓收益至少为 0,所以 ret 从 0 开始。时间 O(nk),空间 O(nk);由于每行只依赖上一行,也可以滚成 O(k)。
![题面里的状态转移图:f 与 g 之间,买入时减 prices[i],卖出时加 prices[i];买入不增加笔数,卖出才进入下一笔](/images/engineering/exam/exam-week-08/p26-919x367.webp)
取金币给一排金币,每次取走第 k 枚,得分等于左邻居 × 当前 × 右邻居,左右没有金币时按 1 算,求最大总分。
在数组两端各补一个 1,把问题变成“最后取哪一个”。dp[i][j] 表示区间 [i, j] 全部取完能得到的最大分,枚举最后一个取的位置 k:
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
class Solution
{
public:
int getCoins(vector<int>& coins)
{
int n = coins.size();
vector<int> a(n + 2, 1);
for (int i = 1; i <= n; ++i) a[i] = coins[i - 1];
vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
for (int i = n; i >= 1; --i)
for (int j = i; j <= n; ++j)
for (int k = i; k <= j; ++k)
dp[i][j] = max(dp[i][j],
dp[i][k - 1] + dp[k + 1][j] + a[i - 1] * a[k] * a[j + 1]);
return dp[1][n];
}
};按区间长度从小到大推:i 从 n 到 1,j 从 i 到 n,保证 [i, k-1] 和 [k+1, j] 都先算好。补的两个 1 只在边界相乘时出现,不会参与取走。n ≤ 100,O(n³) 大约是 10^6 次运算。
栈、堆与窗口:AOE、栈排序、加减、接雨水
AOE 还是单体? 单体技能花 1 点 mp 打 1 点伤害,AOE 花 x 点 mp 打全体 1 点。给 n 个怪物的血量,求清完的最小 mp。
设一共放 t 次 AOE,总消耗是 t × x + Σ max(0, a[i] - t)。每多放一次 AOE,省下“还活着的怪物数”点单体伤害;当活着的小怪不超过 x 时,再放 AOE 就不划算了。把血量排序,最优的 t 取第 n - x 小的血量:比它大的怪物数量不超过 x。
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n;
LL x, a[N];
int main()
{
cin >> n >> x;
for (int i = 1; i <= n; ++i) cin >> a[i];
sort(a + 1, a + n + 1);
LL ret = 0;
if (x >= n) // 一次 AOE 比打所有单体还贵
{
for (int i = 1; i <= n; ++i) ret += a[i];
}
else
{
int idx = n - (int)x; // 1 下标,第 idx 小的血量
ret = a[idx] * x; // 这里必须先转 64 位
for (int i = idx + 1; i <= n; ++i) ret += a[i] - a[idx];
}
cout << ret << '\n';
return 0;
}a[idx] * x 是两个 int 相乘,血量与 x 都可以到 10^9,乘积到 10^18,32 位乘法会溢出。课件这里写的是 ret += arr[index] * x;,ret 虽然是 long long,乘法已经先按 int 算完了;必须写成 (LL)a[idx] * x。Java 同样要先把一侧转成 long。
复杂度 O(n log n),瓶颈在排序。
栈和排序给一个 1..n 的排列,按顺序入栈,可以在任意时刻出栈,要求输出的字典序最大。
维护 aim 为“还没入栈的最大值”。每次入栈后,只要栈顶不小于 aim,栈顶就是当前能输出的最大元素,连续弹出;全部入栈后 aim 会降到 0,栈会被清空。
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n), ret;
for (int i = 0; i < n; ++i) cin >> a[i];
vector<int> st;
vector<bool> seen(n + 1, false);
int aim = n;
for (int x : a)
{
st.push_back(x);
seen[x] = true;
while (aim >= 1 && seen[aim]) --aim;
while (!st.empty() && st.back() >= aim)
{
ret.push_back(st.back());
st.pop_back();
}
}
for (int x : ret) cout << x << ' ';
cout << '\n';
return 0;
}比 aim 小的元素先压在栈里,等更大的元素都输出后再处理。每个元素入栈、出栈一次,时间 O(n),空间 O(n)。
加减给 n 个数和 k 次操作,每次把某个数加一或减一,问最多能让多少个数相等。排序后,最优方案是把一段连续区间改成它们的中位数;操作次数是区间内每个数与中位数之差的绝对值之和。
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;
LL k, a[N], sum[N];
LL cost(int l, int r)
{
int mid = (l + r) / 2;
return (LL)(mid - l) * a[mid] - (sum[mid - 1] - sum[l - 1])
+ (sum[r] - sum[mid]) - (LL)(r - mid) * a[mid];
}
int main()
{
cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> a[i];
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + a[i];
int left = 1, ret = 1;
for (int right = 1; right <= n; ++right)
{
while (cost(left, right) > k) ++left;
ret = max(ret, right - left + 1);
}
cout << ret << '\n';
return 0;
}cost 用前缀和把“左半部分降下来、右半部分升上去”的代价算成 O(1)。区间变长时,改成中位数的总代价不会减少,所以左指针可以一路右移,滑动窗口是单调的。排序 O(n log n),窗口 O(n)。
接雨水给一排柱子的高度,求下雨后能接多少水。每根柱子上方的水高等于左右两侧最高柱子的较小值减去自身高度。
课件的写法预处理左右最大值数组,时间 O(n)、空间 O(n)。用双指针可以把空间压到 O(1):维护左右两侧已经见过的最大高度,哪一侧的当前最大值更小,就结算哪一侧的柱子。
#include <algorithm>
#include <vector>
using namespace std;
class Solution
{
public:
int trap(vector<int>& h)
{
int n = h.size();
int l = 0, r = n - 1, lm = 0, rm = 0, ret = 0;
while (l < r)
{
lm = max(lm, h[l]);
rm = max(rm, h[r]);
if (lm < rm) { ret += lm - h[l]; ++l; }
else { ret += rm - h[r]; --r; }
}
return ret;
}
};lm 是 [0, l] 的最大值,rm 是 [r, n-1] 的最大值。若 lm < rm,左柱的水位由 lm 决定,可以直接结算并右移;右侧同理。每个下标只走一次,时间 O(n),空间 O(1)。
还没有评论 — 第一条由你来留。