反转就是写的非常烂 Awa10 其他还行吧 丢人
A. Ian Visits Mary
如果这两个数的gcd是1 可以直接过去 如果是0 那就绕一个1 过去 变成三角形 不然就用 （1，b-1） 到（a,1) 这样就是两次的1 不会遇到
#include<bits/stdc++.h> #define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const ll MAXN = 3e5+7; const ll mod =1e9+7; const ll inf =0x3f3f3f3f; const ll INF =0x3f3f3f3f3f3f3f3f; int lowbit(int x){ return x&-x; } int gcd(int x,int y){int k=0; if(x<y){k=x;x=y;y=k;}while(x%y!=0){k=x%y;x=y;y=k;}return y;} ll _power(ll a,int b){ll ans=1,res=a;while(b){if(b&1) ans=ans*res%mod;res=res*res%mod;b>>=1;}return ans%mod;} void solve(){ int n,m; cin>>n>>m; if(n==0){ cout<<"2\n"; cout<<1<<" "<<m+1<<"\n"; cout<<0<<" "<<m<<"\n"; } else if(m==0){ cout<<"2\n"; cout<<n+1<<" "<<1<<"\n"; cout<<n<<" "<<0<<"\n"; } else{ int k=gcd(n,m); if(k==1){ cout<<1<<"\n"; cout<<n<<" "<<m<<"\n"; } else{ cout<<2<<"\n"; if(n>m){ int p=1; cout<<n-1<<" "<<1<<"\n"; cout<<n<<" "<<m<<"\n"; } else{ cout<<1<<" "<<m-1<<"\n"; cout<<n<<" "<<m<<"\n"; } } } } int main(){ int t;cin>>t; while(t--) solve(); }
B. Grid Reconstruction
跟着题目给的规律写的 其实因为A拖了一个小时多了 就无所谓了 随便交已发就过了 应该就是交替 还没想到证明 交叉位取的都是正或负交叉 但摆放顺序的影响就不得而知了
#include<bits/stdc++.h> #define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const ll MAXN = 3e5+7; const ll mod =1e9+7; const ll inf =0x3f3f3f3f; const ll INF =0x3f3f3f3f3f3f3f3f; int a[MAXN],b[MAXN]; int lowbit(int x){ return x&-x; } int gcd(int x,int y){int k=0; if(x<y){k=x;x=y;y=k;}while(x%y!=0){k=x%y;x=y;y=k;}return y;} ll _power(ll a,int b){ll ans=1,res=a;while(b){if(b&1) ans=ans*res%mod;res=res*res%mod;b>>=1;}return ans%mod;} void solve(){ int n;cin>>n; deque<int> mins; deque<int> maxs; int flag=1; for(int i=1;i<=n-1;i+=2){ if(flag==1){ mins.push_front(i); flag*=-1; } else{ mins.push_back(i); flag*=-1; } } for(int i=n*2-1;i>n;i-=2){ maxs.push_back(i); } for(int i=1;i<=n;i++){ if(i%2==1){ a[i]=maxs.front(); b[i]=mins.front()+1; } else{ a[i]=mins.front(); mins.pop_front(); b[i]=maxs.front()-1; maxs.pop_front(); if(i==n) b[i]=n*2; } } for(int i=1;i<=n;i++) cout<<a[i]<<" "; cout<<"\n"; for(int i=1;i<=n;i++) cout<<b[i]<<' '; cout<<"\n"; } int main(){ int t;cin>>t; while(t--) solve(); }
C. Ian and Array Sorting
首先 如果给的数是奇数个 那通过很多次变换 肯定可以把后面偶数个的数字变成一样 比如 4 3 2 能变成 3 2 2 后面的偶数个一定能通过+ +比前面大 变成非递减 因此一定正确
如果给的数字是偶数个 除去第一个数 后面的数是奇数个 那么后面奇数个一定能变成递增数列 就把所有的n-2个数都变成最后一个数 递增的也要变 比如 5 2 -3 -1 4 5 因为这样就是这个2能最大变动的范围
然后再比较第一个和第二个数字
#include<bits/stdc++.h> #define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; const ll MAXN = 3e5+7; const ll mod =1e9+7; const ll inf =0x3f3f3f3f; const ll INF =0x3f3f3f3f3f3f3f3f; #define int long long int a[MAXN]; int lowbit(int x){ return x&-x; } int gcd(int x,int y){int k=0; if(x<y){k=x;x=y;y=k;}while(x%y!=0){k=x%y;x=y;y=k;}return y;} ll _power(ll a,int b){ll ans=1,res=a;while(b){if(b&1) ans=ans*res%mod;res=res*res%mod;b>>=1;}return ans%mod;} void solve(){ int n;cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; if(n%2==1) cout<<"YES\n"; else{ if(n==2){ if(a[1]>a[2]) cout<<"NO\n"; else cout<<"YES\n"; return; } int last=a[n]; for(int i=n;i>=3;i--){ if(a[i]==last); else{ int k=a[i]-last; a[i-1]-=k; } } if(a[2]<a[1]) cout<<"NO\n"; else cout<<"YES\n"; } } signed main(){ close; int t;cin>>t; while(t--) solve(); }
D的话一时半会儿写不来 哈哈 2000的题