codeforces round ＃797 ABCDEFG

A

#include <bits/stdc++.h>
using namespace std;
void solve(){
    
    int n;
    cin>>n;
    if(n%3==0){
    
        cout<<n/3-1+1<<" "<<n/3-1+2<<" "<<n/3-1<<endl;
    }
    else if(n%3==1){
    
        cout<<n/3-1+1<<" "<<n/3-1+3<<" "<<n/3-1<<endl;
    }
    else 
        cout<<n/3-1+2<<" "<<n/3-1+3<<" "<<n/3-1<<endl;
}
int main(){
    
    int t;
    cin>>t;
    while(t--){
    
        solve();
    }
    system("pause");
}

B

Difference between two arrays , Then compare whether the numbers on all non-zero bits are the same .

#include <bits/stdc++.h>
using namespace std;
int solve(){
    
    int n;
    cin>>n;
    vector<int>a(n),b(n);
    for( int i=0;i<n;i++){
    
        cin>>a[i];
    }
    for( int i=0;i<n;i++){
    
        cin>>b[i];
    }
    for( int i=0;i<n;i++){
    
        a[i]-=b[i];
        if(a[i]<0) return false;
    }
    int dec=*max_element(a.begin(),a.end());
    for( int i=0;i<n;i++){
    
        if(b[i]==0) continue;
        if(a[i]!=dec) return false;
    }
    return true;
}
int main(){
    
    int t;
    cin>>t;
    while(t--){
    
        if(solve())
            cout<<"YES"<<"\n";
        else 
            cout<<"NO"<<"\n";
    }
    system("pause");
}

C

It can be simulated directly

#include <bits/stdc++.h>
using namespace std;
void solve(){
    
    int n;
    cin>>n;
    vector<int>s(n),f(n);
    for( int i=0;i<n;i++) cin>>s[i];
    for( int i=0;i<n;i++) cin>>f[i];
    int cur=0;
    for( int i=0;i<n;i++){
    
        if(s[i]>=cur) cur=s[i];
        cout<<f[i]-cur<<" ";
        cur=f[i];
    }
    cout<<"\n";
}
int main(){
    
    int t;
    cin>>t;
    while(t--){
    
        solve();
    }
    system("pause");
}

D

Use similar double pointers , Maintain an interval W The number of

#include <bits/stdc++.h>
using namespace std;
int solve(){
    
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    int tot=0;
    for( int i=0;i<k;i++){
    
        if(s[i]=='W') tot++;
    }
    int ans=tot;
    for( int i=k;i<n;i++){
    
        if(s[i]=='W') tot++;
        if(s[i-k]=='W') tot--;
        ans=min(ans,tot);
    }
    return ans;

}
int main(){
    
    int t;
    cin>>t;
    while(t--){
    
        cout<<solve()<<"\n";
    }
    system("pause");
}

E

The idea of this question is , How to minimize the loss after division .
First , To simplify the problem , Can be All number pairs k modulus .
Traverse all processed numbers from large to small
For a certain number x, obviously ,x And k-x The pairing loss is the smallest . without k-x, Then choose ratio k-x The smallest number of the big .

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll solve(){
    
    int n,k;
    cin>>n>>k;
    vector<int>v(n);
    for( int i=0;i<n;i++) cin>>v[i];
    ll ans=0;
    for( int i=0;i<n;i++){
    
        ans+=v[i]/k;
        v[i]%=k;
    }
    multiset<int>se;
    for( int i=0;i<n;i++) se.insert(v[i]);
    while(!se.empty()){
    
        int x=*--se.end();
        se.erase(--se.end());
        auto it=se.lower_bound(k-x);
        if(it!=se.end()){
    
            se.erase(it);
            ans++;
        }
        else{
    
            break;
        }
    }
    return ans;
    
}
int main(){
    
    int t;
    cin>>t;
    while(t--){
    
        cout<<solve()<<"\n";
    }
    system("pause");
}

F

Permutation problems can be abstracted into rings to consider .
If in position i The number on is x, that , We can think of something i Sum point x A side is connected between .
Through the above treatment , Finally, we can get a graph composed of several rings .

obviously , If the length of a ring is y, Then the time for these numbers to return to the initial state through rotation is y Multiple .

There are several rings in a graph , We only need to calculate the least common multiple of the length of these rings .

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll lcm( ll x,ll y){
    
    return x*y/__gcd(x,y);
}
ll solve(){
    
    int n;
    cin>>n;
    string s;
    cin>>s;
    vector<int>v(n);
    for( int i=0;i<n;i++){
    
        cin>>v[i];
        v[i]--;
    }
    ll ans=1;
    vector<int>vis(n);
    for( int i=0;i<n;i++){
    
        if(vis[i]) continue;
        int cur=i;
        string ss,ns;
        while(vis[cur]==0){
    
            ss.push_back(s[cur]);
            vis[cur]=1;
            cur=v[cur];
        }
        ns=ss;
        int cnt=0;
        while(1){
    
            rotate(ns.begin(),ns.begin()+1,ns.end());
            cnt++;
            if(ns==ss) break;
        }
        ans=lcm(cnt,ans);
    }
    return ans;
}
int main(){
    
    int t;
    cin>>t;
    while(t--){
    
        cout<<solve()<<"\n";
    }
    system("pause");
}

G

This question requires a knowledge point , Is the use of map To maintain interval problems .
Use map The maintenance method is , Key value key Store left endpoint , The number val Store the values of the right endpoint and interval .

map Maintain the data structure of the interval , Support interval merging and interval splitting , The time complexity of a merge and a split is logn

For this question , A deceleration operation will produce a new train（ Section ）, Or several train（ Section ） Merge .

At the beginning, at most n Intervals ,n At most n Intervals , The time complexity of merging is at most nlogn, The time complexity of splitting is at most nlogn

#include<bits/stdc++.h>
// #pragma GCC optimize(2)
using namespace std;
typedef long long ll;
void solve(){
    
	int n,m;
	cin>>n>>m;
	vector<int>v(n+1);
	for( int i=1;i<=n;i++){
    
		cin>>v[i];
	}
	map<int,pair<int,int>>mp;
	mp[1]={
    1,v[1]};
	for( int i=2;i<=n;i++){
    
		auto it=*--mp.end();
		int x=it.first,y=it.second.first,speed=it.second.second;
		if(v[i]>=speed) {
    
			mp[x]={
    y+1,speed};
		}
		else {
    
			mp[i]={
    i,v[i]};
		}
	}
	vector<int>ans;
	while(m--){
    
		int k,d;
		cin>>k>>d;
		auto it=prev(mp.upper_bound(k));
		v[k]-=d;
		if(v[k]>=it->second.second) {
    
			ans.push_back(mp.size());
			continue;
		}
		else
		{
    
			if(k==it->first){
    
				it->second.second=v[k];
			}
			else{
    
				mp[k]={
    it->second.first,v[k]};
				it->second.first=k-1;
		
			}
			auto cur=mp.find(k);
			while(next(cur)!=mp.end()&&next(cur)->second.second>=v[k]){
    
				cur->second.first=next(cur)->second.first;
				mp.erase(next(cur));
			}					
		}
		ans.push_back(mp.size());
	}
	for( auto it:ans){
    
		cout<<it<<" ";
	}
	cout<<"\n";
}
int main(){
    
	int t;
	cin>>t;
	while(t--){
    
		solve();
	}
	system("pause");
}