Robot Arms(AtCoder-4432)(二进制构造,数学归纳证明,贪心策略)
前言
一道极为好的题,这思路我打包票比赛时写不出来…
题目
传送门:
Vjudge
Atcoder
题目大意:
现在你有n个点,然后让你构造一个长度为m的序列,序列中是每一次移动的距离,输出这个序列,你对每个点对()每一次从原点出发执行m此操作,对于每一个指令你可以上下左右任选一个方向走长度,执行完命令后恰好落到(),输出对于每一点对的操作方式(‘U’,‘D’,‘L’,‘R’)
数据范围:
思路
构造长度
我们可以由我们的‘常识’和联想可以知道,二进制解决这种题一直都十分有优势,所以我们可以尝试从二进制构造入手,我们就让边长集合我们发现
只有最多只有29位,那是不是意味着我们k只用29就够了呢?其实我们的k要30才行,为什么呢?因为我们有两个坐标约束,但其实你开30以上也没有问题…呵呵呵,后面证明了一大堆,自己往下看吧.
注意,到了这里,过程思路要综合看一看…
奇偶性判断无解
我们发现,我们所构造的线段中只有1为奇数,剩下的都是偶数,那么我们对于一个坐标()而言()()()()当时是不会改变x+y的奇偶性的,那么我们如果走了1这条边,由于起点(0,0),0+0=0为偶数,所以下一个点变为奇数,为我们只走一次1,剩下只走偶数,所以之后x+y奇偶性不变,恒为奇数
那如果要走x+y为偶数的点呢?我们有两种方法思考
把1去掉
我们发现,我们仅仅是满足了x+y为偶数,但x,y仍奇偶性单独不确定,例如去掉后(1,1)就走不到了,所以这种方法不行
我们还可以想一下,就算所有x,y均为偶数,那么实际上我们又可以把整个坐标系缩小2倍,这又等价于我们要解决的问题,就是个极为难以实现的递归问题了
加一个1
这将原来x+y和为奇数前提上又转化为偶数,显然是可以的
那如果又有x+y为奇数,又有x+y为偶数的点显然就无解了
证明
能用边长集合走到范围内所有的x+y为奇数的点。
用一幅图就是这样:
我们用数学归纳法证明:
令d(k)表示采用边集合所能走到的范围
当时,显然成立
当时,我们可以用一用下面这一幅图,中间的小的正方形表示d(k-1),外面大的正方形表示d(k)
我们把小正方形切割成四块,我们关注内部最靠上的小正方形即可以将它向左、上、右,四个方向平移现在边的长度得到下面的图形:
那么对于剩下三个也这么操作后的范围我们都可以走到了
但是我们还不知道能否依旧走的到
我们可以假设落到红色正方形中,我们之前就可以先到d(k-1)中下部的小正方形,然后再向上走即可
那么对于一个k而言,d(k)里所有为x+y为奇数的点都可以走到了
如果是偶数你多的一条长度为1的边,随便上下左右动一动就好了…
贪心走法
这个就跟LCA深度相同后找祖先差不多…
走法:将所有边集合降序排序,每次对于一点(),让x,y绝对值较大的一个用此时便使它尽量变小(加或减)后总能到(0,0)
说得有点绕,看下面吧:
感觉跟上面的差不多…但这是倒着来的
令d(k)表示采用边集合所能走到的范围,(x,y)为此时的点坐标
我们首先要知道,这点很重要
当时,显然成立
当时,分两种情况
①当(x,y)为d(k-1)外部时:
注意,现在我们移动距离是大正方形对角线长的四分之一的,不要搞混了
显然,往小正方形里面移动就是了,因为,把坐标中绝对值较大的绝对值变小就可以了
②当(x,y)为d(k-1)内部时:
还是直接让绝对值较大的变小就是了
如果都为偶数多的长度为1的边,在d(0)时也是显然可以的…
那这就说完了。。。
代码
#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<climits>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
int read(){
int f=1,x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
return x*f;
}
#define MAXN 1000
#define INF 0x3f3f3f3f
int n,len,x[MAXN+5],y[MAXN+5],d[35];
void Print(int X,int Y){//贪心策略
for(int i=1;i<=len;i++){
if(abs(X)>abs(Y)){
if(X>0) putchar('R'),X-=d[i];
else putchar('L'),X+=d[i];
}
else{
if(Y>0) putchar('U'),Y-=d[i];
else putchar('D'),Y+=d[i];
}
}
puts("");
return ;
}
int main(){
bool f[2]={0};
n=read();
for(int i=1;i<=n;i++)
x[i]=read(),y[i]=read(),f[(x[i]+y[i])%2]=1;
if(f[0]&&f[1]){//判断奇偶有无解
puts("-1");
return 0;
}
for(int i=30;i+1;i--)
d[++len]=(1<<i);
if(f[0]) d[++len]=1;//奇偶处理
printf("%d\n",len);
for(int i=1;i<len;i++)
printf("%d ",d[i]);
printf("%d\n",d[len]);
for(int i=1;i<=n;i++)
Print(x[i],y[i]);
return 0;
}
题外话
如果你还不懂,或者不习惯作者的语言(hhh),你还可以看下面这一篇网上路人甲写的…(觉得他并没我写得好…)
有关构造证明
请用你的手指轻轻地点个赞~