2022.07.11 summer training personal qualifying (VI)

2022.07.11 Summer training Individual qualifying （ 6、 ... and ）

Post game introspection

It looks better than before , But it's still normal . Dynamic planning is still unskilled . Continue refueling .
I didn't sleep last night , It's over cf It's so exciting , Then I watched the mobile phone for a while, and after reading the question, I became more excited and couldn't sleep . Don't make up the question today .

Problem E

Source

Codeforces-1084C

Answer key

First think of the string as just letters a And letters b Sequence , With b Separator ,b hold a Divided into several parts , The number of each copy is different . A group b Ahead a Mandatory , Then you can choose b hinder a Any one to form the answer , In fact, it is also a combinatorial counting problem ,

Code

// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long

using namespace std;

const int mod=1e9+7;
int n, T = 1, m;
string st;
int len,all=1,ans;
vector<int> cnta;

int qsm(int x,int y){
    
    int res=1;
    while(y){
    
        if(y&1) res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res%mod;
}

void ready()
{
    
    int cnt=0;
    cin>>st;
    len=st.size();
    for(auto item:st){
    
        if(item=='a'){
    
            cnt++;
        }
        if(item=='b'){
    
            if(cnt){
    
                cnta.push_back(cnt);
                cnt=0;
            }
        }
    }
    if(cnt) cnta.push_back(cnt);
    for(auto item:cnta) all=all*(item+1)%mod;
    for(auto item:cnta){
    
        all=all*qsm(item+1,mod-2)%mod;
        ans=(ans+item*all%mod)%mod;
        //cout<<item<<' '<<all<<' '<<ans<<'\n';
    }
    cout<<ans;
}


void work()
{
    

}

signed main()
{
    
	IOS;
    ready();
	//cin>>T;
	while (T--) {
    
		work();
	}
	return 0;
}

Problem F

Source

Codeforces-1163B2

Answer key

Inductive questions

Only ___-__ When there are other all the same , The number of times to add a new one is 1 Meet the requirements when .

In addition, pay attention to some special situations , For example, all are the same color or different colors .

Code

// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long

using namespace std;

const int N=1e5+5;
int n, T = 1, m;
int col[N],cnt[N],maxn,minn;

void out(){
    
    cout<<"col\n";
    for(int i=1;i<=n;i++) cout<<col[i]<<' ';
    cout<<"\ncnt\n";
    for(int i=1;i<=n;i++) cout<<cnt[i]<<' ';
    cout<<"\n\n";
}

void ready()
{
    
    int ans=1,num=0;
    cin>>n;
    maxn=minn=1;
    ffor(i,1,n){
    
        int x;
        cin>>x;
        if(!col[x]) num++;
        else cnt[col[x]]--;
        if(cnt[col[x]]==0 && minn==col[x]) minn++;
        col[x]++; cnt[col[x]]++;
        maxn=max(maxn,col[x]);
        minn=min(minn,col[x]);
        if(cnt[maxn]==1 && minn==maxn-1)
            ans=i;
        if(minn==1 && cnt[minn]==1 && num==cnt[maxn]+1)
            ans=i;
        if(maxn==minn && (maxn == 1 || num == 1))
            ans=i;
       // cout<<"i="<<i<<" num="<<num<<'\n';
       // cout<<"maxn="<<maxn<<' '<<" minn="<<minn<<'\n';
       // out();

    }
    cout<<ans;
}


void work()
{
    

}

signed main()
{
    
	IOS;
    ready();
	//cin>>T;
	while (T--) {
    
		work();
	}
	return 0;
}

Problem I

Source

Codeforces-1129A2

Answer key

greedy .

Each point can only take one sugar , How many points you send, how many circles you have to walk . Then the last time you send the circle must be at least . In this way, we can calculate , From this point , Then what is the shortest distance to send all the sweets .

Then enumerate from different points , Assuming that i. If you want to send j Of candy , So the path is i To j The path of +j The path to send all the sweets . about i, Enumerate all j Then take the largest , This can guarantee others j All have been delivered .

Code

// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long

using namespace std;

const int N=5005;
int n, T = 1, m;
int dp[5005][5005];
vector<int> ve[N];
int maxn[N];

void ready()
{
    
    cin>>n>>m;
    ffor(i,1,n){
    
        int cnt=0;
        int j=i+1;
        if(j>n) j=1;
        while(j!=i){
    
            cnt++;
            dp[i][j]=cnt;
            j++;
            if(j>n) j=1;
        }
    }
    /*ffor(i,1,n){ ffor(j,1,n) cout<<dp[i][j]<<' '; cout<<'\n'; }*/
    ffor(i,1,m){
    
        int a,b;
        cin>>a>>b;
        ve[a].push_back(b);
    }
}


void work()
{
    
    ffor(i,1,n){
    
        int minn=INF,cnt=0;
        for(auto v:ve[i]){
    
            minn=min(minn,dp[i][v]);
            cnt++;
        }
        if(minn==INF) minn=0,cnt=1;
        maxn[i]=(cnt-1)*n+minn;
    }
    ffor(i,1,n){
    
        int ans=0;
        ffor(j,1,n){
    
            //if(i==j) continue;
            if(maxn[j])
              ans=max(ans,dp[i][j]+maxn[j]);
        }
        cout<<ans<<' ';
    }
}

signed main()
{
    
	IOS;
    ready();
	//cin>>T;
	while (T--) {
    
		work();
	}
	return 0;
}