题解：CF2253D

· · 题解

第一眼感觉是 P17201 类似物，后来发现差异还是有点大的。

该题解中出现的定义

某个点 (px,py) 在图内：指满足 0 \le px \le x,0 \le py \le y。

形式化题面

飞船最初位置在 (0,0)，目标点为 (x,y)，初始速度 (v_x,v_y) 为 (0,0)，每次可以在两种操作中选一种：

  1. 将 v_x 变为 v_x+1，然后 x 方向前进 v_x 单位长度，y 方向前进 v_y 单位长度。
  2. 将 v_y 变为 v_y+1，然后 x 方向前进 v_x 单位长度，y 方向前进 v_y 单位长度。

构造一种方案，使得飞船全程坐标均在图内且终点离目标点的几何距离最近。

解题思路

不难发现，无论每次怎样操作，每次移动的曼哈顿距离是固定的，即第 i 次移动的曼哈顿距离为 i，由此可以确定移动次数 r 为满足 1+2+3+\dots+r=\frac{r \times (r+1)}{2} \le x+y 的最大的 r。

在确定操作次数后，可以证明任意一个满足与起点 (0,0) 曼哈顿距离为 \frac{r \times (r+1)}{2} 的点均可达，只要找出距离目标点曼哈顿距离为 x+y-\frac{r \times (r+1)}{2} 的几何距离最近的点即可。

由函数 f(a)=a^2+(n-a)^2 的单调性可得，终点与目标点沿 x 轴或 y 轴方向距离越接近 \frac{x+y-\frac{r \times (r+1)}{2}}{2}，两点间几何距离越小，因此，理论最佳的终点为 (\frac{x-y+\frac{r \times (r+1)}{2}}{2},\frac{y-x+\frac{r \times (r+1)}{2}}{2})。要注意这个公式得到的终点不一定在图内且坐标不一定是整数。

每一次操作，如果这一次操作选择增加 v_x 之后均选择增加 v_y，最终的 x 轴坐标不大于终点的 x 轴坐标，那么选择增加 v_x，否则选择增加 v_y。按照这种方案操作后飞船的坐标就是终点。

代码如下：

#include <bits/stdc++.h>
using namespace std;
int t,x,y,xx,yy,vx,vy;
int main() {
    scanf("%d",&t);
    while (t--) {
        scanf("%d%d",&x,&y);
        int l=1,r=20000;
        while (l<=r) {
            int mid=(l+r)>>1;
            if (mid*(mid+1)/2<=x+y) l=mid+1;
            else r=mid-1;
        }
        //printf("%d %d\n",l,r);
        int mn=x+y-(r*(r+1)/2);
        int mnx=mn/2;
        int mny=mn-mnx;
        if (mnx>x) {
            mnx=x;
            mny=mn-mnx;
        }
        if (mny>y) {
            mny=y;
            mnx=mn-mny;
        }
        x-=mnx;
        y-=mny;
        //printf("x %d y %d\n",x,y);
        xx=0;
        yy=0;
        vx=0;
        vy=0;
        for (int i=1;i<=r;i++) {
            if (xx+(vx+1)*(r-i+1)<=x) {
                printf("X");
                vx++;
            }
            else {
                printf("Y");
                vy++;
            }
            xx+=vx;
            yy+=vy;
        }
        printf("\n");
        //printf("xx:%d yy:%d\n",xx,yy);
    }
}