主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
题解:P12264 『STA - R9』咏叹调调律
最后更新于 2025-07-31 12:56:02
作者
Nephren_Sakura
分类
题解
题解
P12264
复制 Markdown
查看原文
删除文章
更新内容
很有意思的计数题!观察!注意!启示! 观察给出的四个字符串,注意到这四个串的 B 都在结尾,C 都在开头,这启示我们把 C 当成左括号,B当成右括号进行括号匹配,因为给出的字符串是 CCB,所以 B 要当成两个右括号。 接下来观察 A,注意到 A 出现在 CA、AB 中,这启示我们把 A 当成一个可以成为单右括号或双左括号的通配符。代入发现这同样能凑出 AAA。 继续观察,注意如果你将前面的 A 当作右括号,后面的 A 当作左括号,你直接交换过来是不劣的,因为你匹配的是子序列,这启示我们存在一个分界线,使得前面的 A 被当成双左括号,右边被当成单右括号。这代表我们可以直接把当前 A 是左括号还是右括号扔进状态里。 试着写个 DP,发现算重了,这是因为一个字符串会有多种匹配方式,这启示我们钦定一个优先级,使得某个优先级优先匹配。 注意到你两个左括号或右括号不能各自匹配一半,比如 AACB,直接转括号序列是 ```(()())```,但事实上是不合法的,因为 A 的第一个左括号和 B 的最后一个右括号匹配了。这启示我们优先匹配变成两个括号的字母,也就是左 A 和 B。 此时还有一个问题,就是你加入右 A 时,和左 A 匹配,剩下的那个括号只能与另一个右 A 匹配。这个时候你再加入一个 B,如果你加入的右 A 左边有 C,按照优先匹配双括号的优先级,你应该是要用这个 B 去匹配左 A,然后 C 匹配右 A 的。于是再加入一维状态,表示现在是否存在只能匹配右 A 的特殊括号。如果存在,这个括号是否能和 B 交换。 所以最终的状态就是 $dp_{i,j,k,0/1,0/1/2}$ 表示使用了 $i$ 个字母,剩下 $j$ 个左 A,$k$ 个 C,当前 A 是否已经只能取右括号,只能与右 A 匹配的括号的状态。转移枚举每种字符进行转移即可。时间复杂度 $O(n^3)$,空间复杂度滚动数组优化后 $O(n^2)$。 我代码里最后一维是 $1/2/3$,相当于把 $0/1/2$ 都加了 $1$,事实上没有必要,但懒得改了。 代码,注释应该算比较清晰的: ```cpp #include<bits/stdc++.h> using namespace std; #define int long long const int mod=998244353; int n,p,q,r,dp[2][505][505][2][4]; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>p>>q>>r; dp[0][0][0][0][1]=1; for(int i=0; i<n; i++){ for(int j=0; j<=i; j++){ for(int k=0; j+k<=i; k++){ for(int l=0; l<2; l++){ for(int s=1; s<=3; s++){ if(!dp[i&1][j][k][l][s]) continue; if(!l) (dp[i+1&1][j+1][k][0][s]+=dp[i&1][j][k][l][s]*p)%=mod;//加入左 A if(s==3) (dp[i+1&1][j][k][1][1]+=dp[i&1][j][k][l][s]*p)%=mod;//加入右 A,发现存在只能匹配右 A 的右括号,且右括号前面没 C else if(s==2) (dp[i+1&1][j][k+1][1][1]+=dp[i&1][j][k][l][s]*p)%=mod;//加入右 A,发现存在只能匹配右 A 且前面有 C 的右括号,把被预留的 C 加回来。 else if(j&&k) (dp[i+1&1][j-1][k-1][1][2]+=dp[i&1][j][k][l][s]*p)%=mod;//加入右 A,发现不存在只能匹配右 A 的左括号,且前面既有左 A 又有 C,匹配左 A 并预留一个 C else if(j) (dp[i+1&1][j-1][k][1][3]+=dp[i&1][j][k][l][s]*p)%=mod;//同上,发现只存在左 A,特殊括号增加只能匹配右 A 且前面没 C 的右括号 else if(k) (dp[i+1&1][j][k-1][1][1]+=dp[i&1][j][k][l][s]*p)%=mod;//同上,发现只存在 C,直接匹配 if(j) (dp[i+1&1][j-1][k][l][s]+=dp[i&1][j][k][l][s]*q)%=mod;//加入 B,优先和左 A 匹配 else if(s==2) (dp[i+1&1][j][k][1][1]+=dp[i&1][j][k][l][s]*q)%=mod;//如果没有,考虑和特殊括号置换 else if(k>=2) (dp[i+1&1][j][k-2][l][s]+=dp[i&1][j][k][l][s]*q)%=mod;//如果还没有,考虑和两个 C 匹配 (dp[i+1&1][j][k+1][l][s]+=dp[i&1][j][k][l][s]*r)%=mod;//加入 C dp[i&1][j][k][l][s]=0; } } } } cout<<(dp[i+1&1][0][0][0][1]+dp[i+1&1][0][0][1][1])%mod<<' '; } return 0; } ```
正在渲染内容...
点赞
1
收藏
0