[AtCoder] [經典競程 90 題] 002 - Encyclopedia of Parentheses(★3)

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_b
題目大意:
給你一個 $N$ ,請輸出所有長度為 $N$ 且合法括號序列。
這題其實跟 LeetCode 22 一模一樣,不過我真的做不太出來,上次面試被問還真的寫錯東西...
總之,這裡的做法是因為我們知道把「(」當作 $+1$、「)」當作 $-1$ 的話,一個括號序列合法,若且唯若前綴和恆非負且總和為 $0$。於是我們就可以暴力遞迴下去,每次都加加看右括號或左括號,並檢查當前的和是不是少於 $0$ 了,最後長度滿足後就把構造的序列加入 set 裡即可。
#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n; cin >> n;

	if (n & 1) return 0;

	set<string> ans;

	auto generate = [&ans](auto rec, int lef, int rig, string s) -> void {
		if (rig < lef or lef < 0 or rig < 0) return;
		if (lef == 0 and rig == 0) {
			ans.insert(s);
			return;
		}
		rec(rec, lef - 1, rig, s + "(");
		rec(rec, lef, rig - 1, s + ")");
	};
	generate(generate, n/2, n/2, "");

	for (auto s: ans) cout << s << '\n';
	return 0;
}

留言

這個網誌中的熱門文章

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

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

[Codeforces] 731D. 80-th Level Archeology