Educational Codeforces Round 153 (Rated for Div. 2)

Educational Codeforces Round 153 (Rated for Div. 2)

A - Not a Substring

思路：找到串中最大的层数，若层数为1，构造层数大于1的即可；若层数大于1，构造层数为1的即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=200+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;


void solve(){
    string s;cin>>s;
    if(s.size()==2&&s=="()")cout<<"No\n";
    else{
        cout<<"YES\n";
        int c=0;
        for(int j,i=0;i<s.size();++i){
            j=i;
            while(j+1<s.size()&&s[j+1]==s[i])j++;
            c=max(c,j-i+1);
            i=j;
        }
        if(c==1){
            for(int i=0;i<s.size();++i)cout<<"(";
            for(int i=0;i<s.size();++i)cout<<")";cout<<'\n';
        }else{
            for(int i=0;i<s.size();++i)cout<<"()";cout<<'\n';
        }
    }
    return;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

B - Fancy Coins

思路：要让硬币数尽可能少，那么用尽可能多的k价值的硬币；

先将m变成k的倍数，即用价值为1的普通硬币；若普通硬币不够，则用价值为1的花色硬币；

m为k的倍数后，先用普通硬币，再用价值为k的花色硬币

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=200+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;


void solve(){
    int m,k,a1,ak;
    cin>>m>>k>>a1>>ak;
    int c=m/k,z=c*k;
    int c1=min(a1,m-z),ck;
    a1-=c1,m-=c1;
    ck=min(ak,m/k);
    int ans;
    if(m%k==0)c1=min(a1/k,m/k-ck),ans=m/k-ck-c1;
    else ans=m%k+m/k-ck;
    cout<<ans<<'\n';

    return;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

C - Game on Permutation

思路：要让Alice赢，即Alice下的位置前只有一个小于Alice的位置。那么可以维护前i-1个里的最小值和第二小值，当第i个数大于前i-1个数中的最小值且小于第二小值则说明Alice可以赢

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=200+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;


void solve(){
    int n;cin>>n;
    vector<int>ve(n+1);
    for(int i=1;i<=n;++i)cin>>ve[i];
    int ans=0,mi=INF,p=INF;
    for(int i=1;i<=n;++i){
        if(ve[i]>mi&&p>ve[i]){
            ans++;
            p=min(ve[i],p);
        }
        mi=min(mi,ve[i]);
    }
    cout<<ans<<'\n';
    return;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}