题解：CF2253D Hypercarp and Interdimensional Jumps

· · 题解

题目

首先我们发现一个性质，就是每次移动的距离就是当前第几次移动。因为每次移动的距离就是 a+b，最开始移动0步时 a+b=0，每次会先让 a 或者 b 增加一，移动的距离就是 a+b+1，每一步都增加一，所以当前第几次移动的距离就是几。

所以我们可以想到枚举移动的次数 T，总移动距离就是 \frac{T(T+1)}{2}，设为 S，于是 p+q=S。现在我们需要求最优的 (p,q)，使得

(p-x)^2+(q-y)^2

最小，令 q=S-p，于是原式变为

(p-x)^2+(S-p-y)^2\\ =2p^2−2(S+x−y)p+x^2+(S−y)^2

可以求得，当 p=\frac{S+x-y}{2} 时，原式最小，所以 q=\frac{S-x+y}{2}。

所以原问题就变成了给一个起始位置 (0,0) 和目标位置 (p,q)，求怎么构造一个合法的操作序列。

我们先设这个序列有 A 个 X 和 B 个 Y，那么可以想到最大的 p_{max} 就是让 X 全部排在前面，Y 全部在后面，这样的 p_{max} 就是 \sum_{i=1}^Ai+A\times B，因为前面每次都增加 a，增加 A 次，所有的 a 之和就是 \sum_{i=1}^Ai，最后 a 不变，一直增加 b，增加 B 次，所以 a 的和就是 A\times B。p_{min} 就是反过来，让 Y 全排前面，所以 p_{min}=\sum_{i=1}^Ai。我们又可以发现，在一个序列中，如果将某个左边的 X 和右边的 Y 交换，这个序列的 p 就会减一，如果存在一个 Y 的左边还有 X 就可以进行交换。最后就来到了 p_{min} 的序列。所以我们就证明了，可以在 p_{max} 的序列上进行操作，就可以让 p_{max} 连续地变到 p_{min}。所以任意一个 p_{min}\le p\le p_{max} 的整数 p 都可以构造出一个合法序列。

我们可以设 \Delta=p_{max}-p。我们知道，将一个 X 放在全部的 Y 后面，序列会减少 B 的值，将一个 X 移动到 r 个 Y 后面，序列又会减少 r，设我们将 k 个 X 全部移动到 Y 的后面，即 \Delta=kB+r,0\le r<B。这样构造的序列就是：

由于这样构造出来的值就是 p，由于整个序列横坐标加纵坐标的值不变是 S，所以这样构造出来的序列的 q 值就是 S-p。注意需要特判，当 k=A 时，就按照 p_{min} 的方法构造即可。

所以我们只需要先枚举一遍 T，保证 \frac{T(T+1)}{2}\le x+y，找出所有的候选 (p,q)，求出最优的 (p,q) 和对应的 T 值。然后我们再枚举 A，B=T-A，如果 A 和 B 合法，直接构造出最终的序列。时间复杂度是 O(T) 的。其中 T 大概就是 \sqrt{x+y} 的量级，最终的时间复杂度就是 O(tT) 可以通过。

最后还有几个小细节，就是我们求出的 p 可能不是整数，我们还需要看 \lfloor p\rfloor 和 \lceil p\rceil 谁更优；题目说 p 不能超过 x 且 q 不能超过 y，所以 0\le p\le x,0\le S-p\le y，解得 p\in [max(0,S-y),min(x,S)]。所以我们还要看 \lfloor p\rfloor,\lceil p\rceil 是否落在合法区间内，如果都在区间外的话我们就取区间端点 max(0,S-y) 和 min(x,S)。