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

## 本节目标

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

## 前置知识与课前自测

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

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

<details><summary>答案</summary>

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

</details>

## 问题动机

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

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

- [洛谷-P10217 季风](https://vjudge.net/problem/%E6%B4%9B%E8%B0%B7-P10217)，省选联考 2024
- 周期 n 的风位移，每天另可选 L1 长度不超过 k 的实位移；求到达目标 `(x,y)` 的最少非负天数或 -1。总 n 至 $10^6$。

<details><summary>Hint 1：不要对天数整体二分</summary>多过一天会受到新风影响，可达性未必单调。</details>
<details><summary>Hint 2：枚举天数模 n</summary>固定余数 r 后，天数是 `q*n+r`，风位移关于 q 线性。</details>
<details><summary>Hint 3：去绝对值</summary>Manhattan 条件拆成四个线性不等式，分别给 q 的下界或上界。</details>

## 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` 防止系数乘法溢出。

## 核心伪代码与附件

```text
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 附件](../../参考实现/12-历年真题/洛谷-P10217.cpp)

## 实现指南

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

## 扩展与联系

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

## 总结与自检

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

## 课后训练建议

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