题解：P13049 [GCJ 2020 Qualification] Nesting Depth

Canbo · 2025-07-04 20:02:52 · 题解

题目传送门

题意

给定一个数字字符串 \mathbf{S}，在其中插入最少数量的左右括号，使得生成的字符串是平衡的，并且每个数字 d 恰好位于 d 对匹配的括号内。

思路

我们可以把 \mathbf{S} 的每个字符转化为对应的数字 n，如果当前深度小于 n，插入(，增加深度直到等于 n，否则插入)，减少深度直到等于 n，在所有数字处理完毕后，插入)闭合所有剩余的括号。

AC CODE

#include <bits/stdc++.h>
using namespace std;
int t;
int main() {
    cin>>t;
    for (int i=1;i<=t;i++) {
        string s;
        cin>>s;
        string new_s;
        int shen=0;
        for (int j=0;j<s.size();j++) {
            int n=s[j]-'0';
            while(shen<n) {
                new_s+='(';
                shen++;
            }
            while(shen>n) {
               new_s+=')';
               shen--;
            }
            new_s+=s[j];
        }
        while(shen>0) {
            new_s+=')';
            shen--;
        }
        cout<<"Case #"<<i<<": "<<new_s<<endl;
    }
    return 0;
}