题解：P4788 [BalkanOI 2018] Parentrises

__FL__ · 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;
}