自动搬运

查看原文

来自洛谷，原作者为

	Ginger_he .

搬运于2025-08-24 22:36:43，当前版本为作者最后更新于2022-02-27 14:53:31，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

本文同步更新于博客园

题目描述

已知 $4$ 个长度为 $6$ 的字符串，每次给定一个字符串 $s$，现在可以从每个已知的字符串中选 $0$ 或 $1$ 个字母，问是否能组成 $s$。

题解

对于每次询问，我们用一个桶 $a$ 记录下 $s$ 中 $26$ 个出现的次数。然后 dfs 枚举从每个字符串中选出哪个字母，也用一个桶 $b$ 记录下出现的次数。若 $\displaystyle\sum_{i=1}^{26}[b_i\ge a_i]=26$，则输出 YES；否则输出 NO。

Code

#include<bits/stdc++.h>
using namespace std;
int n,a[30],b[30];
bool flag;
char s[5][10],t[5];
void dfs(int x)
{
	if(flag)
		return;
	if(x==5)
	{
		for(int i=1;i<=26;i++)
		{
			if(a[i]>b[i])
				return;
		}
		flag=1;
		return;
	}
	for(int i=1;i<=6;i++)
	{
		b[s[x][i]-'A'+1]++;
		dfs(x+1);
		b[s[x][i]-'A'+1]--;
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=4;i++)
		scanf("\n%s",s[i]+1);
	for(int i=1;i<=n;i++)
	{
		memset(a,flag=0,sizeof(a));
		scanf("\n%s",t+1);
		for(int j=1;t[j];j++)
			a[t[j]-'A'+1]++;
		dfs(1);
		printf("%s\n",flag?"YES":"NO");
	}
	return 0;
}