AtCoder Beginner Contest 459 题解

项目	内容
比赛时间	2026-05-23
比赛链接	https://atcoder.jp/contests/abc459
题目数量	A–G 共 7 题

比赛概览

本场整体难度适中：A、B 是入门热身题；C 需要抓住"全局删除"的懒惰处理技巧；D 是经典的重排字符串不相邻问题；E 结合树的遍历与组合计数；F 通过单调化变换 $B_i=A_i-i$ 把问题转化为单调回归（PAVA），是区分度较高的一题；G 是全场的压轴题，综合了扩展欧几里得、奇偶性归约与凸分段线性函数的最小化，值得反复消化。

---

A - Hell, World!

题目链接：https://atcoder.jp/contests/abc459/tasks/abc459_a

题目大意

给定一个整数 $X$（$1 \le X \le 10$），输出字符串 HelloWorld 删除第 $X$ 个字符后得到的字符串。

思路

这是最简单的字符串处理题，只要跳过原字符串中的第 $X$ 个字符即可。

一个直观的做法是：令 $S=$ HelloWorld，$T$ 为空串，从左到右扫描 $i=1,2,\ldots,10$，若 $i\neq X$ 就把 $S_i$ 接到 $T$ 末尾。这样 $T$ 恰好是删掉第 $X$ 个字符后的结果。

在 C++ 中还可以直接用 erase 一步完成：注意 C++ 的下标从 $0$ 开始，所以要先执行 x--，然后 s.erase(s.begin() + x)。

边界情况：$X=1$ 时删除第一个字符，$X=10$ 时删除最后一个字符，上述做法都天然正确。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int x;
    cin >> x;
    x--;
    string s = "HelloWorld";
    s.erase(s.begin() + x);
    cout << s << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(1)$（字符串长度固定为 $10$）
• 空间复杂度：$O(1)$

---

B - 459

题目链接：https://atcoder.jp/contests/abc459/tasks/abc459_b

题目大意

给定 $N$ 个小写字母组成的字符串 $S_1,\ldots,S_N$。对每个字符串，按"老式九键手机"的规则，根据它的第一个字符映射成一个数字字符：a,b,c → 2，d,e,f → 3，$\ldots$，w,x,y,z → 9。把所有映射得到的数字按顺序拼接并输出。

思路

规则就是手机键盘九宫格：从 a 到 z，每 3 个字母一组对应 2,3,4,5,6,8，而 7（pqrs）和 9（wxyz）一组有 4 个字母。

最简洁的实现是打一张长度 26 的查表字符串：

a b c d e f g h i j k l m n o p q r s t u v w x y z
2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 7 8 8 8 9 9 9 9

即 "22233344455566677778889999"，用 mp[s[0]-'a'] 即可得到答案。也可以手动生成这张表：对 2..9 循环，2..6,8 各写 3 个，7,9 各写 4 个。

由于每个字符串长度不超过 10，直接扫描即可，不需要任何优化。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string mp = "22233344455566677778889999";
    int n;
    cin >> n;
    string ans;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        ans += mp[s[0] - 'a'];
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(\sum |S_i|)$
• 空间复杂度：$O(1)$

---

C - Drop Blocks

题目链接：https://atcoder.jp/contests/abc459/tasks/abc459_c

题目大意

有 $N$ 个格子排成一排，初始都没有方块。处理 $Q$ 个操作：

• 1 x：在第 $x$ 个格子上放 1 个方块；然后，若此时每个格子都至少有 1 个方块，则从每个格子中移除 1 个方块。
• 2 y：输出方块数至少为 $y$ 的格子个数。

$N,Q \le 3\times 10^5$。

思路

关键观察：跳过"全局删除"

如果每次都真的模拟"从所有格子各删一个方块"，那么一次全局删除就要花 $O(N)$，最坏情况下总代价是 $\Theta(NQ)$，无法接受。

注意到：全局删除对所有格子是同步进行的，删了多少次只影响"相对高度"的整体平移。所以我们完全不去真正删除，而是维护一个计数器 $k$，表示"已经发生了多少次全局删除"。那么格子的实际高度就是它的原始高度减去 $k$。

记 $a_i$ 为格子 $i$ 的原始高度（即所有 1 x 操作在它上面的累加，不扣除任何东西）。当发生 $k$ 次全局删除时，实际高度为 $a_i - k$。

用频率数组维护"至少"计数

再维护 $B_h$ = "原始高度 $\ge h$ 的格子个数"。每当 1 x 把 $a_x$ 从 $h-1$ 增加到 $h$ 时，只影响 $B_h$：因为该格子原来就满足 $\ge j$（$j<h$）的条件，而 $\ge j$（$j>h$）的条件它还不满足。所以只需执行 B[a[x]]++。

全局删除发生的条件：每个格子实际高度 $\ge 1$，等价于每个格子原始高度 $\ge k+1$，即 $B_{k+1}=N$。因此 $k$ 就是"满足 $B_j=N$ 的最大 $j$"，也就是所有格子原始高度的最小值。

当一次 1 x 操作把 $a_x$ 增加到 $h$ 且 $B_h=N$ 时，说明此时所有格子的原始高度都 $\ge h$，而刚才那格恰好就是 $h$，所以最小值恰好等于 $h$，令 $k=h$ 即可。注意 $k$ 每次最多增加 $1$（因为最小值每次至多上升 1），所以这个维护是正确的。

回答询问

类型 2 询问 y：答案是"原始高度 $\ge y+k$ 的格子数"，即 $B_{y+k}$（若 $y+k>Q$，显然为 $0$，因为原始高度不可能超过 $Q$）。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    cin >> N >> Q;
    vector<int> a(N + 1, 0);       // 原始高度
    vector<int> B(Q + 2, 0);       // B[h] = 原始高度 >= h 的格子数
    int k = 0;                     // 已发生的全局删除次数
    for (int qi = 0; qi < Q; qi++) {
        int t, x;
        cin >> t >> x;
        if (t == 1) {
            a[x]++;
            B[a[x]]++;
            if (B[a[x]] == N) k = a[x];   // 所有格子原始高度都 >= a[x]
        } else {
            int y = x;
            if (y + k > Q) cout << 0 << '\n';
            else cout << B[y + k] << '\n';
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(N+Q)$
• 空间复杂度：$O(N+Q)$

---

D - Adjacent Distinct String

题目链接：https://atcoder.jp/contests/abc459/tasks/abc459_d

题目大意

给定由小写字母组成的字符串 $S$。判断能否将 $S$ 重排，使得没有两个相邻字符相同；若可以，输出任意一个这样的重排。共 $T$ 组数据，$T \le 3\times 10^5$，总长度 $\le 10^6$。

思路

可行性的判定

记 $n=|S|$，设出现次数最多的字符出现了 $M$ 次。

必要性：若 $M > \lceil n/2 \rceil$，则 $n-M < M-1$：$M$ 个该字符之间需要至少 $M-1$ 个其他字符来隔开，而其他字符总共只有 $n-M$ 个，不够，因此必有某两个该字符相邻，无解。故必须 $M \le \lceil n/2 \rceil = (n+1)/2$。

充分性：当 $M \le \lceil n/2 \rceil$ 时，一定能构造出合法排列（见下面的贪心）。这是经典结论。

贪心构造

维护每个字母剩余的次数 $d[c]$，以及上一次放入的字母 $\mathrm{prev}$。每次从"不等于 $\mathrm{prev}$ 的字母"中挑出剩余次数最多的一个放入答案，并令其次数减一。

为什么贪心永远成功？ 关键在于不变量：

在每次放置之前，任意字母的剩余次数 $d[c] \le \lceil L/2 \rceil$，其中 $L$ 为剩余长度。

初始时由 $M \le \lceil n/2\rceil$ 保证。假设放置前不变量成立，我们放置的是"不等于 $\mathrm{prev}$"中次数最多的字母 $c$（次数为 $m$）：

• $c$ 的次数变为 $m-1$。若 $L=2r$ 为偶数，则 $m\le r$，$m-1\le r-1 < \lceil(2r-1)/2\rceil=r$，成立；若 $L=2r+1$ 为奇数，则 $m\le r+1$，$m-1\le r=\lceil 2r/2\rceil$，成立。
• 其他字母的次数不变。若 $L$ 为偶数，$\lceil L/2\rceil=\lceil(L-1)/2\rceil$，不变显然仍成立。若 $L$ 为奇数（$L=2r+1$），新的上界是 $\lceil(L-1)/2\rceil=r$，唯一需要担心的是某字母次数恰为 $r+1$ 的情形：
  • 它不可能是 $\mathrm{prev}$：$\mathrm{prev}$ 在上一步刚被放置，放置前它的次数为 $r+2$，而那一步的不变量（当时 $L=2r+2$，上界 $r+1$）要求 $r+2\le r+1$，矛盾。
  • 它也不可能是除 $c$ 外的其他字母：$c$ 是"非 $\mathrm{prev}$"字母中次数最多的，若某个非 $\mathrm{prev}$ 字母次数为 $r+1$，则 $m\ge r+1$ 即 $m=r+1$，会出现两个次数为 $r+1$ 的字母，总次数 $\ge 2r+2>L$，矛盾。
    因此唯一可能为 $r+1$ 的字母就是 $c$，而 $c$ 恰好被减掉。不变量保持。

再说明贪心不会"卡死"：若某步只能放 $\mathrm{prev}$（即所有剩余字母都是 $\mathrm{prev}$），则剩余长度 $L=d[\mathrm{prev}]$，由不变量 $d[\mathrm{prev}]\le \lceil L/2\rceil$ 得 $d[\mathrm{prev}]\le 1$。若 $d[\mathrm{prev}]=1$ 且 $L=1$，说明只剩最后一位且它与前一位相同——但若前一状态是 $(L=2,\, d[\mathrm{prev}]=1,\, d[q]=1)$（$q\ne \mathrm{prev}$），贪心一定先放 $q$，所以这种卡死状态根本到不了。因此贪心总能完成。

注意：因为 $\mathrm{prev}$ 被排除在候选之外，如果出现"唯一有剩余次数的字母恰好是 $\mathrm{prev}$"且它次数 $\ge 2$，说明此前的不变量已经被破坏，这在 $M\le\lceil n/2\rceil$ 的前提下不会发生。

实现时每步扫描 26 个字母找最大值即可，总复杂度 $O(26\sum|S|)$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        int n = (int)s.size();
        int cnt[26] = {0};
        for (char c : s) cnt[c - 'a']++;
        bool ok = true;
        for (int i = 0; i < 26; i++)
            if (cnt[i] > (n + 1) / 2) ok = false;
        if (!ok) {
            cout << "No\n";
            continue;
        }
        string ans;
        int prev = -1;
        while ((int)ans.size() < n) {
            int best = -1;
            for (int i = 0; i < 26; i++) {
                if (i == prev) continue;
                if (cnt[i] > 0 && (best == -1 || cnt[i] > cnt[best])) best = i;
            }
            ans += char('a' + best);
            cnt[best]--;
            prev = best;
        }
        cout << "Yes\n" << ans << '\n';
    }
    return 0;
}

官方题解还提供了等价的 Python 实现：

import sys
input = sys.stdin.readline

def solve():
    s = input()[:-1]
    n = len(s)
    cnt = [0] * 26
    for c in s:
        cnt[ord(c) - ord("a")] += 1
    for v in cnt:
        if v > (n + 1) // 2:
            print("No")
            return
    ans = []
    prev = -1
    while True:
        idx = -1
        val = 0
        for i in range(26):
            if i == prev:
                continue
            if val < cnt[i]:
                val = cnt[i]
                idx = i
        if idx == -1:
            break
        ans.append(chr(ord("a") + idx))
        cnt[idx] -= 1
        prev = idx
    print("Yes")
    print("".join(ans))

for _ in range(int(input())):
    solve()

复杂度分析

• 时间复杂度：$O(26 \sum |S|)$
• 空间复杂度：$O(26)$

---

E - Select from Subtrees

题目链接：https://atcoder.jp/contests/abc459/tasks/abc459_e

题目大意

给出一棵以 $1$ 为根的树，顶点 $i$ 有 $C_i$ 个互不相同的糖果。$N$ 只松鼠 $i$ 要从以 $i$ 为根的子树中取出 $D_i$ 个糖果，不同松鼠不能拿同一个糖果。求方案数模 $998244353$；若不可能，输出 $0$。

约束：$N\le 2\times10^5$，$C_i\le 10^9$，$\sum_i D_i\le 10^6$。

思路

关键观察：按后序遍历，逐步计数是独立的

松鼠的选择顺序不影响答案，所以让松鼠按顶点的后序遍历依次取糖。此时处理到顶点 $i$ 时，$i$ 的所有后代（子树内的其他顶点）都已经取完了。

记以 $i$ 为根的子树中：

$$S_i=\sum_{j\in \text{subtree}(i)} C_j,\qquad T_i=\sum_{j\in \text{subtree}(i)} D_j.$$

当轮到松鼠 $i$ 取糖时，它的后代松鼠已经从子树 $i$ 里取走了 $T_i-D_i$ 个糖果（不管它们具体取了哪几个，数量是固定的）。因此子树 $i$ 中仍可选的糖果数为

$$S_i-(T_i-D_i)=S_i-T_i+D_i,$$

于是松鼠 $i$ 的选择数为二项式系数

$$\binom{S_i-T_i+D_i}{D_i}.$$

这个数与后代松鼠的具体选择无关，因此总方案数就是所有 $i$ 的乘积：

$$\text{ans}=\prod_{i=1}^{N}\binom{S_i-T_i+D_i}{D_i}.$$

若存在某个 $i$ 使 $S_i<T_i$（子树糖果不够），则答案为 $0$。

正确性：后序遍历保证每颗糖果只会被"最深的那只松鼠"拿走，方案的计数与按后序的逐步选择形成一一对应，且每一步的候选项数只依赖计数、不依赖具体哪几颗，故乘积公式成立。

计算 $S_i,T_i$

一次自底向上的遍历即可：后序遍历中，处理顶点 $i$ 前，其所有儿子的 $S,T$ 都已算好，直接累加。$N$ 可达 $2\times10^5$，递归可能爆栈，用显式栈做迭代式后序遍历。

计算二项式系数

$n=S_i-T_i+D_i$ 可能高达 $O(\sum C_i)\approx 2\times10^{14}$，远大于模数，因此不能预计算到 $n$ 的阶乘。但 $k=D_i\le 10^6$ 很小，可以用"下降幂"计算：

$$\binom{n}{k}=\frac{n(n-1)\cdots(n-k+1)}{k!}\pmod{998244353}.$$

分子每个因子对模数取模后相乘，分母 $k!$ 预计算阶乘与逆元。总复杂度 $O(\sum_i D_i)$，满足 $\sum_i D_i\le 10^6$。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;

ll modpow(ll b, ll e) {
    ll r = 1;
    b %= MOD;
    while (e) {
        if (e & 1) r = r * b % MOD;
        b = b * b % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<vector<int>> ch(N);
    for (int i = 1; i < N; i++) {
        int p;
        cin >> p;
        ch[p - 1].push_back(i);
    }
    vector<ll> C(N), D(N);
    for (int i = 0; i < N; i++) cin >> C[i];
    for (int i = 0; i < N; i++) cin >> D[i];

    // 预计算阶乘与阶乘逆元，范围到 max D
    ll maxD = 0;
    for (ll d : D) maxD = max(maxD, d);
    vector<ll> fact(maxD + 1), invfact(maxD + 1);
    fact[0] = 1;
    for (int i = 1; i <= maxD; i++) fact[i] = fact[i - 1] * i % MOD;
    invfact[maxD] = modpow(fact[maxD], MOD - 2);
    for (int i = maxD; i >= 1; i--) invfact[i - 1] = invfact[i] * i % MOD;

    // 迭代式后序遍历
    vector<int> order;
    stack<pair<int, int>> st;
    st.push({0, 0});
    while (!st.empty()) {
        auto [v, vis] = st.top();
        st.pop();
        if (vis) {
            order.push_back(v);
            continue;
        }
        st.push({v, 1});
        for (int u : ch[v]) st.push({u, 0});
    }

    vector<ll> S(N, 0), Tsum(N, 0);
    ll ans = 1;
    bool impossible = false;
    for (int v : order) {              // 后序：儿子先于父亲
        ll s = C[v], t = D[v];
        for (int u : ch[v]) { s += S[u]; t += Tsum[u]; }
        S[v] = s;
        Tsum[v] = t;
        if (s < t) { impossible = true; break; }
        ll k = D[v];
        ll top = s - t + k;            // = S_i - T_i + D_i
        ll prod = 1;                   // 下降幂 top*(top-1)*...*(top-k+1)
        for (ll j = 0; j < k; j++) prod = prod * ((top - j) % MOD) % MOD;
        ans = ans * prod % MOD * invfact[k] % MOD;   // 除以 k!
    }
    if (impossible) cout << 0 << '\n';
    else cout << ans << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(N+\sum_i D_i)$
• 空间复杂度：$O(N+\max_i D_i)$

---

F - -1, +1

题目链接：https://atcoder.jp/contests/abc459/tasks/abc459_f

题目大意

给定长度为 $N$ 的序列 $A=(A_1,\ldots,A_N)$。每次操作可以选择 $1\le i\le N-1$，令 $A_i$ 减 $1$、$A_{i+1}$ 加 $1$。求把 $A$ 变成严格递增序列所需的最少操作次数。$T$ 组数据，$\sum N\le 6\times10^5$。

思路

第一步：严格递增 $\to$ 弱递增

令（下标从 0 开始）

$$B_i = A_i - i.$$

则 $A$ 严格递增等价于 $B$ 弱递增：

$$A_i < A_{i+1} \iff B_i < B_{i+1}+1 \iff B_i \le B_{i+1}.$$

（最后一步用了整数性质。）而在 $B$ 的视角下，一次操作仍是"把 1 从位置 $i$ 移到位置 $i+1$"：$B_i$ 减 1、$B_{i+1}$ 加 1，总和不变。问题变成：用最少次"向右搬一个单位"的操作，把 $B$ 变成弱递增序列。

第二步：最优终态是唯一的——按段"压平"

考虑把一段长度 $L$、和为 $S$ 的连续区间压平成弱递增，且尽量"均匀"。满足弱递增、和为 $S$ 的最均匀整数序列是

$$b_j=\left\lfloor \frac{S+j}{L}\right\rfloor,\qquad j=0,1,\ldots,L-1.$$

（它的累加和恰为 $S$：这是经典的"尽量平均分配"。）

官方题解给出这样的结论：存在唯一的分割

$$0=C_0<C_1<\cdots<C_M=N,$$

使得对每段 $[C_k,C_{k+1})$（设段内和为 $S_k$），最终的弱递增序列取

$$B_i=\left\lfloor\frac{S_k+(i-C_k)}{C_{k+1}-C_k}\right\rfloor.$$

直觉上就是把每段"压平"成尽可能均匀的弱递增序列，各段首尾相接仍是弱递增。这个分割可以用贪心（单调栈）构造：从左到右，每个元素先自成一个段 $(len=1, sum=a_i)$；然后反复检查栈顶段与当前段：若栈顶段的最大值大于当前段的最小值，说明接起来不满足弱递增，就把两段合并（长度、和都相加），继续向上检查。

对段 $(L,S)$，其压平后的最小值（第一个元素）是 $\lfloor S/L\rfloor$，最大值（最后一个元素）是 $\lfloor (S+L-1)/L\rfloor$。合并条件即为

$$\left\lfloor\frac{S_{\text{tail}}+L_{\text{tail}}-1}{L_{\text{tail}}}\right\rfloor > \left\lfloor\frac{S_{\text{cur}}}{L_{\text{cur}}}\right\rfloor.$$

注意 $S$ 可能为负，要用向下取整。

第三步：最少操作数 $=\sum i\,(B_i-A_i)$

考虑势能 $\Phi=\sum_i i\,A_i$（0 下标）。一次把 1 从 $i$ 移到 $i+1$ 的操作使 $\Phi$ 恰好增加 1：

$$\Delta\Phi = -i + (i+1) = 1.$$

因此任何把 $A$ 变成 $B$ 的操作序列，其操作次数必然等于 $\Phi(B)-\Phi(A)=\sum_i i(B_i-A_i)$。又因为每一步操作都不改变总和、只把质量右移，最终能到达的弱递增序列正是上述"压平"得到的唯一 $B$（直观地：它让质量尽量留在左边，同时满足弱递增）。于是最少操作数就是

$$\text{ans}=\sum_{i=0}^{N-1} i\,(B_i-A_i),$$

其中 $A_i,B_i$ 都是变换后的值（$B$ 为压平结果）。直接按段展开计算即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll floordiv(ll num, ll den) {  // 向下取整，den > 0
    if (num >= 0) return num / den;
    return -((-num + den - 1) / den);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<ll> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            a[i] -= i;            // B_i = A_i - i，弱递增化
        }
        // 单调栈维护段 (len, sum)，合并违反弱递增的相邻段
        vector<pair<ll, ll>> seg;
        for (ll v : a) {
            ll len = 1, sum = v;
            while (!seg.empty()) {
                auto [plen, psum] = seg.back();
                ll pMax = floordiv(psum + plen - 1, plen);   // 栈顶段的最大值
                ll curMin = floordiv(sum, len);              // 当前段的最小值
                if (pMax <= curMin) break;
                seg.pop_back();
                len += plen;
                sum += psum;
            }
            seg.push_back({len, sum});
        }
        __int128 ans = 0;
        ll idx = 0;
        for (auto [len, sum] : seg) {
            for (ll i = 0; i < len; i++) {
                ll b = floordiv(sum + i, len);   // 段内压平值
                ans += (__int128)idx * (b - a[idx]);
                idx++;
            }
        }
        cout << (ll)ans << '\n';
    }
    return 0;
}

官方题解给出的 Python 实现（思路相同，用队列实现合并）：

from collections import deque
import sys

input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(n):
        a[i] -= i
    d = deque()
    for v in a:
        now = (1, v)
        while d:
            tail = d[-1]
            if (tail[1] + tail[0] - 1) // tail[0] <= now[1] // now[0]:
                break
            now = (now[0] + tail[0], now[1] + tail[1])
            d.pop()
        d.append(now)
    b = []
    for v in d:
        length, s = v
        for i in range(length):
            b.append((s + i) // length)
    ans = 0
    for i in range(n):
        ans += i * (b[i] - a[i])
    print(ans)

复杂度分析

• 时间复杂度：$O(N)$（每段至多入栈出栈一次），总计 $O(\sum N)$
• 空间复杂度：$O(N)$

---

G - Golf 2

题目链接：https://atcoder.jp/contests/abc459/tasks/abc459_g

题目大意

棋盘上有一个棋子，初始在 $(0,0)$。一次操作可以把棋子移到满足 $|x-x'|=A$ 且 $|y-y'|=B$，或 $|x-x'|=B$ 且 $|y-y'|=A$ 的位置 $(x',y')$。判断能否到达 $(X,Y)$，若能，输出最少操作次数，否则输出 $-1$。$T\le 2\times10^5$，$1\le A<B\le10^6$，$0\le X,Y\le10^6$。

思路

（本题官方题解只有文字推导，无样例代码，以下实现依据该算法编写并经过大量对拍验证。）

第一步：gcd 归约与可行性

记 $g=\gcd(A,B)$。每次移动的横、纵坐标变化量都是 $A$ 或 $B$，因此 $X,Y$ 都必须是 $g$ 的倍数；否则输出 $-1$。若都是倍数，把 $A,B,X,Y$ 同除以 $g$，此后 $\gcd(A,B)=1$。

另外还要注意：除以 $g$ 后若 $A,B$ 都为奇数，则每步移动的横、纵坐标奇偶性相同，所以 $X,Y$ 必须同奇偶（$X\equiv Y\pmod 2$）。这个额外条件不需要单独特判，下面的奇偶枚举会自然处理掉。

第二步：把移动建模为符号和，并固定奇偶

把移动分成两类：第一类 $p_1$ 次（$\Delta x=\pm A,\Delta y=\pm B$），第二类 $p_2$ 次（$\Delta x=\pm B,\Delta y=\pm A$）。

设第一类移动中 $x$ 方向的符号和为 $S_{11}$（则其 $x$ 贡献为 $S_{11}A$），$y$ 方向符号和为 $S_{12}$（贡献 $S_{12}B$）；第二类同理为 $S_{21},S_{22}$。则必须满足

$$A S_{11}+B S_{21}=X,\qquad B S_{12}+A S_{22}=Y.$$

同时 $|S_{11}|,|S_{12}|\le p_1$ 且 $S_{11}\equiv S_{12}\equiv p_1\pmod 2$（因为 $p_1$ 次符号求和，奇偶性等于 $p_1$），同理 $|S_{21}|,|S_{22}|\le p_2$ 且 $S_{21}\equiv S_{22}\equiv p_2\pmod 2$。

对给定的 $(S_{11},S_{12})$，最小 $p_1=\max(|S_{11}|,|S_{12}|)$（该值与 $S_{11},S_{12}$ 同奇偶，天然满足奇偶要求）。符号表总是可构造的：设需要 $a=\dfrac{p_1+S_{11}}{2}$ 次 $x$ 符号为 $+$、$b=\dfrac{p_1+S_{12}}{2}$ 次 $y$ 符号为 $+$，取 $\#(+,+)=\max(0,a+b-p_1)$ 即可配平，故无额外约束。于是目标为

$$\min \max(|S_{11}|,|S_{12}|)+\max(|S_{21}|,|S_{22}|),$$

在所有满足上述两个方程的整数解上取最小值。

第三步：固定奇偶组合，用扩展欧几里得参数化

枚举 $c_1=p_1\bmod 2$、$c_2=p_2\bmod 2$（各取 $0/1$，共 4 种组合）。对第一个方程 $Ae_1+Be_3=X$，先用扩展欧几里得求出特解 $(Xu,Xv)$，通解为

$$e_1=Xu+Bt,\quad e_3=Xv-At.$$

枚举 $t\in\{0,1\}$（$t$ 变化 2 不改奇偶性）即可挑出满足 $e_1\equiv c_1$、$e_3\equiv c_2\pmod 2$ 的特解。于是

$$S_{11}=2Bn+e_1,\quad S_{21}=e_3-2An,\qquad n\in\mathbb{Z}.$$

对第二个方程 $Be_2+Ae_4=Y$ 同理（对 $(B,A)$ 做扩展欧几里得）：

$$S_{12}=2Am+e_2,\quad S_{22}=e_4-2Bm,\qquad m\in\mathbb{Z}.$$

若某个 $(c_1,c_2)$ 无法同时满足两个方程的奇偶条件（例如 $A,B$ 均为奇数而 $X+Y$ 为奇数时，任何组合都会失败），则跳过该组合。

于是问题归结为：对每个可行组合，求

$$f(n,m)=\max(|2Bn+e_1|,|2Am+e_2|)+\max(|e_3-2An|,|e_4-2Bm|),\quad n,m\in\mathbb{Z}$$

的最小值，再对全部组合取最小。

第四步：最小化凸分段线性函数 $f$

把定义域放宽到实数 $f(x,y)$。它是凸的、分段线性的、且随 $|x|,|y|\to\infty$ 趋于无穷，因此最小值一定取到。$f$ 的"折痕"（两个 $\max$ 的等值线）由四条直线给出：

$$L_1:2Bx-2Ay=e_2-e_1,\qquad L_2:2Bx+2Ay=-e_1-e_2,$$

$$L_3:2Ax-2By=e_3-e_4,\qquad L_4:2Ax+2By=e_3+e_4.$$

为什么最小值点必是两条折痕的交点？ 设 $g_1(x,y)=\max(|2Bx+e_1|,|2Ay+e_2|)$、$g_2(x,y)=\max(|e_3-2Ax|,|e_4-2By|)$。

• 在非折痕处 $f$ 光滑，$\nabla f=\nabla g_1+\nabla g_2$。而 $g_1$ 的光滑片梯度只可能是 $(\pm2B,0)$ 或 $(0,\pm2A)$，$g_2$ 的只可能是 $(\pm2A,0)$ 或 $(0,\pm2B)$。由于 $A\ne B$，任意两者之和都不为零向量。
• 恰在一条折痕上时，次梯度是连接上述两个方向向量的线段，检查四种折痕情形可知该线段仍不与另一函数的梯度抵消为零。

因此最小值点必须同时落在至少两条折痕上，即四条直线中某两条的交点。只需枚举全部 $\binom42=6$ 个两两交点（$A\ne B$ 保证它们都相交）。

整数解离实数解很近。 官方题解证明：存在整数最小值点 $(n_0,m_0)$ 与某个实数最小值点 $(x_0,y_0)$ 满足

$$|n_0-x_0|\le 2,\qquad |m_0-y_0|\le 2.$$

（证明思路：$f$ 的水平集 $f=K$ 是凸多边形，把 $\max(|x|,|y|)=\max(x,-x,y,-y)$ 展开可知其边斜率只能是 $0,\infty,\pm1$，由此用反证可得该结论。）因此对每个交点，只需检查其 Chebyshev 邻域内的 $5\times 5=25$ 个整数点，取 $f$ 的最小值即可。

交点坐标为有理数，为避免浮点误差，用整数除法精确求 $\lfloor x_0\rfloor$、$\lfloor y_0\rfloor$（分子可能为负，用向下取整），再展开 $[\lfloor x_0\rfloor-2,\lfloor x_0\rfloor+2]\times[\lfloor y_0\rfloor-2,\lfloor y_0\rfloor+2]$。

总结算法流程

1. 若 $g\nmid X$ 或 $g\nmid Y$，输出 $-1$；否则全部除以 $g$。
2. 枚举 $(c_1,c_2)\in\{0,1\}^2$，用扩展欧几里得求出满足奇偶条件的 $(e_1,e_3)$ 与 $(e_2,e_4)$；任一不可行则跳过。
3. 构造四条直线 $L_1\sim L_4$，枚举 6 个交点，对每个交点检查 $5\times5$ 整数邻域内的 $f$ 值。
4. 全部组合中取最小值输出；若无任何可行组合，输出 $-1$。

每组的复杂度为扩展欧几里得的 $O(\log(A+B))$ 加上常数次 $f$ 求值。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;

// 扩展欧几里得：a*x + b*y = gcd(a,b)
ll extgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    ll x1, y1;
    ll g = extgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// 向下取整除法，den > 0
ll floordiv(i128 num, i128 den) {
    if (num >= 0) return (ll)(num / den);
    return (ll)(-((-num + den - 1) / den));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        ll A, B, X, Y;
        cin >> A >> B >> X >> Y;
        ll g = gcd(A, B);
        if (X % g != 0 || Y % g != 0) {
            cout << -1 << '\n';
            continue;
        }
        A /= g; B /= g; X /= g; Y /= g;

        ll u, v, u2, v2;
        extgcd(A, B, u, v);      // A*u + B*v = 1
        extgcd(B, A, u2, v2);    // B*u2 + A*v2 = 1

        const ll INF = (1LL << 62);
        ll best = INF;

        for (int c1 = 0; c1 <= 1; c1++) {
            for (int c2 = 0; c2 <= 1; c2++) {
                // 方程1: A*e1 + B*e3 = X，奇偶性 e1≡c1, e3≡c2 (mod 2)
                ll e1, e3;
                bool ok1 = false;
                for (int t = 0; t <= 1; t++) {
                    ll e1t = X * u + B * t;
                    ll e3t = X * v - A * t;
                    if ((e1t & 1) == c1 && (e3t & 1) == c2) {
                        e1 = e1t; e3 = e3t; ok1 = true; break;
                    }
                }
                if (!ok1) continue;
                // 方程2: B*e2 + A*e4 = Y，奇偶性 e2≡c1, e4≡c2 (mod 2)
                ll e2, e4;
                bool ok2 = false;
                for (int t = 0; t <= 1; t++) {
                    ll e2t = Y * u2 + A * t;
                    ll e4t = Y * v2 - B * t;
                    if ((e2t & 1) == c1 && (e4t & 1) == c2) {
                        e2 = e2t; e4 = e4t; ok2 = true; break;
                    }
                }
                if (!ok2) continue;

                // 折痕直线：
                // L1: 2B x - 2A y = e2 - e1
                // L2: 2B x + 2A y = -e1 - e2
                // L3: 2A x - 2B y = e3 - e4
                // L4: 2A x + 2B y = e3 + e4
                ll al[4] = {2 * B, 2 * B, 2 * A, 2 * A};
                ll bl[4] = {-2 * A, 2 * A, -2 * B, 2 * B};
                ll cl[4] = {e2 - e1, -e1 - e2, e3 - e4, e3 + e4};

                auto eval = [&](ll n, ll m) -> ll {
                    ll t1 = llabs(2 * B * n + e1);
                    ll t2 = llabs(2 * A * m + e2);
                    ll t3 = llabs(e3 - 2 * A * n);
                    ll t4 = llabs(e4 - 2 * B * m);
                    return max(t1, t2) + max(t3, t4);
                };

                // 枚举四条直线的全部两两交点
                for (int i = 0; i < 4; i++) {
                    for (int j = i + 1; j < 4; j++) {
                        i128 det = (i128)al[i] * bl[j] - (i128)al[j] * bl[i];
                        i128 xn = (i128)cl[i] * bl[j] - (i128)cl[j] * bl[i];
                        i128 yn = (i128)al[i] * cl[j] - (i128)al[j] * cl[i];
                        ll fx, fy;
                        if (det > 0) {
                            fx = floordiv(xn, det);
                            fy = floordiv(yn, det);
                        } else {
                            fx = floordiv(-xn, -det);
                            fy = floordiv(-yn, -det);
                        }
                        // 整数最小值点距实数最小值点 Chebyshev 距离不超过 2
                        for (ll n = fx - 2; n <= fx + 2; n++)
                            for (ll m = fy - 2; m <= fy + 2; m++)
                                best = min(best, eval(n, m));
                    }
                }
            }
        }
        if (best == INF) cout << -1 << '\n';
        else cout << best << '\n';
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(\log(A+B))$ 每组数据（扩展欧几里得），另有常数次（约 $4\times 6\times 25$）的 $f$ 求值
• 空间复杂度：$O(1)$

---

（本场题解中的参考代码均已通过官方样例测试；G 题实现额外通过了随机小数据与 BFS/枚举解的暴力对拍。）