526互联

Educational Codeforces Round 105 (Rated for Div. 2) A. ABC String

发布时间 2023-10-11 21:29:20作者: zsxuan

给一个长为 \(n\) 的字符串 \(a\) ，\(n\) 是偶数，字符串中只包含三种字符 \(A, B, C\) 。规定一个合法的字符串为一个符合入栈规则的字符串。

需要构造一个长为 \(n\) 的括号字符串 \(b\) 。

  • \(b\) 是一个合法的括号序列
  • \(\forall 1 \leq i < j \leq n\) ，\(b_i = b_j\) 当且仅当 \(a_i = a_j\) 。

考虑对 \(2^3\) 的压位枚举，二进制的第 \(i\) 位对应 \(s_j\) - ‘A’ 。权值 \(0/1\) 对应 '(' 和 ')' 。于是可枚举构造出一个 \(b\) 。于是可以判断是否存在合法的 \(b\) 。

view 
#include <bits/stdc++.h>

typedef long long ll;
bool is_regular(std::string s) {
	std::stack<char> stk;
	for (int i = 0; i < s.length(); i++) {
		if (s[i] == '(') stk.push(s[i]);
		else {
			if (stk.empty() || stk.top() == ')') return false;
			else stk.pop();
		}
	}
	return stk.empty();
}
void solve() {
	std::string s; std::cin >> s; int n = s.length(); s = " " + s;
	for (int bit = 0; bit < (1 << 3); bit++) {
		std::string s_cur = "";
		for (int i = 1; i <= n; i++) {
			s_cur += ((bit >> (s[i] - 'A')) & 1 == 1) ? '(' : ')';
		}
		if (is_regular(s_cur)) {
			std::cout << "YES" << '\n';
			return;
		}
	}
	std::cout << "NO" << '\n';
}

int main() {
	int _ = 1; std::cin >> _;
	while(_--) { solve(); }
	return 0;
}