专栏文章

题解：P13049 [GCJ 2020 Qualification] Nesting Depth

aabc1234shi
P13049题解参与者 4已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@mioz0fuj
此快照首次捕获于
2025/12/03 03:28
3 个月前
此快照最后确认于
2025/12/03 03:28
3 个月前
查看原文

题意

题意其实就是插入括号，使得所有括号内的字符串和括号外的字符串都是平衡字符串。
平衡字符串的定义：字符串中每个有出现的字母（题目中是数字）出现的次数都相同。当然，如果出现只一种字母（数字），则它本身就是平衡字符串。
比一般水题加强一点的是位置 pp 的嵌套深度是包含 pp 的匹配括号对的数量 mm。也就是说，这个数字是几，它就要被几个括号嵌套。
题目最重要的一点是，要使得答案字符串长度最短。

思路

好家伙，这不贪心配上字符串，淄博烧烤串吗？
题目让我们维护一个答案字符串：我们先定义一个变量 sdsd（深度的拼音缩写），再求出第 ii 个数字 dd。
如果 d>sdd>sd 也就是此数字大于当前深度，那就是要加深度了，将答案字符串加左括号，并将 sdsd 加一。
如果 d<sdd<sd 也就是此数字小于当前深度，那就是深度超了，将答案字符串加加右括号，并将 sdsd 减一。
然后直接将这个数字加入答案字符串，最后可能还有的左括号没有匹配右括号，所以要输出剩下的 sdsd 个右括号。
最后注意，输出时还要输出测试用例编号。我喜欢将数据总行数递减，所以先将数据总行数存档，后用存档的数据总行数减去现在的数据剩余行数（虽然比较麻烦）。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	cin>>t;
	int h=t;
	while(t--){
		string r="";
		string s;
		cin>>s;
		int l=s.length();
		int sd=0;
		for(int i=0;i<l;i++){
			int d=s[i]-'0'; 
		    while(d>sd){
            r+='(';
            sd++;
            }
            while(d<sd){
            r+=')';
            sd--;
            }
            r+=s[i];
		}
		while(sd>0){
        r+=')';
        sd--;
        }
        cout<<"Case #"<<h-t<<": "<<r<<endl; 
	}
	return 0;
}

细节

  • 每一轮循环后要进行清空。
  • 每一次输出答案要进行换行。
  • 遍历字符串时记得从 00 开始（因为字符串的存储是从 00 开始的）。

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...