自动搬运

查看原文

来自洛谷，原作者为

	qzmoot 唯有残生相思入骨，我的爱一如既往，至死不渝

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

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

以下是正文

---

题解：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$ 可以表示为：

$$\begin{cases} &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$ 在变化过程中不能变为负数，则我们可以推出不等式：

$$\begin{cases} &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;
}