亲宝软件园·资讯

展开

CCPC-2020 黑龙江省赛——Let’s Get Married

Xiaojun珺 人气:0

题意:~~

思路:题目给出的数字太少了,我们多写几个,就会发现每层最左边的值等于1.2*k(k+1) ,k代表层数,找规律发现如果一个点的坐标为2.(x,y)且|a|+|b|=k,id<=2*k*(k+1),利用这两个结论我们我们就可以解题了,如果给我们的是id,那么我们二分出该值所在层数,然后这里有个技巧我们吧该值减去上一层最大的值,就可以把id小化,同时方便计算左边,正因为这个处理,我们发现在x周上方的点是左右对称放置的,很容易得到坐标,剩下两个象限里的点,则是安斜对角变化的,第三象限的是从左上到右下依次递减,第四象限的则是从左下到右上依次递减。然后在坐标轴上的点即为id-f(n-1).针对操作二给出坐标求值,就需要用到结论2,先确定上一层的最大值,然后分情况讨论x,y的位置确定id,这些并不复杂,找几个点就能发现其中的规律。要注意的是nowx,nowy是一直在变化的。

AC_Code:

ll nowx,nowy;
ll f(ll x){ //返回当前层大的的元素
    if(x<=0) return 0;
    return 2ll*(1+x)*x;
}
int find(ll id){ //二分找层数
    ll l=0,r=1e9;
    while(l<r){
        ll mid=(l+r)>>1;
        if(f(mid)>=id) r=mid;
        else l=mid+1;
    }
    return l;
}
void solve1(ll id){
    ll n=find(id);
    id-=f(n-1);
    ll x,y;
    if(id==0) x=0,y=0; //原点
    else if(id==1) x=0,y=n;//y轴上
    else if(id<=2*n-1){//x轴上方
        ll t=id/2;
        ll r=id%2;
        if(!r) x=t,y=n-t;
        else x=-t,y=n-t;
    }
    else if(id<=3*n){//第四象限
        id-=2*n;
        y=-id;
        x=n-id;
    }
    else if(id<=4*n){//第三象限
        id-=3*n;
        x=-id;
        y=-(n-id);
    }
    printf("%lld %lld\n",x-nowx,y-nowy);
    nowx=x,nowy=y;
}
void solve2(ll x,ll y)
{
    ll n=abs(x)+abs(y); // |x|+|y|=k,该层最左边的值为2*k(k+1);
    ll id;
    id=f(n-1);
    if(y>0)
    {
        if(x>0) id+=2*abs(x);
        else id+=2*abs(x)+1;
    }
    else
    {
        if(x>=0) id+=2*n+abs(y);
        else id+=3*n+abs(x);
    }
    if(n==0) id=0;
    printf("%lld\n",id);
    nowx=x,nowy=y;
}
void run(){
    ll op=rdll(),x,y,id;
    if(op==1){
        id=rdll();
        solve1(id);
    }
    else{
        x=rdll(),y=rdll();
        solve2(x,y);
    }
}

(训练的时候一直因为是推公式,推了两个小时,都没结果,隔了好几天才补出来)

加载全部内容

相关教程
猜你喜欢
用户评论