题解：P17295 [ICPC 2026 Xi'an I] Operating Robot

· · 题解

机器人每一步只会向右或向上移动，因此若能到达 (x,y)，必然恰好发生在执行完第 m=x+y 条指令的时刻。设替换后整串中 0 的个数为 a，并令

k=\left\lfloor\frac mn\right\rfloor,\qquad r=m\bmod n,

即前 m 步由 k 个完整循环与一个长度为 r 的前缀组成，那么前 m 步中 0 的总数为 k\cdot a+z，其中 z 是串的前 r 个字符里 0 的个数；那么必须等于 x，于是得到关键约束

z=x-k\cdot a.

由此可行性只由总量 a 决定。记全串中固定 0 与 2 的个数分别为 f_0,F，前 r 位中固定 0 与 2 的个数分别为 g_0,g_2，后缀对应为 h_0,h_2。前 r 位里需要由 2 变成 0 的个数为 w=z-g_0，后缀里需要由 2 变成 0 的个数为 t=a-z-h_0，二者都必须落在各自可用的 2 数量之内，连同总量本身的界限 f_0\le a\le f_0+F，全部整理成关于 a 的区间上下界即可；若下界大于上界则无解，输出 -1。

由于 z=x-ka 随 a 的增大而严格减小，取越小的可行 a，前缀中能变成 0 的那么 2 就越多，而把 2 填成 0 越靠前字典序越小，因此直接取可行区间的最小下界作为 a，再从左到右贪心：前 r 位中把最先遇到的 w 个 2 填成 0、其余填 1，后缀中把最先遇到的 t 个 2 填成 0、其余填 1，得到的即为字典序最小的答案。特殊情形单独处理：当 k=0 时目标落在第一圈内，只需保证前 r=m 位恰好有 x 个 0 而后缀全部填 0；当 (x,y)=(0,0) 时机器人原地即达，把所有 2 替换成 0 即可。总复杂度 O(n)。