1 条题解

  • 0
    @ 2025-8-24 21:46:47

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar xxboyxx
    黄瓜♿||天汪 xxboyxx 射射喵，天汪 xxgirlxx 射射喵||支持炉关

    搬运于2025-08-24 21:46:47，当前版本为作者最后更新于2025-06-10 20:50:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

    以下是正文

    这是一个大号+小号一共提交了192次才A的入的题解。

    思路

    这是一道字符串匹配题，所以可以拿哈希做。

    这个 * 可以当做任意字符串，还可以是空串。

    那么我们就分讨成三种情况：

    第一种：所有字符串都无 *

    这种情况很好办，只需要把所有的字符串的哈希值算出来再比较是否完全相等即可。

    第二种：所有字符串都有 *

    我们发现，字符串第一个 * 和最后一个 * 之间的所有字符对字符串是否匹配是没有影响的，所以我们只需要比较它们的前缀和后缀。

    比如这两个字符串：

    ABC*DE*FG*12345*XYZ

    ABC*DE*GF*6789*WXYZ

    两个字符串中间的部分都可以变成 DEFGGF123456789，而前缀和后缀都相同，所以这两个字符是可以匹配的。

    我们只需要把每个字符串的第一个 * 之前的字符串按照长度来排序，检查每个字符串是否都是下一个的前缀。

    后缀同理，检查每个字符串最后一个 * 之后的字符串是否都是下一个的后缀。

    第三种：有的字符串有 * 而有的字符串没有

    我们可以把字符串分为两类，一类是有 * 的，另一类是没有 * 的。

    首先，所有的没有 * 的字符串都应该像第一种情况那样完全相同，如果是完全相同的话我们就选取其中的一个字符串作为“样本”。

    然后，有 * 的字符串的第一个 * 之前的字符串都应该和样本前缀相同，同理，最后一个 * 之后的字符串都应该和样本后缀相同。这里有一点需要注意，如果待匹配串中非 * 的字符比“样本”还要多的话是不行的。

    我们对每一个待匹配串的中间部分（这里指最左和最右两个星号之间的部分）和“样本”的中间部分（这里指去掉和待匹配串匹配的前缀和后缀的部分）进行匹配，以 * 作为间隔。

    比如待匹配串是 ABC*DE*FGH*I*123 ，“样本”是 ABC123DEFGH456I789XYZ123，要进行匹配的子串分别是 DE、FGH、I，在“样本”中间部分 123DEFGH456I789XYZ 中可以找到这些串，所以可以匹配。

    注意

    题目里面说 NN 和最长字符串长度的积不超过 2×1082\times10^8，所以这里需要用到 vector。

    这里的“输入文件不超过10M”其实就是字符总数不超过 10710^7 的意思。

    题目的样例有点水，这里提供几个样例。

    如果待匹配串中非 * 的字符比“样本”还要多的话是不行的（在前文中提到过）。

    input:

    2
2
AB*BA
ABA
2
A*A
A

    output:

    N
N

    只有一个串无论如何都可以匹配。

    input:

    2
1
ABC
1
A*B*C

    output:

    Y
Y

    可以有连续的 *。

    input:

    2
2
AB**C
ABDC
2
A*B**C
AZ***K*DC

    output:

    Y
Y

    朴素的情况一。

    input:

    2
3
ABC123
ABC123
ABC123
2
ABCD
ABDC

    output:

    Y
N

    朴素的情况二。

    input:

    4
2
ABC*DE*FG*12345*XYZ
ABC*DE*GF*6789*WXYZ
2
ABC*DE*FG*12345*XYZ
ABC*DE*GF*6789*XYZW
2
ABC*DEF
AB*F
3
AB*123XYZ*ASD*123DFS*LL
A*DFSDFS*123*SADSDA*TLHLL
*231*DFS*JIJETR*TLHLL*DL*SL*

    output:

    Y
N
Y
Y

    朴素的情况三。

    input:

    4
2
ABC*DE*FGH*I*123
ABC123DEFGH456I789XYZ123
7
ABCDEFGHIJK
AB*DE*HI*JK
A*H*K
*DEF*GH*K
ABCDEFGHIJK
ABC*DEF*GHI*JK
*B*D*GH*I*
3
ABCDEFG
AB*D*FG*
ABCD*DE*FG
4
ABCDEFGHIJKLMN
ABC*DEFI*K*MN
A*C*EFG*I*N
*DEFGH*KL*

    output:

    Y
Y
N
N

    代码

    #include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int t,n,sum=0,flag=0;
const int N=100005,M=10000005;
const int B=233;
vector<char> a[N];
int c[M];
vector<char> d[N];
bool f[M];
int e[M];
int h[M];
vector<char> g;
bool cmp(vector<char> a,vector<char> b)
{
	return a.size()<b.size();
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	h[0]=1;
	for (int i=1;i<=M-5;i++)//这个地方一定要写成M-5否则可能会RE 
		h[i]=h[i-1]*B;
	while (t--)
	{
		sum=0,flag=0;
		cin>>n;
		for (int i=1;i<=n;i++)
		{
			string s;
			cin>>s;
			a[i].clear();
			a[i].push_back(0);
			for (int j=0;j<s.length();j++)
				a[i].push_back(s[j]);
		}
		for (int i=1;i<=n;i++)
		{
			int ff=0;
			for (int j=1;j<=a[i].size()-1;j++)
			{
				if (a[i][j]=='*')
				{
					ff=1;
					break;
				}
			}
			if (ff==0)//这里的f代表这个字符串是否含有'*'，1代表没有，0代表有 
			{
				sum++;
				f[i]=1;
			}
			else
				f[i]=0;
		}
		if (sum==n)//情况1 
		{
			for (int i=1;i<=n;i++)//求出每个字符串的哈希值 
			{
				int x=0;
				for (int j=1;j<=a[i].size()-1;j++)
					x=x*B+a[i][j];
				c[i]=x;
			}
			for (int i=2;i<=n;i++)
			{
				if (c[i]!=c[i-1])
				{
					flag=1;
					break;
				}
			}
		}
		else if (sum==0)//情况2 
		{
			int x,y;
			for (int i=1;i<=n;i++)
			{
				d[i].clear();
				d[i].push_back(0);
				for (int j=1;j<=a[i].size()-1;j++)
				{
					if (a[i][j]=='*')
						break;
					d[i].push_back(a[i][j]);
				}
			}
			sort(d+1,d+n+1,cmp);//用长度排序 
			for (int i=1;i<=n;i++)
			{
				x=0;
				for (int j=1;j<=d[i].size()-1;j++)
				{
					x=x*B+d[i][j];//这里的x代表当前哈希值 
					if (i!=1 && j==d[i-1].size()-1)//哈希值求到了与上一次前缀的长度相同的地方 
					{
						if (x!=y)//这里的y代表上一次前缀的哈希值 
						{
							flag=1;
							break;
						}
					}
				}
				if (flag==1)
					break;
				y=x;
			}
			if (flag==0)
			{
				for (int i=1;i<=n;i++)//与前缀处理方式相同 
				{
					d[i].clear();
					d[i].push_back(0);
					for (int j=a[i].size()-1;j>=1;j--)
					{
						if (a[i][j]=='*')
							break;
						d[i].push_back(a[i][j]);
					}
				}
				sort(d+1,d+n+1,cmp);
				for (int i=1;i<=n;i++)
				{
					x=0;
					for (int j=1;j<=d[i].size()-1;j++)
					{
						x=x*B+d[i][j];
						if (i!=1 && j==d[i-1].size()-1)
						{
							if (x!=y)
							{
								flag=1;
								break;
							}
						}
					}
					if (flag==1)
						break;
					y=x;
				}
			}
		}
		else
		{
			g.clear();
			int tot=0;
			for (int i=1;i<=n;i++)//判断每个不带'*'的字符串是否都相同 
			{
				if (f[i]==1)
				{
					int x=0;
					for (int j=1;j<=a[i].size()-1;j++)
						x=x*B+a[i][j];
					c[++tot]=x;
					if (g.empty())
					{
						g.push_back(0);
						for (int j=1;j<=a[i].size()-1;j++)
							g.push_back(a[i][j]);
					}
				}
			}
			for (int i=2;i<=tot;i++)
			{
				if (c[i]!=c[i-1])
				{
					flag=1;
					break;
				}
			}
			for (int i=1;i<=n;i++)//检查是否待匹配串中非'*'的字符比样本还要多 
			{
				if (f[i]==0)
				{
					int sum=0;
					for (int j=1;j<=a[i].size()-1;j++)
						if (a[i][j]!='*')
							sum++;
					if (sum>g.size()-1)
					{
						flag=1;
						break;
					}
				}
			}
			if (flag==0)
			{
				for (int i=1;i<=n;i++)//判断前缀是否合法 
				{
					if (f[i]==0)
					{
						int x=0,y=0;
						for (int j=1;j<=a[i].size()-1;j++)
						{
							if (a[i][j]=='*')
								break;
							x=x*B+a[i][j];
							y=y*B+g[j];
							sum++;
						}
						if (x!=y)
						{
							flag=1;
							break;
						}
					}
				}
				for (int i=1;i<=n;i++)//判断后缀是否合法 
				{
					if (f[i]==0)
					{
						int x=0,y=0;
						for (int j=a[i].size()-1;j>=1;j--)
						{
							if (a[i][j]=='*')
								break;
							x=x*B+a[i][j];
							y=y*B+g[g.size()-1-(a[i].size()-1-j)];
						}
						if (x!=y || flag==1)
						{
							flag=1;
							break;
						}
					}
				}
				if (flag==0)
				{
					for (int i=1;i<=n;i++)
					{
						if (f[i]==0)
						{
							int x,y,z;
							for (int j=1;j<=a[i].size()-1;j++)
							{
								x=j;//x代表待匹配串也是样本的开始匹配的地方 
								if (a[i][j]=='*')
									break;
							}
							for (int j=a[i].size()-1;j>=1;j--)
							{
								y=g.size()-(a[i].size()-1-j)-1;//y代表样本结束匹配的地方 
								z=j;//z代表待匹配串结束匹配的地方 
								if (a[i][j]=='*')
									break;
							}
							if (y<=0)
							{
								flag=1;
								break;
							}
							int t1=0,t2=0,ff=0,tt=0,sum=0;
							for (int j=x;j<=z;j++)//以'*'为分隔找待匹配子串 
							{
								if (ff==0)
								{
									if (a[i][j]!='*')
									{
										ff=1;
										sum++;
										t1=t1*B+a[i][j];
									}
								}
								else
								{
									if (a[i][j]=='*')
									{
										c[++tt]=t1;//t1是这个子串的哈希值 
										e[tt]=sum;//sum是这个子串的长度 
										ff=0;
										t1=0;
										sum=0;
									}
									else
									{
										sum++;
										t1=t1*B+a[i][j];
									}
								}
							}
							int p=1,k=0,flagg=0;
							if (x>y)
								flagg=1;
							for (int j=x;j<=y;j++)
							{
								t2=t2*B+g[j];
								k++;
								if (k>e[p])//如果现在区间长度大于待匹配子串的长度了就该删掉最前面的一位了 
								{
									t2=t2-g[j-e[p]]*h[e[p]];
									k--;
								}
								if (c[p]==t2)
								{
									p++;
									k=0;
									t2=0;//匹配成功后应该清空哈希值和区间长度 
								}
								if (p>tt)//所有子串匹配成功 
								{
									flagg=1;
									break;
								}
							}
							if (flagg==0)
							{
								flag=1;
								break;
							}
						}
					}
				}
			}
		}
		if (flag==0)
			cout<<"Y\n";
		else
			cout<<"N\n";
	}
    return 0;
}
/*
最后：
感谢Hollow_Knight的抢夺最优解+卡常+调试+嘲讽
感谢wjj201p的卡常+调试
感谢Little_x_starTYJ提供的AI技术支持
感谢radio、tanlihan的嘲讽
*/
    • 1

    [HNOI2014] 抄卡组

    信息

    ID
    2307
    时间
    1000ms
    内存
    512MiB
    难度
    6
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 19ms