Codeforces Round ＃797 (Div. 3) A—E

First put a roast after the day's typing ：

today cf It's disgusting , First card b Card for dozens of minutes , Finish and then quickly c Then I got stuck d, I really can't think of it, so I went to write e, Over e Find out e Over 2000 people d Over 7000 people , Gray continue to write d, The result prefix and are over , Give me disgusting , Fortunately, so many people I've seen didn't think dp, Or send it directly .

A. Print a Pedestal (Codeforces logo?)

A brief explanation of the meaning of the topic

#include<bits/stdc++.h> 
using namespace std;
#define ll long long 
const int maxn=1e5+7;
int main() {
    
    int t;cin>>t;
    while(t--){
    
    	int n;
		cin>>n;
		int now=n%3;
		if(now==0){
    
			cout<<n/3<<" "<<n/3+1<<" "<<n/3-1<<endl;
		} 
		else if(now==1){
    
			cout<<n/3<<" "<<n/3+1+1<<" "<<n/3-1<<endl;
		}
		else {
    
			cout<<n/3+1<<" "<<n/3+1+1<<" "<<n/3-1<<endl;
		}
	}
	return 0;
}

B. Array Decrements

The question ：

Each operation can make all the numbers -1, If it changes to 0 Then it will not be reduced .

Answer key ：

Except for returnable 0 Directly calculate the difference of , All differences are required to be equal , return 0 The difference of is less than or equal to the difference that requires identity .

wa： card b Not because it's hard to think , I made the difference in the first position , Forget that the first position is return 0 Can not be used as a reference . We need to judge the real 【 Difference value 】.

#include<bits/stdc++.h> 
using namespace std;
#define ll long long 
const int maxn=2e5+7;
int a[maxn],b[maxn];
#define sc scanf
int main() {
    
    int t;cin>>t;
    while(t--){
    
    	int n;
		cin>>n;
		for(int i=1;i<=n;i++)sc("%d",&a[i]);
		for(int i=1;i<=n;i++)sc("%d",&b[i]);
		int c=INT_MAX;
		for(int i=1;i<=n;i++){
    
			if(b[i]!=0)
			{
    
				c=a[i]-b[i];continue;
			}
			 
		}
		
		if(c<0){
    
			cout<<"NO"<<endl;
			continue;
		}
		else if(c==INT_MAX){
    
			cout<<"YES"<<endl;
			continue;
		}
		int f=1;
		for(int i=1;i<=n;i++){
    
			if(b[i]==0){
    
				if(a[i]<=c)continue;
			}
			if(a[i]-b[i]!=c){
    
				f=0;break;
			}
		}
		if(f)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}

C. Restoring the Duration of Tasks

A brief explanation of the meaning of the topic

notes ： According to the conditions, we know that there is no existence. The previous one is not over, but the next one is over , And I wrote one more in consideration of this situation max, Deletion has no effect .

#include<bits/stdc++.h> 
using namespace std;
#define ll long long 
const int maxn=2e5+7;
int a[maxn],b[maxn];
#define sc scanf
#define pr printf
int main() {
    
    int t;cin>>t;
    while(t--){
    
    	int n;
		cin>>n;
		for(int i=1;i<=n;i++)sc("%d",&a[i]);
		for(int i=1;i<=n;i++)sc("%d",&b[i]);
		cout<<b[1]-a[1];
		for(int i=2;i<=n;i++){
    
			pr(" %d",max(0,b[i]-max(a[i],b[i-1])));
		}
		pr("\n");
	}
	return 0;
}

D. Black and White Stripe

The question ：
Select the minimum number of dyes to make it grow to k The subsequence of is all black .

Answer key ：

Personal thinking ：
At first glance, it seems that some algorithms should be used , however div3（）, There are many people . It belongs to pure thinking , And fear is dp. I can't think of a pure thinking solution , Not willing to use Algorithm , So kazhi .

In fact, just use the prefix and slightly optimize the direct violence , We directly calculate the length of all intervals as k The subsequence —> Calculate all the staining possibilities , Take the minimum .

#include<bits/stdc++.h> 
using namespace std;
#define ll long long 
const int maxn=2e5+7;
int a[maxn],b[maxn];
#define sc scanf
#define pr printf
int main() {
    
    int t;cin>>t;
    while(t--){
    
    	int n,m;cin>>n>>m;
    	string s;cin>>s;
    	if(s[0]=='W')a[0]=1;
    	else a[0]=0;
    	for(int i=0;i<n;i++){
    
    		if(s[i]=='W')a[i]=a[i-1]+1;
    		else a[i]=a[i-1];
		}
		int mmin=a[m-1];
		for(int i=m;i<n;i++){
    
			mmin=min(a[i]-a[i-m],mmin);
		}
		//cout<<"ans:";
		cout<<mmin<<endl;
	}
	return 0;
}

E. Price Maximization

The question ：

At first sight ： The title is long and rounded down , It must be a difficult math problem ！（ A fart ）

In fact, the feeling and D Almost difficult ：n Number , Add two and divide by k（ Rounding down ）, How to maximize the answer ？

Answer key ：

Put all the ‘k’ Take it out first . This will not be lost by rounding down 1, Add all and save ans.
Deal with the rest , In fact, it is the remainder ,sort Take the sequence . Double pointer traversal guarantees maximum , See code for this part , When the sum of two numbers is greater than k Then you can ans++.
final ans That's the answer. .

Not open ll wa A hair （）

#include<bits/stdc++.h> 
using namespace std;
#define ll long long 
const int maxn=2e5+7;
ll a[maxn],b[maxn];
#define sc scanf
#define pr printf
int main() {
    
    int t;cin>>t;
    while(t--){
    
    	ll n,m;cin>>n>>m;
    	ll cnt=0;
    	for(int i=1;i<=n;i++){
    
    		sc("%lld",&a[i]);
    		if(a[i]>=m){
    
    			cnt+=a[i]/m;
    			a[i]%=m;
			}
		}
		sort(a+1,a+n+1);
		ll l=1,r=n;
		while(l<r){
    
			if(a[l]+a[r]>=m){
    
				cnt++;
				l++;
				r--;
			}
			else l++;
		}
		//cout<<"ans:";
		cout<<cnt<<endl;
	}
	return 0;
}