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