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");
}

E. Between

对给出来的ai和bi 总是有bi限制ai

如果限制是一个单向边 可以构成一个类似树的图（可能有除了树枝之外的边）

首先考虑 每个点都在树里

将1看作树根 如果深度为依次为2,3,4,···,n的点集分别记为k(2),k(3),k(4),···,k(n)

只有1的个数受到具体限制 先排列1 一个1则可以有两个k(2) 则可以有三个k(3) ··· 则可以有n个k(n)

所以排列可以为 k(n)+k(n-1)+ ··· +k(2)+k(1)+k(n)+k(n-1)+ ··· +k(3)+k(2)+ ··· +k(n) 明显是有限的

如果不是所有的点都在树里 则可以不断重复 所以是无限的

void solve(){
    int n=read(),m=read();
    vector<vector<int>>g(n);
    for(int i=0;i<m;i++){
        int x=read(),y=read();
        x--;
        y--;
        g[y].push_back(x);            //构建邻接矩阵
    }
    vector<int>d(n,-1),que(1,0);
    d[0]=1;                            
    for(int i=0;i<que.size();i++){    //这个循环相当于一次对树的bfs遍历
        for(int u:g[que[i]]){    
            if(d[u]==-1){            
                que.push_back(u);
                d[u]=d[que[i]]+1;    //记录深度
            }
        }
    }
    if(*min_element(d.begin(),d.end())==-1){    //有点不在树里则直接INFINITE
        cout<<"INFINITE\n";
        return ;
    }
    cout<<"FINITE\n";                
    vector<vector<int>>at(n+1);
    vector<int>seq;
    for(int i=0;i<n;i++){            //构建各深度的点集
        at[d[i]].push_back(i);    
    }
    for(int from =1 ;from <= n;from ++){    //照上面说的序列构成答案
        for(int val=n;val>=from;val--){
            for(int x:at[val]){
                seq.push_back(x);    
            }
        }
    }
    cout<<seq.size()<<"\n";            //输出答案
    for(int i=0;i<seq.size();i++){
        cout<<seq[i]+1<<" ";
    }
    cout<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}