第 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 会残留,第二次答案偏大。把两个数组都在入口清零更稳。

题面里的 4×4 城市地图:橙色格 (0,0) 是商家,绿色格 (2,2) 是经理,灰色 -1 是障碍;样例的最短方案有 2 条

四个选项有 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];买入不增加笔数,卖出才进入下一笔

取金币给一排金币,每次取走第 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)。