Educational codeforces round 129 (rated for Div. 2) supplementary problem solution

---

I haven't practiced for a while , Two questions in ten minutes , But the third question is still lack of thinking ability , Keep practicing , come on.

A Parkway Walk

Simple thinking , Calculate the distance and , Then subtract the distance between the stools

#include<bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10;

#define int long long 

int T;
int a[N];
int n, m;

signed main()
{
    
	cin>>T;
	while(T -- ){
    
		int res = 0;
		cin>>n>>m;
		for(int i = 0; i < n; i ++ ){
    
			int t;
			cin>>t;
			res += t;
		}
		if(m >= res) cout<<0<<endl;
		else{
    
			cout<<res - m<<endl;
		}
	}
	return 0;
}

B Promo

Simple thinking , Arrange the order , Find a prefix and , Prefix and output the following part as required

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

#define int long long 

int T;
int a[N];
int n, m, q;
int res[N]; // Prefixes and arrays 
 
signed main()
{
    
	cin>>n>>q;
	for(int i = 1; i <= n; i ++ ){
    
		cin>>a[i];
	}
	
	sort(a + 1, a + n + 1);
	
	for(int i = 1; i <= n; i ++ ) res[i] = res[i - 1] + a[i];
// cout<<res[n]<<endl;
	while(q -- ){
    
		int x, y;
		cin>>x>>y; 
	// cout<<n - x + y<<' '<<n - x<<"***"<<endl;
		int op = res[n - x + y] - res[n - x];
		cout<<op<<endl;
	}
	return 0;
}

C awoo’s Favorite Problem

Thinking questions , It's not too late for the game , The official solution is quite clear ：

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

string s, t;
int T;
int n;
int res1, res2;
bool st;

int main()
{
    
	cin>>T;
	while(T -- ){
    
		res1 = 0;
		res2 = 0;
		s.clear();
		t.clear();
		cin>>n;
		cin>>s;
		cin>>t;
		int j = 0;
		st = false;
		//b The number of will not change , If two strings b The number of different , Then it must not be a string  
		for(int i = 0; i < n; i ++ ){
    
			if(s[i] == 'b') res1 ++ ;
			if(t[i] == 'b') res2 ++ ;
		}
		
		if(res1 != res2){
    
			cout<<"NO"<<endl;
			continue;
		}
		// Transformation s, Give Way s And t equal  
		//a Can only move right 
		//c It can only be moved to the left  
		for(int i = 0; i < n; i ++ ){
    			
			if(s[i] == 'b'){
    
				while(t[j] == 'b'){
    // find t The first of them is not b The letter of 
					j ++ ;
				}		
				continue;
			} 
			while(t[j] == 'b'){
    // find t The first of them is not b The letter of 
				j ++ ;
			} 
			//s[i] May be b, however t[j] It must not be for b, In three cases, two strings can never be equal 
			//①s[i] and t[j] Remove b The first one traversed after is not b Different characters , because a、c Unable to cross b swap , therefore s It must not be able to become t 
			//s[i] by a, But at this time s The pointer is in t To the right of , because a Can only move right , therefore s It must not be able to become t
			//s[i] by c, But at this time s The pointer is in t Left side , because c It can only be moved to the left , therefore s It must not be able to become t
			if(s[i] != t[j] || (s[i] == 'a' && i > j) || (s[i] == 'c' && i < j)){
    
				st = true;
				break;
			}
			j ++ ;
			if(i == n - 1 && t[j] == 'b') res2 ++ ;
		}
		if(st){
    
			cout<<"NO"<<endl;
			continue;
		}
		else cout<<"YES"<<endl;
	}
	return 0;
}