自动搬运

查看原文

来自洛谷，原作者为

	wang54321 **

搬运于2025-08-24 23:14:08，当前版本为作者最后更新于2025-04-20 19:55:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

update：应 jijidawang 要求在末尾换成了一份调试版代码

可能是内测人员题解。

这个题场上很多选手都写了假的 dp，获得了 $35$ 分，事实上当初验这个题的时候大家都写假 dp 爆炸了，然后前面 $5$ 分暴力的包其实能起到一个提示你假了的作用，然后这个题拥有一份正确的指数暴力是非常重要的，然而场上并没有很多人去写这个暴力，我们几个翻提交记录的时候一起变身急急大王。

首先子串的可删性是不好刻画的，首先看一下特征，就是 $\text{B}$ 全在结尾，$\text{C}$ 全在开头，那么如果只有 $\text{B}$ 和 $\text{C}$ 就只有 $\text{CCB}$ 一种消除方式，考虑一个括号序列，左括号匹配一个右括号，这里两个 $\text{CC}$ 匹配一个 $\text{B}$，就是 $\text{C}$ 是左括号，$\text{B}$ 是两个右括号。

那么我们发现 $\text{A}$，相当于是选择成为两个左括号或者一个右括号。

现在考虑简单情况，就是一个括号序列，可以填写 $\text{(},\text{?},\text{)}$，其中问号代表通配符，问合法的括号序列的个数。

发现如果一个序列合法的话必然将一个前缀的问号全换成左括号，后缀全部换成右括号不劣，并且这样合法的分界点只有一个，设 $dp_{i,j,0/1}$ 表示填到第 $i$ 个数，前面剩下 $j$ 个没匹配的左括号，当前的问号代表 左/右 括号，直接做就好了（事实上这题已经能做1e7了，灌注 jijidawang 谢谢喵，灌注 joke3579 谢谢喵）。

接下来考虑原问题，这个 $\text{A}$ 就是刚才的问号的地位，接下来所有特殊性质就显然了。

然后有一个深刻的问题就是 $\text{AACB}$ 转化成括号之后是 $\text{(()())}$，但是它消不掉，这里需要特殊注意一下，因为后面的 $\text{B}$ 不能拆成一半和前面的 $\text{AA}$ 匹配，一半和前面的 $\text{C}$ 匹配。

那么我们仿照上面的括号处理方式，先来考虑如何判定：

1. 每当遇到一个单独的右括号的时候肯定优先匹配双左括号，注意剩下的这一个括号是特殊的（只能用 $\text{A}$ 也就是单右括号删除,但是可以被 $\text{B}$ 抢夺）。

2. 每当遇到一个双右括号的时候优先匹配双左括号，否则的话匹配两个单左括号。

于是设 $dp_{i,j,k,s,0/1}$ 表示到第 $i$ 个数，前面有 $j$ 个单左括号，$k$ 个双左括号，特殊括号的状态，当前问号的状态。

直接 dp 就好了，代码非常难看。

提供一份调试用代码，输入 $n$，它会按照字典序输出所有长为 $n$ 的咏叹调，大概能跑 $n \le 15$。

它实现和正解的 dp 几乎没区别，就是把答案集合全部记录了，一些实现细节也可以看里面的。

#include<bits/stdc++.h>
using namespace std;
using llt=long long;
const llt N=20,mod=998244353;
llt n;vector<string> dp[N][N][N][3][2],Ans;
void add(vector<string> &S,vector<string> A,char s){if(s=='O')for(auto v:A)   S.push_back(v);else for(auto v:A)   S.push_back(v+s);}
int main()
{
    cin>>n;
    dp[0][0][0][0][0].push_back("");
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=i;j++)
            for(int k=0;k+j<=i;k++)
            {
                if(j>=1)
                    add(dp[i][j][k][0][0],dp[i-1][j-1][k][0][0],'A'),
                    add(dp[i][j][k][1][0],dp[i-1][j-1][k][1][0],'A'),
                    add(dp[i][j][k][2][0],dp[i-1][j-1][k][2][0],'A');
                add(dp[i][j][k][(k>0)+1][1],dp[i-1][j+1][k][0][1],'A');
                add(dp[i][j][k][(k>0)+1][1],dp[i-1][j+1][k][0][0],'A');
                add(dp[i][j][k][0][1],dp[i-1][j][k][1][1],'A');  
                add(dp[i][j][k][0][1],dp[i-1][j][k][2][1],'A');  
                add(dp[i][j][k][0][0],dp[i-1][j+1][k][0][0],'B'),
                add(dp[i][j][k][0][1],dp[i-1][j+1][k][0][1],'B'),
                add(dp[i][j][k][1][0],dp[i-1][j+1][k][1][0],'B'),
                add(dp[i][j][k][1][1],dp[i-1][j+1][k][1][1],'B'),
                add(dp[i][j][k][2][0],dp[i-1][j+1][k][2][0],'B'),
                add(dp[i][j][k][2][1],dp[i-1][j+1][k][2][1],'B');
                if(k>=1)
                    add(dp[i][j][k][0][0],dp[i-1][j][k-1][0][0],'C'),
                    add(dp[i][j][k][0][1],dp[i-1][j][k-1][0][1],'C'),
                    add(dp[i][j][k][1][0],dp[i-1][j][k-1][1][0],'C'),
                    add(dp[i][j][k][1][1],dp[i-1][j][k-1][1][1],'C'),
                    add(dp[i][j][k][2][0],dp[i-1][j][k-1][2][0],'C'),
                    add(dp[i][j][k][2][1],dp[i-1][j][k-1][2][1],'C');
            }
        for(int k=0;k<=i;k++) 
            add(dp[i][0][k][0][0],dp[i-1][0][k+2][0][0],'B'),
            add(dp[i][0][k][0][1],dp[i-1][0][k+2][0][1],'B'),
            add(dp[i][0][k][1][0],dp[i-1][0][k+2][1][0],'B'),
            add(dp[i][0][k][1][1],dp[i-1][0][k+2][1][1],'B'),
            add(dp[i][0][k][0][1],dp[i-1][0][k+1][0][0],'A'),
            add(dp[i][0][k][0][1],dp[i-1][0][k+1][0][1],'A'),
            add(dp[i][0][k][0][1],dp[i-1][0][k+1][2][1],'B');
        for(int j=0;j<=i;j++)   add(dp[i][j][0][1][1],dp[i][j][0][2][1],'O');
    }
    add(Ans,dp[n][0][0][0][0],'O');add(Ans,dp[n][0][0][0][1],'O');sort(Ans.begin(),Ans.end());
    for(auto v:Ans) cout<<v<<endl;
    return 0;
}