lessons/课程/12-历年真题/05-CSP-S2024物理区间与双序列DP.md

CSP-S 2024 真题：物理条件区间化与双序列状态压缩

本节目标

学习把连续运动判定转成测速仪下标区间，并把两种颜色的完整历史压成“当前颜色末值 + 另一颜色末值”。

前置知识与课前自测

前置：二分、区间刺点贪心、动态规划、Lazy 全局加思想。

1. 匀加速下速度平方关于位置是怎样的函数？
2. 两种颜色序列中，处理新值时未来还关心每种颜色的哪些信息？

答案

1. $v^2(x)=v_0^2+2a(x-d)$，对位置单调。 2. 各颜色最后一个值；更早历史已经结算完得分。

问题动机

《超速检测》若按每车逐监测器模拟会产生二次量访问，《染色》若把两个序列的选择进度全放进状态又会得到平方状态。两题的降维分别来自“物理不等式在单调位置上形成区间”与“下一步只与已取元素的边界色有关”。

精选例题 1：超速检测

来源、题意与范围

• 洛谷-P11232 超速检测
• 每组 $n,m\le10^5$，车辆匀加速向北、测速仪位置有序；先求会被全部仪器检测的车数，再求保证都仍被检测时最多关闭多少仪器。

Hint 1：避免浮点

在位置 p 比较 `v_i^2 + 2*a_i*(p-d_i) > V^2`。

Hint 2：每辆车对应什么

由于速度平方单调，能检测它的测速仪下标构成一个连续区间。

Hint 3：保留最少测速仪

转成用最少点刺中全部区间，按右端点贪心。

Observations

• 加速度正、零、负分别产生后缀、全后缀/空、有限前缀区间，但统一为检测器下标区间。
• 严格“超过”要求使用 >，速度恰等于限速不能计入。
• 第二问只关心每辆已检测车至少留下一个命中仪器，是经典区间刺点。

Editorial 与证明

对每辆车先找第一个不小于驶入位置的测速仪，再按加速度与整数速度平方不等式二分区间另一端。非空区间计入检测车辆。将区间按右端点排序；若上次保留点不在当前区间，就保留当前右端点。

区间右端点是当前及以后所有可选点中最早的，不会比任何其他选择减少覆盖后续区间的机会；交换可得到存在最优方案选它。故保留点数最小，关闭数为 m 减它。

复杂度 $O((n+m)\log n)$。

核心伪代码与附件

for each car:
    derive detector-index interval where speed_squared(position) > limit_squared
sort nonempty intervals by right endpoint
last = none; kept = 0
for [l,r]:
    if last < l: keep detector r; last=r; kept++
output interval_count, m-kept

完整 C++17 附件

精选例题 2：染色

来源、题意与范围

• 洛谷-P11233 染色
• $n\le2\times10^5$，每个正整数染红/蓝；若它与同色前一个数相等则获得该值，最大化总分。

Hint 1：两条子序列

红蓝染色等价于把原序列分到两个保持顺序的子序列。

Hint 2：利用颜色对称

令当前元素总在“活动颜色”末尾，状态只记录另一颜色末值。

Hint 3：全体状态同加

若下一值等于当前值，继续活动颜色让所有状态统一加该值；切换颜色只更新一个状态。

Observations

• 朴素状态 (lastRed,lastBlue) 是值域平方；颜色交换对称可固定一边末值为当前元素。
• 新值放当前颜色时，另一末值不变且全部 DP 状态加同一奖励。
• 新值放另一颜色后，新的“另一末值”统一变成旧当前值；只需用全局最优或旧另一末值等于新值的状态更新一个点。

Editorial

处理到 i，设当前活动颜色末值为 $A_i$，dp[x] 表示另一颜色末值为 x 的最优分。维护所有 dp 的全局加量与基值最大值。到新值 y：切换颜色候选为 max(globalBest, dp[y]+y)；继续当前颜色若 y 等于旧当前值则给所有状态加 y；最后用切换候选点更新状态 oldCurrent。

正确性证明

任一染色方案在处理前缀后可交换红蓝名称，使当前元素属于活动颜色，故状态无损。下一元素只有继续或切换两种，转移完全覆盖。继续奖励只由 y 与旧当前值决定，切换奖励只由 y 与另一末值决定，因此聚合公式精确。

每步 $O(1)$，空间 $O(\max A_i)$。

核心伪代码与附件

dp[empty_other] = 0; current = A[1]; global_add = 0
for y in A[2:]:
    switch_value = max(best_dp + global_add, dp[y] + global_add + y)
    if y == current: global_add += y
    dp[current] = max(dp[current], switch_value - global_add)
    current = y
answer = best_dp + global_add

完整 C++17 附件

实现指南

《超速检测》先在 128 位整数中解速度平方不等式，再用两次二分将实数/整数边界落到监测器下标；贪心覆盖时按区间右端排序。《染色》的状态中要明确“上一个取自哪个序列”，相同位置色值不能代替来源维度；转移时使用新层数组，防止一个元素在同层被取多次。

扩展与联系

超速检测把连续实数运动压成离散区间；染色把两维历史压成一个值与全局偏移。两者都先找单调/对称结构，再选择数据结构。

总结与自检

1. 减速车辆为什么仍是连续检测区间？
2. 区间刺点为何按右端点？
3. 染色状态中的颜色交换为什么安全？
4. 切换转移为何只更新 oldCurrent 状态？

课后训练建议

物理题用离散时间模拟小数据；染色题枚举 $2^n$ 染色对拍，覆盖连续相等、全不同、零状态不存在等情况。