自动搬运

查看原文

来自洛谷，原作者为

	FL 穷则独善其身，达则兼济天下 || 高天之歌，与风同唱；听凭风引，且听风吟；千风涤荡，温门永存！

搬运于2025-08-24 22:03:38，当前版本为作者最后更新于2025-08-02 12:57:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

Question 1

可以先考虑 Special Jugde 是怎么写的。容易想到对于一个颜色序列，可以维护一个蓝栈和红栈，如果颜色是绿色，两个栈都弹出/压入一个，否则对应颜色栈弹出/压入一个。中途没有弹空栈，最后栈为空即合法。

如果我们得到了一个合法的 $01$ 序列，其中元素为 $1$ 代表该位置为绿色，否则为蓝色或红色。显然最优方案是在任意时刻，蓝栈和红栈的大小差不超过 $1$，通过上面的方式，容易构造方案。

我们考虑如何求这个 $01$ 序列。由于绿色括号会使总栈大小 $\pm2$，我们设绿色括号的权值是 $2$，非绿色括号的权值是 $1$，一开始我们可以假设所有的左括号都是绿色的，所有右括号是非绿色的。要让一些左括号变成非绿色，一些右括号变成绿色，使得对权值取前缀和不存在负数，且最后一位是 $0$，最优方案显然是从最后一位往前更改。容易构造序列。

Question 2

考虑不可三染色的情况，设左括号权值为 $2$，右括号权值为 $-1$，$s_i$ 为括号序列的前缀和，不可三染色当且仅当存在 $i$，使得 $n-i<s_n-s_i$。

计数。设计状态 $f_{i,j,k}$ 表示填完前 $i$ 位，满足 $s_i=j$，且 $s_i-i$ 的最小值为 $k$。转移显然。答案即为 $\textstyle \sum_{j=0}^{2n} f_{n,j,j}$。

注意本题卡常。需要优化常数。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5,M = 1e9+7;
int p,t,n,f[301][601][501];
string a;
signed main()
{
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> p >> t;
	if (p == 1)
	{
		int s[N];
		memset(s,0,sizeof s);
		while (t--)
		{
			cin >> a;
			n = a.size();
			a = ' '+a;
			for (int i = 1; i <= n; i++)
				if (a[i] == '(') s[i] = s[i-1]+2;
				else s[i] = s[i-1]-1;
			int k = s[n];
			if (k > n)
			{
				cout << "impossible\n";
				continue;
			}
			for (int i = 1; i <= k; i++)
				s[n-i+1] -= k-i+1;
			bool d = 0;
			for (int i = 1; i <= n; i++)
				if (s[i] < 0)
				{
					cout << "impossible\n";
					d = 1;
					break;
				}
			if (d) continue;
			int b = 0,r = 0;
			for (int i = 1; i <= n; i++)
			{
				if (s[i]-s[i-1] == 2)
				{
					b++,r++;
					cout << 'G';
				}
				else if (s[i]-s[i-1] == -2)
				{
					b--,r--;
					cout << 'G';
				}
				else if (s[i]-s[i-1] == 1)
				{
					if (b < r) b++,cout << 'B';
					else r++,cout << 'R';
				}
				else
				{
					if (b > r) b--,cout << 'B';
					else r--,cout << 'R';
				}
			}
			cout << '\n';
		}
	}
	else
	{
		f[0][0][300] = 1;
		for (short i = 1; i <= 300; i++)
			for (short j = 0; j <= i*2; j++)
			{
				for (short k = -i+1+300; k <= min(i+300,500); k++)
				{
					if (j >= 2)
						f[i][j][min((short)(j-i+300),k)] += f[i-1][j-2][k];
					(f[i][j][min((short)(j-i+300),k)] += f[i-1][j+1][k]) %= M;
				}
			}
		while (t--)
		{
			cin >> n;
			int ans = 0;
			for (int i = 0; i <= n*2; i++)
				(ans += f[n][i][i-n+300]) %= M;
			cout << ans << '\n';
		}
	}
	return 0;
}