526互联

Educational Codeforces Round 153 (Rated for Div. 2) A. Not a Substring

发布时间 2023-10-16 18:05:22作者: zsxuan

给一个长度为 \(n\) 的括号字符串 \(a\) 。你需要构造一个长度为 \(2n\) 的合法括号字符串 \(b\) ，且满足 \(a\) 不是 \(b\) 的子串。或者回答不可能。

显然若 \(a = ()\) ，则一定不可能构造出 \(b\) ，否则可以。

观察到合法括号穿串中， \(()()...()()\) 的限制属性更强，即子串一定满足相邻不等，于是

  • 若 \(a\) 的字符都是相邻不等的，不妨构造 \((((...)))\) 。
  • 否则构造 \(()()...()()\) 。
view 
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
	std::string s; std::cin >> s; int n = s.length();
	if (s == "()") std::cout << "NO\n";
	else {
		std::cout << "YES\n";
		int ok = 1;
		for (int i = 1; i < n; i++) ok &= (s[i] != s[i - 1]);
		if (ok) for (int i = 1; i <= 2 * n; i++) std::cout << (i <= n ? "(" : ")");
		else for (int i = 1; i <= n; i++) std::cout << "()";
		std::cout << "\n";
	}
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) {solve();}
	return 0;
}