Daily Practice：Codeforces Round ＃794 (Div. 2)（A~D）

VP*n,, Mainly this one cf Time is too dark hhhhh

A. Everything Everywhere All But One

give n Number , choice n-1 Number , And replace each of these numbers with the average of these numbers ,  Ask whether you can make the numbers in the array equal through several operations .

Ideas ： Since you have to choose n-1 Change the number to the average , Then meet this n-1 The average of the number is the average of the entire array , And the unselected number is this average . Pay attention to double Keep accuracy .

A Code：

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
typedef long long ll;
const int mod=1e9+7;
const int N=55;
int t,n;
double a[N];

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>t;
    while(t--){
    	std::cin>>n;
    	double sum=0;
    	std::map<double,int>mp;
    	for(int i=1;i<=n;i++){
    		std::cin>>a[i];
    		mp[a[i]]++;
    		sum+=a[i];
    	}
    	std::cout<<(mp[sum/n]?"YES":"NO")<<'\n';
    }
    return 0;
}

B. Odd Subarrays

Give the array , How to segment an array , Make as many inverse pairs of subarrays as possible odd .

Ideas ： greedy , Since it satisfies the inverse order, the pair is odd , As long as there is an inverse pair , Then divide it .

AC Code：

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
typedef long long ll;
const int mod=1e9+7;
const int N=1e5+5;
int t,n;
int a[N];

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>t;
    while(t--){
    	std::cin>>n;
    	for(int i=1;i<=n;i++){
    		std::cin>>a[i];
    	}
    	int ans=0;
    	for(int i=1;i<n;i++){
    		if(a[i]>a[i+1]) ans++,i++;
    	}
    	std::cout<<ans<<'\n';
    }
    return 0;
}

os： At first, because the array is smaller T A hair , cause sb. to die of anger QWQ

C. Circular Local MiniMax

  Give a sequence of numbers , Whether it can be satisfied by rearranging the elements in the array ： End to end , Any element is greater than or less than two adjacent numbers .

Ideas ： First , When the number of array elements is odd , It cannot be constructed ; Then sort the array , Divided into two parts , One large and one small are placed crosswise , Finally, it is judged that the conditions are met .

AC Code：

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
typedef long long ll;
const int mod=1e9+7;
const int N=1e5+5;
int t,n;
int a[N],ans[N];

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>t;
    while(t--){
    	std::cin>>n;
    	memset(ans,0,sizeof(ans));
    	int cnt=0;
    	for(int i=1;i<=n;i++){
    		std::cin>>a[i];
    	}
    	if(n&1){
    		std::cout<<"NO"<<'\n';
    		continue;
    	}
    	std::sort(a+1,a+1+n);
    	std::vector<int>vecs,vecl;
    	for(int i=1;i<=n/2;i++){
    		vecs.push_back(a[i]);
    	}
    	for(int i=n/2+1;i<=n;i++){
    		vecl.push_back(a[i]);
    	}
    	for(int i=0;i<n/2;i++){
    		ans[++cnt]=vecs[i];
    		ans[++cnt]=vecl[i];
    	}
    	bool flag=true;
    	ans[0]=ans[cnt];
    	ans[++cnt]=ans[1];
    	for(int i=1;i<=n;i++){
    		if(!(ans[i]>ans[i+1]&&ans[i]>ans[i-1]||ans[i]<ans[i+1]&&ans[i]<ans[i-1])){
    			flag=false;
    			break;
    		}
    	}
    	if(!flag){
    		std::cout<<"NO"<<'\n';
    		continue;
    	}
    	std::cout<<"YES"<<'\n';
    	for(int i=1;i<=n;i++){
    		std::cout<<ans[i]<<" \n"[i==n];
    	}
    }
    return 0;
}

os： Very unexpected , This time C It's not difficult

D. Linguistics

give A,B,AB,BA The number of four elements , Give the string s, Judge whether the given element can form the string .

Ideas ： Study Big guy's idea ！（ This guy actually fought this scene cf,tqlllllll）

First, if the given element A and B The number of does not match , That must be impossible ; The data range is large , We can't enumerate directly , Then we can adopt this idea ： Find the minimum number of elements of each kind , Compare them separately .

Let's use double pointers to intercept something like ABAB,BABA Such substrings that are different from each other . about A and AB, We can work out the minimum required quantity together , and B and BA It's the same calculation .

There are only two kinds of even length substrings , namely ABAB and BABA, about BABA In this way , No need AB Elements , and ABAB By reducing a pair of separate A and B To become BABA Similar to substring . Only if there is no single pair A and B, It needs to len/2 individual AB, Then we can use pairs of separate A and B To minimize AB Dosage , Work out AB Minimum dosage . For odd length substrings , We can reduce A or B Make it into the above two seed strings , Use the same treatment .

AC Code：

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
typedef long long ll;
const int mod=1e9+7;
const int N=1e5+5;
int T;
int a[6];
std::string s;

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>T;
    while(T--){
    	for(int i=1;i<=4;i++){
    		std::cin>>a[i];
    	}
    	std::cin>>s;
    	int cntA=0,cntB=0;
    	int len=s.length();
    	for(int i=0;i<len;i++){
    		if(s[i]=='A') cntA++;
    		else cntB++;
    	}
    	if(!(cntA==a[1]+a[3]+a[4]&&cntB==a[2]+a[3]+a[4])){
    		std::cout<<"NO"<<'\n';
    		continue;
    	}
    	int cntab=0,cntba=0;
    	std::vector<int>ab,ba;
    	for(int i=0;i<len;i++){
    		int j=i;
    		while(j+1<len&&s[j+1]!=s[j]) j++;
    		if(j-i+1&1){
    			if(s[i]=='A') a[1]--;
    			else a[2]--;
    		}
    		else{
    			int t=j-i+1>>1;
    			if(s[i]=='A') ab.push_back(t),cntab+=t;
    			else ba.push_back(t),cntba+=t;
    		}
    		i=j;
    	}
    	if(a[1]<0||a[2]<0){
    		std::cout<<"NO"<<'\n';
    		continue;
    	}
    	int t=std::min(a[1],a[2]);
    	std::sort(ab.begin(),ab.end());
    	while(!ab.empty()&&t){
    		t--;
    		cntab-=ab.back();
    		ab.pop_back();
    	}
    	if(cntab>a[3]){
    		std::cout<<"NO"<<'\n';
    		continue;
    	}
    	t=std::min(a[1],a[2]);
    	std::sort(ba.begin(),ba.end());
    	while(!ba.empty()&&t){
    		t--;
    		cntba-=ba.back();
    		ba.pop_back();
    	}
    	if(cntba>a[4]){
    		std::cout<<"NO"<<'\n';
    		continue;
    	}
    	std::cout<<"YES"<<'\n';
    }
    return 0;
}

 os： This D It's still hard to think ,, You have to understand the idea of looking at guys for a long time

If there is any mistake, please advise , thank you ！