[TIOJ] 1106. 遇見一株樹

題目連結:http://tioj.infor.org/problems/1106
葉子個數就只要算*的個數就好了,深度則只要看有幾個括號(若是遇到右括號就要把他移掉),而幾元樹則是在每一層都把()合成一個之後再加上*的個數。
#include <bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	string ss;
	while(cin>>ss){
		int l=0, d=0, y=0;
		int cnt=0;
		stack<int> sk;
		sk.push(0);
		for(auto c:ss){
			if(c=='('){
				sk.top()++;
				sk.push(0);
				cnt++;
			}else if(c==')'){
				y=max(y, sk.top());
				sk.pop();
				cnt--;
			}
			d=max(d, cnt);
			if(c=='*'){
				l++;
				sk.top()++;
			}
		}
		cout<<l<<" "<<d+1<<" "<<y<<'\n';
	}
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology