洛谷P8185题解

Ginger_he · 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;
}