开发无限

Codeforces Round 865 (Div. 2) A-D

2023-04-10 12:55 由 EdGrass 发表于 #其他

Codeforces Round 865 (Div. 2)

A. Ian Visits Mary

void solve(){
    int x=read(),y=read();

    if(__gcd(y,x)!=1){
        cout<<2<<endl;
        cout<<1<<" "<<y-1<<endl;
        cout<<x<<" "<<y<<endl;
    }else {
        cout<<1<<"\n";
        cout<<x<<" "<<y<<"\n";
    }
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

 

B. Grid Reconstruction

自己写了挺长一串的 这是赛后学习jiangly的代码

void solve(){
    int n=read();
    for(int i=0;i<2;i++){
        for(int j=0;j<n;j++){
            int x;
            if((i+j)&1) x=j+1;
            else x=(j+n-1)%n+n+1;
            cout<<x<<" ";
            if(j==n-1)cout<<"\n";
        }
    }
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

 

C. Ian and Array Sorting

int a[N];
void solve(){
    int n=read(),ans=1;
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    int d;
    for(int i=n-1;i>=2;i--){
        d=a[i]-a[i+1];
        if(d<0)d=0;
        if(d){
            a[i]-=d;
            a[i-1]-=d;
        }
    }
    d=a[1]-a[2];
    if(d<0)d=0;
    if(d&&(n-1)%2==1){
        for(int i=2;i<n;i++){
           if(i!=2) d=a[i-1]-a[i];
           if(d<0)d=0;
            a[i]+=d;
            a[i+1]+=d;
            
        }
    }
    if(a[n]<a[n-1])ans=0;
    puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

 

D. Sum Graph

为了得到排列 需要构建一个易于找到顺序的图 即单链

构造单链的方法：先add(n+1) 后add(n) 这样会得到一条从尾部开始 不断在头尾跳跃的单链

先询问各点与1的距离 再询问各点与“距离1一步的点”(可能有两个 任选一个即可 下文简称j点 )的距离

规定在单链上1到j点的方向为正方向 即可知道每个值的坐标 再将坐标整体加到从0开始 即可得到排列

又因为可能上一条的正方向与实际方向相反 所以需要反着得到另一个排列

int query(int x,int y){
    cout<<"? "<<x<<" "<<y<<endl;
    int res;
    cin>>res;
    return res;
}
void solve(){
    int n=read();
    
    cout<<"+ "<<n+1<<endl;
    int usl;
    cin>>usl;
    cout<<"+ "<<n<<endl;
    cin>>usl;                    //构造单链    
    
    vector<int>a(n),b(n),c(n),p;
    for(int i=2;i<=n;i++){      //查询所有点到1的距离
        a[i-1]=query(1,i);
    }
    
    int j=find(a.begin(),a.end(),1)-a.begin();  //找到与1相邻的点
    b[0]=a[j];      
    for(int i=1;i<n;i++){
        b[i]=query(j+1,i+1);    //查询各点到j点距离
    }
    
    int minn=inf;
    for(int i=0;i<n;i++){        //假定正方向后 判断各点的坐标
        if(a[i]<b[i]){
            c[i]=-a[i];
        }else {
            c[i]=a[i];
        }
        minn=min(c[i],minn);            
    }
    for(int i=0;i<n;i++){
        c[i]-=minn;                //平移各点坐标 让最小值变成0
    }
    
    int l=1,r=n,t=0;
    while(l<=r){
        if(!t){
            p.push_back(r--);
        }else {
            p.push_back(l++);    //构造单链顺序
        }
        t^=1;
    }
    
    cout<<"!";
    for(int i=0;i<n;i++){
        cout<<" "<<p[c[i]];        //按照相对位置输出两种排序
    }
    for(int i=0;i<n;i++){
        cout<<" "<<p[n-1-c[i]];
    }
    cout<<endl;
    cin>>usl;
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

 

 

热门相关：至尊箭神   情生意动   仗剑高歌   有夫之妇   寂静王冠