https://qoj.ac/contest/3729/problem/17343
题目大意
我们要控制一个机器人走到指定的坐标 (x, y)。
- 指令
0代表向右走（x+1），1代表向上走（y+1）。 - 特殊的
2可以被替换成0或1。 - 指令串会无限循环执行。
- 目标：把所有的
2替换掉，使得机器人恰好停在(x, y)，并且最终的字符串字典序最小。
初看这道题，最大的难点在于“无限循环”和“两个维度的坐标限制”，极容易让人陷入模拟走路的死胡同。但只要转过弯来，这就是一道披着图论外衣的代数题。
观察题干
我们发现机器人每次移动，要么向右，要么向上。这意味着它每走一步，横纵坐标之和 x + y 就会加 1。
- 终极推论：机器人走到
(x, y)的总步数是绝对固定的，必须恰好是x + y步！ - 整体到局部：既然总步数是
x + y，如果我们强行安排了恰好x个向右走的0，剩下的步数自然全都是向上走的1。我们根本不需要去管 1，只需要盯死 0 的数量即可！
Hint 1:周期与余数分离
总步数固定了，指令串的长度 n 也是固定的。我们直接做除法：
- 完整执行的轮数：
k = (x + y) / n - 最后一轮多出来的步数：
m = (x + y) % n
此时，我们可以把原始字符串切成两段来看：
- A 段（前 m 个字符）：这部分指令被机器人走过了
k + 1次。 - B 段（剩余 n-m 个字符）：这部分指令被走过了
k次。
Hint 2: 建立方程与贪心求解
假设我们在 A 段里把 u0 个 2 变成了 0，在 B 段里把 v0 个 2 变成了 0。
加上字符串里原本就有的 0，我们要在整个行走过程中凑齐恰好 x 个 0。于是得到一个简单的方程：
(k + 1) * (A段的0总量) + k * (B段的0总量) = x
移项后，我们只需要算出一个剩余目标缺口 (target)，使得：
(k + 1) * u0 + k * v0 = target
如何保证字典序最小？
字典序的规则是：越靠前的字符越小越好。因为 A 段永远在 B 段前面，所以我们的贪心策略极其简单：拼命往 A 段塞 0！
我们直接从大到小枚举 A 段能放的 0 的数量（即 u0），一旦算出来的 v0 是合法的（即能被 k 整除，且不超过 B 段拥有的 2 的数量），这就是我们要找的最优解，直接 break！
(注：别忘了特判 k=0 的情况。如果 k=0，说明机器人根本没走到 B 段，B 段全填 0 白嫖一个最小字典序即可。)
代码
点击查看代码
//
// Created by awake on 2026/5/17.
//
#include <bits/stdc++.h>
using namespace std;// clang-format off
struct { auto operator()(auto &i) { cin >> i; } } IN; // NOLINT
struct { auto operator()(auto &i) { cout << i << ' '; } } OUT; // NOLINT
// clang-format on
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr)// NOLINT
// #define int long long
using pii = pair<int, int>; //NOLINT
using ll = long long; //NOLINT
template <typename T>
using vec = vector<T>; //NOLINT// #define endl '\n'
constexpr int INF = 0x3f3f3f3f;
constexpr int MOD = 998244353;
constexpr int N = 1e6 + 5;
const int K = [] //NOLINT
{random_device rd;return (static_cast<ll>(rd()) << 32) | rd();
}();void solve()
{ll n, x, y;cin >> n >> x >> y;string s;cin >> s;ll S = x + y;ll k = S / n;ll m = S % n;ll A0 = 0, A2 = 0;ll B0 = 0, B2 = 0;for (ll i = 0; i < m; ++i){if (s[i] == '0') A0++;else if (s[i] == '2') A2++;}for (ll i = m; i < n; ++i){if (s[i] == '0') B0++;else if (s[i] == '2') B2++;}ll target = x - (k + 1) * A0 - k * B0;ll best_u0 = -1;ll best_v0 = -1;for (ll u0 = A2; u0 >= 0; --u0){ll rem = target - (k + 1) * u0;if (k > 0){if (rem >= 0 && rem % k == 0){ll v0 = rem / k;if (v0 <= B2){best_u0 = u0;best_v0 = v0;break;}}}else{if (rem == 0){best_u0 = u0;best_v0 = B2;break;}}}if (best_u0 == -1){cout << -1 << "\n";return;}string res = s;ll u_placed = 0;for (ll i = 0; i < m; ++i){if (res[i] == '2'){if (u_placed < best_u0){res[i] = '0';u_placed++;}else{res[i] = '1';}}}ll v_placed = 0;for (ll i = m; i < n; ++i){if (res[i] == '2'){if (v_placed < best_v0){res[i] = '0';v_placed++;}else{res[i] = '1';}}}cout << res << "\n";
}signed main()
{IOS;int T;cin >> T;while (T--)solve();return 0;
}套路总结
套路一：网格行走中的“步数守恒定律”
- 特征：题目限定了只能向正方向走（如右和上，或者下和右），且要求到达某个具体坐标。
- 解法：总步数必然是曼哈顿距离。立刻将二维坐标要求降维成一维计数。只要搞定其中一个维度的数量，另一个维度自然满足。代码里的
if-else会瞬间少一半。
这个套路在跳青蛙那道题也出现过https://www.cnblogs.com/butaihuia/p/20065585
遇到这种题应该优先往总和上想。
套路二：无限循环模式下的“商余分离法”
- 特征：题目出现“周期性”、“无限循环”、“不断重复直到某条件”的字眼，且数据范围极大（例如本题坐标达到 \(10^{18}\)）。
- 解法：绝不能暴力模拟。立刻算出总需求，然后通过取商 ( / ) 和 取模 ( % )，将问题转化为“完整的 \(k\) 圈”加上“最后残缺的 \(m\) 步”。将整体数据拆分为被执行 \(k+1\) 次的前缀，和被执行 \(k\) 次的后缀。
套路三：字典序最小问题的“优先级贪心”
- 特征：题目不仅要求找出一个解，还要求“字典序最小”或“数值最大/最小”。
- 解法：将可用资源分为“高权重区”（如本题的 A 段，在字符串最前面）和“低权重区”（B 段）。永远从极致状态开始尝试。比如本题，我们直接倒序枚举
u0（从最大可能值开始），这样碰到的第一个可行解，在数学上绝对是字典序的全局最优解，省去了复杂的全量比较。