Educational Codeforces Round 149 (Rated for Div. 2)

Educational Codeforces Round 149 (Rated for Div. 2)

A - Grasshopper on a Line

思路：只有两种情况，x整除k时为x-1和1，否则为x

void solve() {
    int x, k;
    cin >> x >> k;
    if (x % k == 0) {
        cout << "2\n" << x - 1 << " " << x << "\n";
    } else {
        cout << "1\n" << x << "\n";
    }
}

B - Comparison String

思路：找出相同符号的最长序列，答案为最长数加一（连续m个相同符号表示有m+1个递增或递减的数，这m+1个数互不相同）

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7;

const double eps=1e-6;
typedef long long ll;
//#define int long long



void solve(){
    int n;
    string s;
    cin>>n>>s;
    char l=s[0];
    int ma=1;
    for(int i=1,c=1;i<s.size();++i){
        if(s[i]==l)c++,ma=max(ma,c);
        else c=1,l=s[i];
    }
    cout<<ma+1<<'\n';
}
int32_t main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

C - Best Binary String

思路：使reverse的次数尽可能少，那么逆序对的数目尽可能少，每个？满足与前一个字符形成递增即可

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7;

const double eps=1e-6;
typedef long long ll;
//#define int long long



void solve(){
    string s;
    cin>>s;
    for(int i=0;i<s.size();++i){
        if(s[i]=='?'){
            if(i==0)s[i]='0';
            else if(s[i-1]=='1')s[i]='1';
            else s[i]='0';
        }
    }
    cout<<s<<'\n';

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

D - Bracket Coloring

思路：任意给符号分类，实际上只有两种“（）”和“）（”，用栈的思想将符号分类。遇到‘（’，优先判断之前是否有未用过的‘）’，有则分到第二种，否则分到第一类，增加第一类‘（’的个数；同理遇到‘）’的情况；

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7;

const double eps=1e-6;
typedef long long ll;
//#define int long long



void solve(){
    string s;
    int n;
    cin>>n>>s;
    int a=0,b=0,x=0,y=0;
    bool aa=false,bb=false;
    for(int i=0;i<s.size();++i){
        if(s[i]=='('){x++;
            if(b)b--,s[i]='2',bb=true;
            else a++,s[i]='1',aa=true;
        }
        else{y++;
            if(a)a--,s[i]='1',aa=true;
            else b++,s[i]='2',bb=true;
        }
    }
    if(x==y){//cout<<s<<'\n';
        int c=(int)aa+(int)bb;
        cout<<c<<'\n';
        for(int i=0;i<s.size();++i){
            if(c==1)cout<<1<<' ';
            else cout<<s[i]<<' ';
        }cout<<'\n';
    }
    else cout<<"-1\n";

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