2024寒假训练营5

1. E题

代码运行如下：

#include<bits/stdc++.h>
#define ll long long
using  namespace std;
const ll  N =1e5+5;

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	ll t;
	cin>>t;
	while(t--){
		ll n;
	cin>>n;
	ll a[N];
	for(ll i=1;i<=n;i++){
		cin>>a[i];
	}
	int t=0;
	if(n%2==0){
		t=0;
	} /*偶数个数据可以整体加无线次，总能变成非降序*/
	
	else{
		ll r=0; /*r为所对应的数据能容忍的最大操作数*/
		for(ll i=n-1;i>=1;i-=2){ /*因为后面的数据处理会影响到前面的数据，所以从后面开始处理数据*/
		ll lst=a[i+1]-a[i]+r;
		if(lst<0){
			
			t=1;
			break;
		}
		lst=lst/i;
		r+=lst;
		if(a[i-1]>a[i]+r){
			t=1;
			break;
		}
		
	}
	
	}
		if(t==0) cout<<"YES"<<'\n';
		else cout<<"NO"<<'\n';
	}
	
	return 0;
}

2. F题

这道题与上面的题目类似，多了一步输出最少操作次数，没想到这么简单，还想了好久。:(

代码如下：

#include<bits/stdc++.h>
#define ll long long
using  namespace std;
const ll  N =1e5+5;

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	ll t;
	cin>>t;
	while(t--){
		ll n;
		cin>>n;
		ll a[N];
		ll r=0,ans=0;
		for(ll i=1;i<=n;i++){
			cin>>a[i];
		
		}
		
		for(ll i=1;i<n;i++){
			ans=max(a[i]-a[i+1],ans);
			
		}
		int t=0;
		if(n%2==0){
			t=0;
		} 
		else{
			r=0;
			for(ll i=n-1;i>=1;i-=2){
				ll lst=a[i+1]-a[i]+r;
				if(lst<0){
					t=1;
					break;
				}
				lst=lst/i;
				r+=lst;
				if(a[i-1]>a[i]+r){
					t=1;
					break;
				}
				
			}
	
		}
		if(t==1) cout<<"-1"<<'\n';
		else cout<<ans<<'\n';
	}
	
	return 0;
}

3. H题

这个感觉像是贪心。
代码运行：

#include<bits/stdc++.h>
#define ll long long
using  namespace std;
const ll  N =1e6+5;
bool prime(ll n){
	for(ll i=2;i*i<=n;i++){
		if(n%i==0) return false;
	}
	return true;
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	ll n,b;
	cin>>n;
	b=n;
	ll a[N];
	ll pt;
	while(n>0){
		for(pt=1;pt<=n;pt++){
			if(prime(pt+n)){
				break;
			}
		}
		for(ll i=pt;i<=n;i++){
			a[i]=n+pt-i;
		}
		n=pt-1;
	} 
	for(ll i=1;i<=b;i++){
		cout<<a[i]<<" ";
	}
	
	 
}

4. J题

利用区间合并的方法。
代码运行：

#include<bits/stdc++.h>
#define ll long long
using  namespace std;
const ll  N =1e5+5;
void solve(){
	int n;
	cin>>n;
	ll l[N],r[N];
	for(int i=0;i<n;i++){
		cin>>l[i]>>r[i];
	}
	ll ans=0;
	ll L=l[0],R=r[0]; 
	for(int i=1;i<n;i++){
		L=max(L,l[i]);//取最大左边界
		R=min(R,r[i]);//取最小右边界
		//如果新的区间与原来的区间有交集，则ans的增加量为0。
		if(L>R){
			ans+=L-R;
			L=max(R,l[i]);
			R=L;
			//如果没有交集，重新定义区间为新的区间离原区间最近的位置。
		}
	}
	cout<<ans;
	
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	ll t=1;
	while(t--){
		solve();
	}
	
	return 0;
}