目录

刷题记录(Codeforces Round 947 （Div. 1 + Div. 2）前三题)

1.A. Bazoka and Mocha's Array

2.B. 378QAQ and Mocha's Array

3.C. Chamo and Mocha's Array

---

刷题记录(Codeforces Round 947 （Div. 1 + Div. 2）前三题)

1.A. Bazoka and Mocha's Array

输入

3
6
1 1 4 5 1 4
5
7 9 2 2 3
3
1 2 3

输出

No
Yes
Yes

题目意思是，要求我们将数组分成两部分(已经是非递减则不用分)，按照任意拼接两部分成为一个新的数组，使新拼接的数组非递减。

数据范围较小，可以判断每个分开的位置。判断结果为Yes需要满足下面两个要求。

1.两个部分的数组都是非递减的。

2.一部分的数组的最小值大于等于另一个部分的最大值，或者最大值小于等于另一个部分的最小值。

下面是AC代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve()
{
	int n;
	cin>>n;
	vector<int>a(n);
	for(int &i:a)
	cin>>i;
	if(n==2)
	{
		cout<<min(a[0],a[1])<<"\n";
		return;	
	}
	ll ans=-1;
	for(int i=0;i<n-2;i++){
		int p[3];
		p[0]=a[i];
		p[1]=a[i+1];
		p[2]=a[i+2];
		sort(p,p+3);
		ans=max(ans,(ll)p[1]);
	}
	cout<<ans<<"\n";
}
int main()
{
	int t;
	cin>>t;

	while(t--){
		solve();
		
	}
	return 0;
}

2.B. 378QAQ and Mocha's Array

 

输入

4
3
7 3 8
5
7 1 9 3 5
5
4 12 2 6 3
5
7 49 9 3 1000000000
 

输出

No
Yes
Yes
No

题意：题目要求我们找到两个数，使得整个数组的每个数都可以被两个数至少一个整除。

思路：因为是整除关系，小数一定不能被大数整除，所以从最小数下手。

找到的第一个数一定是数组的最小数，第二个数为能被第一个数整除的最小数。

下面是AC代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve()
{
	ll n;
	cin>>n;
	vector<ll>a(n);
	for(ll &i:a)
	{
		cin>>i;
	}
	if(n<=2)
	{
		cout<<"Yes\n";
		return;
	}
	bool ans=true;
	sort(a.begin(),a.end());
	ll b,c;
	b=a[0];
	int f=0,f1=0;
	for(int i=1;i<n;i++){
		if(a[i]!=a[i-1]) 
		{
			f=1;
		}
		if(a[i]%b!=0&&f==1)
		{
			f1=1;
			c=a[i];
			break;
		}
	}
	if(f==0||f1==0)
	{
		cout<<"Yes\n";
		return ;
	}
	for(ll i=2;i<n;i++){
		if(a[i]%b!=0&&a[i]%c!=0) 
		{
			ans=false;
			break;
		}
	}
	cout<<(ans?"Yes\n":"No\n");
}
int main()
{
	int t;
	cin>>t;
	
	while(t--){
		solve();
	}
	return 0;
}

3.C. Chamo and Mocha's Array

输入

2
2
1 2
5
1 2 3 4 5

输出

1
4

题意：对于整个数组，我们可以选择一个范围（l,r），将这个范围内的数全部变为这个范围内的中位数，可以进行多次操作或者不做操作，求最后的数组的全部元素的最大值。

思路：因为当选择的范围长度是2时，就可以将这个范围的两个数全部变为这两个数的较小值(x)，那么一定存在一个长度为3的范围内的中位数<=x。

如果整个数组的长度为2，输出较小值即可，反之，遍历数组全部长度为3的子数组，找到最大的中位数，然后输出。

下面是AC代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve()
{
	int n;
	cin>>n;
	vector<int>a(n);
	for(int &i:a)
	cin>>i;
	if(n==2)
	{
		cout<<min(a[0],a[1])<<"\n";
		return;	
	}
	ll ans=-1;
	for(int i=0;i<n-2;i++){
		int p[3];
		p[0]=a[i];
		p[1]=a[i+1];
		p[2]=a[i+2];
		sort(p,p+3);
		ans=max(ans,(ll)p[1]);
	}
	cout<<ans<<"\n";
}
int main()
{
	int t;
	cin>>t;

	while(t--){
		solve();
		
	}
	return 0;
}