题目理解

这是 BalkanOI 2018 Parentrises 问题的解决方案。题目要求处理两类任务：

• P=1：判断括号串是否RGB可读，并输出染色方案
• P=2：计算长度为N的RGB可读良括号串的数量

代码思路解析

1. P=1 部分：构造染色方案

核心思路：差分约束系统

for (int i = 1; i <= n; i++)
    if (a[i] == '(')
        s[i] = s[i - 1] + 2;
    else
        s[i] = s[i - 1] - 1;

将括号序列转化为数值序列：

• ( → +2
• ) → -1

关键调整

for (int i = 1; i <= k; i++)
    s[n - i + 1] -= k - i + 1;

对序列末尾进行调整，确保满足约束条件。

颜色分配策略

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';

2. P=2 部分：计数问题

三维DP状态设计

f[i][j][k]  // 处理了i个字符，当前平衡度为j，某种约束状态为k

状态转移

if (j >= 2)
    f[i][j][min(j-i+300, k)] += f[i-1][j-2][k];  // 添加开括号
f[i][j][min(j-i+300, k)] += f[i-1][j+1][k];      // 添加闭括号

关键技巧

1. 数值映射技巧

将括号序列映射为数值序列：

• ( → +2
• ) → -1

这种映射便于处理RGB约束。

2. 贪心颜色分配

• 同时影响红蓝的括号设为绿色
• 只影响一个颜色的括号根据平衡情况分配

3. 三维DP设计

• 第一维：处理长度
• 第二维：当前平衡度
• 第三维：约束状态（偏移300处理负数）

4. 模运算优化

(ans += f[n][i][i-n+300]) %= M;

使用模运算避免溢出。

复杂度分析

P=1 部分：

• 预处理：O(n)
• 颜色分配：O(n)
• 总复杂度：O(n)

P=2 部分：

• 状态数：O(n^3)（但实际有约束）
• 总复杂度：O(n^3) 预处理，O(n) 查询

正确性分析

P=1 的正确性：

算法确保了：

1. 忽略蓝色后红色序列平衡
2. 忽略红色后蓝色序列平衡
3. 绿色括号同时影响红蓝

P=2 的正确性：

通过DP枚举所有可能的RGB可读良括号串，确保计数准确。

总结

这个解法展现了问题转化和多维DP的高级技巧：

1. 问题转化：将颜色约束转化为数值约束
2. 贪心构造：在P=1中高效生成解
3. 计数优化：在P=2中通过DP准确计数
4. 边界处理：巧妙处理负数和边界情况

体现了竞赛中构造题和计数题的综合解题能力。