Colton Star Blog

成绩#

队伍过 2 题，全场最高 6 题，共 13 题。

签到题#

题意：给出角块、边块、中间块个数，判断能否构造一个合法矩形。中间块个数可以为 0。

踩坑：中间块可以为 0 这个条件一开始没注意，WA 了2发。矩形构造的数学条件倒是简单——角块固定 4 个，边块必须是 2 的倍数分配到四条边上，中间块个数和行列数对应。

这题过得还算顺利，签到题不签到才是真问题。

卡住的题#

一、序列分段 DP

题意：从第一个节点走到第 n 个节点，每次跳若干步（步长 = 跳过的节点数），收集落脚点的权值。步长必须单调不增——每一步不能比上一步长。求最大总权值。n ≤ 3000。

状态定义

dp[i][j]：到达位置 i，且上一步走了 j 步，已经获得的最大总权值。a[i] 表示位置 i 的权值。

转移方程

到达位置 i 之前，你在位置 i - j，上一步跳了 j 步。再上一步跳了 k 步，约束 k ≥ j（步长单调不增）：

1
dp[i][j] = max_{k ≥ j} dp[i - j][k] + a[i]

max_{k ≥ j} dp[i - j][k] 是行 i - j 上步长 ≥ j 的所有状态的最大值。

初始化

起点在位置 1，权值自动获得。最简洁的方式——给位置 1 所有步长状态赋值为 a[1]：

1
for (int j = 1; j <= n; j++)
2
    dp[1][j] = a[1];

优化：从 O(n³) 到 O(n²)

原方程的最内层需要枚举 k——遍历所有 k ≥ j，三重循环 ≈ O(n³)。观察到一个关键性质：每一行的查询区间永远是后缀（[j, i-1]）。后缀最大值数组 O(1) 查询：

1
// suf[k][j] = max(dp[k][j], suf[k][j+1])  逆序构建
2
dp[i][j] = suf[i - j][j] + a[i];

复杂度：O(n²)，n = 3000 能过。

坑点

1. 不要一看到区间最值就上 ST 表。ST 表是为任意 [L, R] 区间设计的，而这道题右端点固定、左端点单调——后缀数组就够了。四行代码和十几行代码的差别，调 bug 的时间完全不一样。
2. 哨兵值需要初始化为 -1e18，因为 a[i] 可能为负，3000 个负数累加远小于 -1e9。
3. 位运算溢出——中间乘法 a * b % p 在 a 和 b 都接近 10⁹ 时可能爆 long long，需要用 __int128 做中间类型。但如果模数本身很小（如 ≤ 45000），用 long long 直接乘法更快——64 位硬件取模指令比 128 位软件模拟快数倍。

教训

推完 DP 方程后，先看一眼查询区间的形状。如果是后缀 → 后缀最值数组，前缀 → 前缀最值数组。只有任意 [L, R] 无规律时才考虑 ST 表或线段树。赛场上这道题花了四十分钟，赛后重写只用了十五分钟——差距就是这一步”看一眼区间形状”。

问题总结#