A-先交换
总共统计三种情况:
- 第一个数是奇数,交换0次
- 第一个数是偶数
- 后面有奇数,交换1次
- 后面也没有奇数,无法交换(-1)
#include<iostream> #include<map> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define PII pair<int,int> #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define int long long using namespace std; const int N = 5e5+10; const int MOD = 1e9+7; int a[N]; void solve() { int n; cin>>n; bool f = false; for(int i=1;i<=n;i++) { cin>>a[i]; if(i>1&&a[i]<a[1]&&(a[i]&1)) f=true; } if(a[1]&1) cout<<0<<endl; else if(!(a[1]&1) && !f) cout<<-1<<endl; else if(!(a[1]&1) && f) cout<<1<<endl; } signed main(){ IOS; int T=1; cin>>T; while(T--) solve(); return 0; }
B-再交换
从前往后比较,看第一个不相同的数
对于这个第一个不同的数
- 如果A[i] > B[i],说明A>B,交换该位置的数,使得A<B
- 如果A[i] < B[i],说明 A<B
- 如果 i=1 ,那么后面随便找个数交换,就可以使得 A<B 保持不变
- 如果 i!=1,那么前面位置肯定都是相同的,随便找个位置交换也可以使得 A<B 保持不变
#include<iostream> using namespace std; void solve() { int n,x,y; string a,b; cin>>n>>a>>b; a="-"+a; b="-"+b; for(int i=1;i<=n;i++) { if(a[i]==b[i]) continue; else if(a[i]>b[i]) { x=i; y=i; break; }else if(a[i]<b[i]) { if(i==1) { x=n; y=n; }else { x=1; y=1; } break; } } cout<<x<<" "<<y<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int _; cin>>_; while(_--) solve(); return 0; }
C-空间骑士
两种情况
- 首到尾必定1e6长度大小(中间某个片段大小就无所谓了)
- 折返
- 0和1位置,小骑士从0位置开始,跑到最右边那个吉欧位置,收集一下,其他的吉欧顺便就收集了,在跑回到1位置
- 1e6和1e6-1位置,小骑士从1e6位置开始,跑到最左边那个吉欧位置,收集一下,其他的吉欧顺便就收集了,在跑回到1e6-1位置
坑点:
s和p位置能相同,因此不能是1和1,以及1e6和1e6.
其他的路程必定属于上述情况的一部分
#include<iostream> #include<algorithm> using namespace std; const int N = 2e5+10; int a[N]; void solve() { int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n); if(n==1&&a[1]==500000000) cout<<"0 1000000000"<<endl; else { int x=a[n]-1+a[n]; int y=1000000000-1-a[1]+1000000000-a[1]; int z=1000000000; if(z>=x&&z>=y) cout<<"0 1000000000"<<endl; else if(x>=y&&x>=z) cout<<0<<" "<<1<<endl; else if(y>=x&&y>=z) cout<<1000000000<<" "<<1000000000-1<<endl; } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int _=1; // cin>>_; while(_--) solve(); return 0; }
D-障碍
暴力吧 (我也不会其他解法)
记录每一个断点的位置(0和n位置也算断点) ,存到数组0~m+1下标中
a[0]=0 , a[1]~a[m]是读入 , a[m+1]=n
这样把每一个区间都可以用 a[j] - a[i] 来表示,
区间内断点数量为 j-i-1
优化:
- 区间内断点的数量的平方必须小于等于n,否则 L-x*x < 0,即一定不是答案
- 我用的算啥…~~(双指针?)~~看看就得了,我也不知道这叫啥
#include<iostream> #include<cmath> #include<algorithm> using namespace std; const int N = 2e5+10; int a[N]; void solve() { int n,m,mx=0; cin>>n>>m; int t = sqrt(n); a[0]=0; for(int i=1;i<=m;i++) cin>>a[i]; m++; a[m]=n; for(int i=1;i<=m;i++) { for(int j=i-1;j>=0&&(i-j-1)<=t;j--) { mx = max(mx,a[i]-a[j]-(i-j-1)*(i-j-1)); } } cout<<mx<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int _=1; // cin>>_; while(_--) solve(); return 0; }
E-生成树与路径
这道题怎么说,我是看了题解的
我原本的想法是这个图
但是不对,因为比如1 ~ 4 <1 ~ 2 ~ 3 ~ 4,所以1 ~ 2 ~ 3 ~ 4就不是最短路了
题解给出的这个图
可以保证比如1节点开始生成最小树,那么这条边一定是1 ~ 2,同理2开始一定是2 ~ 1和2 ~ 3
#include<iostream> #include<cmath> #include<algorithm> using namespace std; const int N = 2e5+10; int s[N]; void solve() { int n,m,x=1; cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j+i<=n;j++) { if(!m) return ; cout<<j<<" "<<j+i<<" "<<x++<<endl; m--; } } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int _=1; cin>>_; while(_--) solve(); return 0; }
F-球球大作战
规律是删除一个球后,每次选最大的两个进行合并,最终合并成的一个球,体积最小
删除小的球可以的话,删除大的球自然也可以
eg: 2 5 6 ,删除2的话 ,剩下的球合并为5,删除5的话 ,剩下的球合并为3 < 5,删除6的话 ,剩下的球合并为3 < 5
所以可以预先二分找出最小的满足条件的那个球,比他大的自然都可以
#include<iostream> #include<cmath> #include<algorithm> using namespace std; const int N = 1e5+10; int n,s; int a[N],b[N]; bool check(int po) { int la; if(po==n) { la=b[n-1]; for(int i=n-2;i>=1;i--) { la = la+b[i] >>1; } }else { la=b[n]; for(int i=n-1;i>=1;i--) { if(i==po) continue; la = la+b[i] >>1; } } return la<=b[po]; } void solve() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; b[i]=a[i]; } sort(b+1,b+1+n); int l=1,r=n; while(l<r) { int mid = l+r >>1; if(check(mid)) { r=mid; }else { l=mid+1; } } // cout<<b[r]<<endl; for(int i=1;i<=n;i++) { cout<<(a[i]>=b[r] ? 1: 0 ); } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int _=1; // cin>>_; while(_--) solve(); return 0; }
