题解：P12472 [集训队互测 2024] 基础 ABC 练习题

· · 题解

题解：P12472 [集训队互测 2024] 基础 ABC 练习题

题外话

这是我们学长放在我们 noip 模拟赛里的题目，然后没有一个人会做。

题目分析

本题解借鉴了 Xun_Xiaoyao 学长的思路。

看完题目之后，我们的第一反应是如何判断一个序列是否合法都十分困难。\ 此时，只能从题目出发来寻找性质来做。很显然，贪心的判断是假的，从数据范围来看，大概率是一个多维 dp。\ 观察题目告诉我们的合法子序列，ABC、 BCA 和 CAB 似乎是轮换的，那么我们便可以对原序列进行一个变换，使得第一个字母换到末尾去，若变换前的序列合法，显然在变换后依旧合法。

我们钦定有 x 个 ABC，y 个 BCA 和 z 个 CAB。那么在对序列进行一次变换后，若移动的字母是 A 则 x\rightarrow x-1,y\rightarrow y+1。对于其他字母也是类似的。\ 若我们对整个序列变换完整的一周后，若三个量都未降至过负数，那么我们可以猜测这个序列是合法的。而证明我们可以采用构造性证明，我们可以将位于序列的前 x 个 A 用于构建 ABC，中间的 n-x-y 个用于构造 CAB，最后的 y 个构造 BCA。以此类推便可以证明。

由我们对序列变化对 x,y,z 的推导，令 pre_i 表示前缀中某个字符的个数，那么，在变化中，x,y,z 可以表示为：

&x_i=x-pre_{i,a}+pre_{i,c}\\ &y_i=y-pre_{i,b}+pre_{i,a}\\ &z_i=z-pre_{i,c}+pre_{i,b} \end{cases}

并且，x,y,z 在变化过程中不能变为负数，则我们可以推出不等式：

&x\ge \max\space{pre_{i,a}-pre_{i,c}}\\ &y\ge \max\space{pre_{i,b}-pre_{i,a}}\\ &z\ge \max\space{pre_{i,c}-pre_{i,b}} \end{cases}

于是我们便可以通过线性复杂度检验一组 x,y,z 是否合法。

那么，在没有 s_1,s_2 限制的时候，令 x=\max{a-c}，并且满足 x+y+z\leq n 即可。\ 把上面所说的重要信息全部丢进状态设计里，对于 f_{a,b,c,0/1,0/1} 我们已经处理了 a 个 A，b 个 B 和 c 个 C，并且是否满足了 x,y 的限制，因为 z 没有设置在状态中，所以我们要保证 z\leq n-x-y。\ 面对 ? 我们则可以把它当作 A，B，C 都做一遍相应的操作与判断。

于是我们就可以写出代码，通过本题的弱化版。\ 在外层枚举 x,y 在内层枚举 a,b,c 并进行判断与转移，总复杂度为 O(N^5)。

#include <bits/stdc++.h>
using namespace std;
constexpr int N=60,M=180,mod=998244353;
typedef long long int ui;
int T,tid,n,m;
string s1,s2,s;
ui f[N][N][N][2][2];
ui ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
//  cin>>T>>tid;
//  while(T--)
//  {
        cin>>n>>s;
        m=n*3;
        s=" "+s;
        ans=0;
        for(int x=0;x<=n;x++)
            for(int y=0;y<=n;y++)
            {
                int z=n-x-y;
                memset(f,0,sizeof f);
                f[0][0][0][0][0]=1;
                for(int a=0;a<=n;a++)
                    for(int b=0;b<=n;b++)
                    {
                        if(b-a>y)
                            continue;
                        for(int c=0;c<=n;c++)
                        {
                            int i=a+b+c+1;
                            if(a-c>x || z<c-b || i>m)
                                continue;
                            if(s[i]=='A' || s[i]=='?')
                            {
                                int mz1=((a+1-c)==x),mz2=((b-a-1)==y);
                                (f[a+1][b][c][mz1][mz2]+=f[a][b][c][0][0])%=mod;
                                (f[a+1][b][c][1][mz2]+=f[a][b][c][1][0])%=mod;
                                (f[a+1][b][c][mz1][1]+=f[a][b][c][0][1])%=mod;
                                (f[a+1][b][c][1][1]+=f[a][b][c][1][1])%=mod;
                            }
                            if(s[i]=='B' || s[i]=='?')
                            {
                                int mz1=((a-c)==x),mz2=((b+1-a)==y);
                                (f[a][b+1][c][mz1][mz2]+=f[a][b][c][0][0])%=mod;
                                (f[a][b+1][c][1][mz2]+=f[a][b][c][1][0])%=mod;
                                (f[a][b+1][c][mz1][1]+=f[a][b][c][0][1])%=mod;
                                (f[a][b+1][c][1][1]+=f[a][b][c][1][1])%=mod;
                            }
                            if(s[i]=='C' || s[i]=='?')
                            {
                                int mz1=((a-c-1)==x),mz2=((b-a)==y);
                                (f[a][b][c+1][mz1][mz2]+=f[a][b][c][0][0])%=mod;
                                (f[a][b][c+1][1][mz2]+=f[a][b][c][1][0])%=mod;
                                (f[a][b][c+1][mz1][1]+=f[a][b][c][0][1])%=mod;
                                (f[a][b][c+1][1][1]+=f[a][b][c][1][1])%=mod;
                            }
//                          cout<<f[a][b][c][0][0]<<' '<<f[a][b][c][0][1]<<'\n';
//                          cout<<f[a][b][c][1][0]<<' '<<f[a][b][c][1][1]<<'\n';
//                          cout<<'\n';
                        }
                    }
                (ans+=f[n][n][n][1][1])%=mod;
            }
        cout<<ans<<'\n';
//  }
    return 0;
}

回到本题，对于加入的限制，我们需要找到最小的 x_0,y_0 满足 x_0\ge\max{a-c},y_0\ge\max{b-a},x_0\in s_1,y_0\in s_2，如果该序列合法，那么 x_0,y_0 必定满足条件。

我们可以沿用上面的状态，将最后的两个状态改为是否可以使最小的 x_0,y_0 满足条件，时间复杂度不变，代码如下。

#include <bits/stdc++.h>
using namespace std;
constexpr int N=65,M=180;
typedef unsigned int ui;
int T,tid,n,m;
string s1,s2,s;
ui f[N][N][N][2][2];
ui ans;
int xx,yy;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T>>tid;
    while(T--)
    {
        cin>>n>>s1>>s2>>s;
        if(T)
        {
            cout<<"-1\n";
            continue;
        }
        m=n*3;
        s=" "+s;
        ans=0;
        xx=-1;
        for(int x=0;x<=n;x++)
        {
            if(s1[x]=='0')
                continue;
            yy=-1;
            for(int y=0;y<=n;y++)
            {
                if(s2[y]=='0')
                    continue;
                int z=n-x-y;
                memset(f,0,sizeof f);
                f[0][0][0][!~xx][!~yy]=1;
                for(int a=0;a<=n;a++)
                    for(int b=0;b<=n;b++)
                    {
                        if(b-a>y)
                            continue;
                        for(int c=0;c<=n;c++)
                        {
                            int i=a+b+c+1;
                            if(a-c>x || z<c-b || i>m)
                                continue;
                            if(s[i]=='A' || s[i]=='?')
                                for(int mz=a-c>xx;mz<=1;mz++)
                                    f[a+1][b][c][mz|(a-c+1>xx)][0]+=f[a][b][c][mz][0],
                                    f[a+1][b][c][mz|(a-c+1)>xx][1]+=f[a][b][c][mz][1];
                            if(s[i]=='B' || s[i]=='?')
                                for(int mz=a-c>xx;mz<=1;mz++)
                                    f[a][b+1][c][mz][(b-a+1)>yy]+=f[a][b][c][mz][0],
                                    f[a][b+1][c][mz][1]+=f[a][b][c][mz][1];
                            if(s[i]=='C' || s[i]=='?')
                                for(int mz=a-c>xx;mz<=1;mz++)
                                    f[a][b][c+1][mz][0]+=f[a][b][c][mz][0],
                                    f[a][b][c+1][mz][1]+=f[a][b][c][mz][1];
//                          cout<<f[a][b][c][0][0]<<' '<<f[a][b][c][0][1]<<'\n';
//                          cout<<f[a][b][c][1][0]<<' '<<f[a][b][c][1][1]<<'\n';
//                          cout<<'\n';
                        }
                    }
                ans+=f[n][n][n][1][1];
                yy=y;
            }
            xx=x;
        }
        cout<<ans<<'\n';
    }
    return 0;
}