A. Array Coloring

题目链接

题目描述

一个数组排好序后，相邻两个数的原来的下标奇偶性是否相同

分析

用pair<int，int>模拟即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve(){
    int n;
    cin>>n;
    vector<pair<int,int> >vt(n+1);
    for(int i=1;i<=n;i++){
        cin>>vt[i].first;
        vt[i].second=i;
    }
    sort(vt.begin()+1,vt.end());
    for(int i=1;i<=n-1;i++){
        if(vt[i].second%2==vt[i+1].second%2){
            cout<<"NO"<<endl;
            return;
        }
    }
    cout<<"YES"<<endl;
}

B. MEX Reordering

题目链接

题目描述

有一个长度为n的数组a，问能否对a进行重排，对于所有的$i(i=1,2 \dots,n-1)$都满足$MEX({a_{1},a_{2}, \dots , a_{i}})!=MEX({a_{i+1},a_{i+2}, \dots ,a_{n}})$

分析

可以发现对a进行升序排序后，会出现前后mex相等的情况会变少，然后我们只要判断前后缀mex是否会相等就可以了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void solve(){
    int n;
    cin>>n;
    vector<int>vt(n+1),num1(n+1),num2(n+1);
    for(int i=1;i<=n;i++){
        cin>>vt[i];
        num2[vt[i]]++;
    }
    int mex1=0,mex2=0;
    while(num2[mex2]){
        mex2++;
    }
    sort(vt.begin()+1,vt.end());
    for(int i=1;i<=n-1;i++){
        num2[vt[i]]--;
        num1[vt[i]]++;
        while(num1[mex1]){
            mex1++;
        }
        if(num2[vt[i]]==0){
            mex2=min(mex2,vt[i]);
        }
        if(mex1==mex2){
            cout<<"NO"<<endl;
            return;
        }
    }
    cout<<"YES"<<endl;
}

C. Sorting Game

题目链接

题目描述

一个长度为n的二进制字符串s，爱丽丝和鲍勃轮流操作，每次操作都能选s的子序列进行升序排序(子序列要不降)，如果轮到谁无法操作则输，如果爱丽丝能赢就输出爱丽丝选的子序列

分析

观察到，如果s一开始就是不降，那就是鲍勃赢，否则爱丽丝一定能用一次操作将字符串变为不降。所以只要先将s排好序，然后和原来的字符串比较，不同的就是需要选择的

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    string t=s;
    sort(t.begin(),t.end());
    vector<int> vt;
    for(int i=0;i<n;i++){
        if(s[i]!=t[i]){
            vt.push_back(i+1);
        }
    }
    
    if (vt.size()==0){
        cout << "Bob" << endl;
    }
    else {
        cout << "Alice" << endl;
        cout << vt.size()<<endl;
        for (int it : vt){
            cout << it <<" ";
        }
        cout << endl;
    }
}

D1. Sub-RBS (Easy Version)

题目链接

题目描述

给个正则表达式s，问是否存在一个s的子序列t满足:

  • t是正则表达式
  • t的字典序要比s大

如果有则输出t的最大长度，否则输出-1

分析

我们考虑s中的每个)看是否能替换为(，如果遍历到)我们就选择离它最近的(，再判断后面的)够不够，如果够，那么他的长度就是总长度减去)和(之间相差的字符个数的两倍，最后把结果取max即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    s=" "+s;
    vector<int> sum(n+2, 0);
    for (int i = n; i >= 1; i--){
        sum[i] = sum[i + 1] + (s[i] == ')');
    }
    vector<int> vt;
    for (int i = 0; i < n; i++) {
        if(s[i] == '('){
            vt.push_back(i);
        }
    }

    int p = 0;
    int ans = -1;
    for (int i = 1; i <= n; i++) {
        if (s[i] == ')') {
            auto it = upper_bound(vt.begin(), vt.end(), i);
            if (it != vt.end()) {
                int pp = *it;
                if (sum[pp + 1] >= p + 1) {
                    ans = max(ans, n - 2 * (pp - i));
                }
            }
            p--;
        } 
        else {
            p++; 
        }
    }
    cout << ans << endl;
}