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"); }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/549661.html
標籤：其他