题解：P4788 [BalkanOI 2018] Parentrises

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

CPP

#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;
}

题解：P4788 [BalkanOI 2018] Parentrises

文章操作

Solution

Question 1

Question 2

Code

相关推荐

评论

题解：P4788 [BalkanOI 2018] Parentrises