省选联考 2024《季风》：周期位移与四个线性约束

本节目标

把二维每日可控移动的可达域写成 Manhattan 球，再按周期余数把绝对值不等式化成四个关于周期数的一次约束。

前置知识与课前自测

前置：前缀和、绝对值、一次不等式、周期分解。

m 天每天可自主移动 Manhattan 距离至多 k，总自主位移集合是什么？
二维 $|X|+|Y|\le R$ 等价于哪四个线性不等式？
按完整周期数 q 与余数 r 分解后，为何每个不等式只关于 q 一次？

答案

1. 半径 mk 的整/实 Manhattan 球；每天预算可拆分实现其中任一点。 2. 对所有 $s_x,s_y\in\{-1,1\}$，有 $s_xX+s_yY\le R$。 3. 风位移是 q 倍周期总和加固定前缀，右侧预算也是 q 的一次函数。

问题动机

“求最少天数”容易让人立即二分，但风向会使第 $m+1$ 天的可达域不一定包含第 $m$ 天的可达域，全局谓词不单调。周期分解的真正作用不是少模拟几天，而是固定余数后把风位移与自主移动预算都写成完整周期数 $q$ 的一次式。

精选例题：来源、题意与范围

洛谷-P10217 季风，省选联考 2024
周期 n 的风位移，每天另可选 L1 长度不超过 k 的实位移；求到达目标 (x,y) 的最少非负天数或 -1。总 n 至 $10^6$。

Hint 1：不要对天数整体二分

多过一天会受到新风影响，可达性未必单调。

Hint 2：枚举天数模 n

固定余数 r 后，天数是 `q*n+r`，风位移关于 q 线性。

Hint 3：去绝对值

Manhattan 条件拆成四个线性不等式，分别给 q 的下界或上界。

Observations

“最少天数”容易诱导二分，但风可能把人吹离目标，谓词并不全局单调。
固定 r 后只剩完整周期数 q；这是恢复单调/线性的正确参数。
四个符号不等式的交集是一个整数区间，直接取最小可行 q。

Editorial

预处理一个周期前缀与总风位移。对每个 r=0..n-1，残差为目标减前 r 天风，再减 q 倍周期风。条件

$$ |X(q)|+|Y(q)|\le k(qn+r) $$

拆成四个 C*q<=R。若 C 正给上界，C 负给下界，C 为 0 检查常量。合并四个界，若非空则候选为最小 q；在所有 r 中取最小天数。

正确性证明

m 天自主动作的 Minkowski 和恰为半径 mk 的 L1 球：必要性由三角不等式，充分性可把目标自主位移按天拆成每段不超过 k。四符号表达与 L1 不等式等价。每个 m 有唯一 (q,r)，枚举不漏；固定 r 的线性界求出全部可行 q，取最小不重。

复杂度 $O(n)$ 每组，使用 __int128 防止系数乘法溢出。

核心伪代码与附件

prefix_wind, cycle_wind = preprocess()
answer = infinity
for r in 0..n-1:
    low, high = 0, infinity
    for sx,sy in four sign pairs:
        derive C*q <= R
        intersect [low,high] with this inequality's integer solutions
    if low <= high: answer = min(answer, low*n+r)

完整 C++17 附件

实现指南

对每个余数 $r$，用有符号 128 位整数存四个不等式的系数与常数。处理 $Aq\le B$ 时必须按 $A>0,A=0,A<0$ 分类，负数除法不能直接依赖 C++ 向零截断，应封装数学意义的 floor/ceil divide。合并得到的 $q$ 下界还要与 0 取最大，然后用原 Manhattan 不等式回代一次，可快速抓出不等号和整除边界错误。

扩展与联系

周期系统中“固定余数再研究周期数”常用于移动、自动机与取模 DP。若每日自主位移是欧氏球，四个线性约束会变成二次不等式，方法需调整。

总结与自检

全局二分的反例怎样构造？
L1 球为何由四个半平面交成？
负系数不等式怎样转成 q 下界？
k=0 是否被统一处理？

课后训练建议

对小 n、限制小天数逐日枚举 q/r 与网格自主移动，对拍线性界算法；重点覆盖系数为 0 和无上界情况。

07-省选2024周期位移与四个线性约束.md 4.2 KB History Raw