The 2023 ICPC Asia Jinan Regional Contest (The 2nd Universal Cup. Stage 17: Jinan)补题记录

The 2023 ICPC Asia Jinan Regional Contest (The 2nd Universal Cup. Stage 17: Jinan)

D. Largest Digit

题意：给定两个范围la, ra, lb, rb，求在两个范围内选任意两个数相加，求最大的数位

思路：暴力枚举即可，遇到9跳出循环

void solve(){
    ll la, ra, lb, rb;
    cin >> la >> ra >> lb >> rb;
    ll ans = 0;
    for(ll i = la; i <= ra; i ++){
        for(ll j = lb; j <= rb; j ++){
            ll res = 0;
            ll u = i + j;
            while(u){
                res = max(res, u % 10);
                u /= 10;
            }
            ans = max(ans, res);
            if(ans == 9) break;
        }
        if(ans == 9) break;
    }
    cout << ans << '\n';
}

I. Strange Sorting

题意：给定一个长度为 n 的排列，可以至多选择⌊n / 2⌋个（l, r），并且 a_l < a_{r ，}将（l, r）范围内的数字按照升序排序，求将整个排列完成升序排序的一个方案

思路：每次找当前第一个 a[i]!=i 的数字然后找最后的 a[j]<a[i] 的数字，对这个区间进行排序，在给定的范围内能完成排序

void solve(){
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i ++) cin >> a[i];
    vector<PII> ans;
    for(int i = 1; i <= n; i ++){
        if(a[i] != i){
            int p = i;
            for(int j = i + 1; j <= n; j ++){
                if(a[j] < a[i]) p = j;
            }
            sort(a.begin() + i, a.begin() + p + 1);
            ans.push_back({i, p});
        } 
    }
    cout << ans.size() << '\n';
    for(auto [x, y] : ans){
        cout << x << ' ' << y << '\n';
    }
}

A. Many Many Heads

题意：给定一个括号序列，包含[]()这四种，你可以对括号进行左右变化任意次，但是不能改变括号的种类，问是否存在且仅存在一种合法的括号序列

思路：赛时和队友想的做法是：先把当前的括号序列进行构造变成一个合法的括号序列，然后进行判断每对括号内是否存在两对相同类型的括号序列在同一深度

深度的定义：例如这样的括号序列 ([])([])，我们对他们进行编号：1，2，3，4，5，6，7，8，那么1，4，5，8的括号位于0深度，2，3，6，7括号的深度为1

如果存在同样深度的两对括号，例如（.......）（......）那么这两对括号一定能够组成另外一种合法的情况

那么为什么一定会出现这种情况呢？这和一开始我们构造的方法有关系：我们定义一个存储符号的数组 a，当a为空，我们把第一个放入的括号都变成向右的括号，然后检测之后加入的括号类型，如果是类型相同的括号就配对为一对，否则加入对应类型的向右的括号，所以同一层内只要合法是不会出现（（））这种的情况

然后接下来就是：对深度进行检测，如果当前同一深度的不存在相同的，就把这一层清空，因为后面有可能还会进入这个深度

void solve(){
    string s, s1;
    cin >> s;
    vector<char> a;
    for(int i = 0; i < s.size(); i ++){
        if(a.size() == 0){
            if(s[i] == '(' || s[i] == ')'){
                a.push_back('(');
                s1 += '(';
            } 
            else{
                a.push_back('[');
                s1 += '[';
            }
        }//空先放左括号 
        else{
            if(a.back() == '('){
                if(s[i] == '(' || s[i] == ')'){
                    s1 += ")";
                    a.pop_back(); 
                }
                else{
                    a.push_back('[');
                    s1 += '[';
                }
            }
            else if(a.back() == '['){
                if(s[i] == '[' || s[i] == ']'){
                    s1 += "]";
                    a.pop_back(); 
                }    
                else{
                    a.push_back('(');
                    s1 += '(';                    
                }            
            }
        }//对应匹配 
    }
    
    int p = 0, q = 0;//记录当前深度 
    map<int, int> x, y;
    //x是圆括号的深度，y是方括号的深度 
    for(auto c:s1)
    {
        if(c == '(') p ++; 
        else if(c == '[') q ++;//左边界出现，当前深度++ 
        else if(c == ')'){
            x[q] ++;
            if(x[q] >= 2){
                cout << "No\n";
                return;
            }//对应深度出现了两对 
            y[p] = 0;//这个深度合法就要清空 
            p --;//回到上一个深度 
        } 
        else if(c == ']'){
            y[p] ++;
            if(y[p] >= 2){
                cout << "No\n";
                return;
            }
            x[q] = 0;
            q --;
        } 
    }
    cout << "Yes\n";
}

补题：正解很简单，判断三个连续相同的和两个以上长度大于等于2的连续段会造成多种结果即可

void solve() {
    int n;
    string s;
    cin >> s;
    n = s.size();
    int cur = -1, cnt = 0, sum = 0;
    bool ok = true;
    for(int i = 0; i < n; i ++){
        int now = 0;
        if(s[i] == '[' || s[i] == ']') now = 1;
        if(now == cur){
            cnt ++;
            if(cnt >= 3) ok = false;
            if(cnt == 2) sum ++;
        }
        else{
            cur = now, cnt = 1;
        }
    }
//    cout << sum << '\n';
    if(!ok || sum >= 3) cout << "No\n";
    else cout << "Yes\n";
} 

pending......