2019.12.7 玩具取名

题目描述

某人有一套玩具，并想法给玩具命名。首先他选择\(WING\)四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个字母用\(“WING”\)中任意两个字母代替，使得自己的名字能够扩充得很长。

现在，他想请你猜猜某一个很长的名字，最初可能是由哪几个字母变形过来的。

输入格式

第一行四个整数\(W,I,N,G\)。表示每一个字母能由几种两个字母所替代。

接下来\(W\)行，每行两个字母,表示\(W\)可以用这两个字母替代。

接下来\(I\)行，每行两个字母,表示\(I\)可以用这两个字母替代。

接下来\(N\)行，每行两个字母,表示\(N\)可以用这两个字母替代。

接下来\(G\)行，每行两个字母,表示\(G\)可以用这两个字母替代。

最后一行一个长度不超过\(Len\)的字符串。表示这个玩具的名字。

输出格式

一行字符串，该名字可能由哪些字母变形而得到。（按照\(WING\)的顺序输出）

如果给的名字不能由任何一个字母变形而得到则输出\(“The\) \(name\) \(is\) \(wrong!”\)

输入输出样例

输入 #1

1 1 1 1
II
WW
WW
IG
IIII

输出 #1

IN

说明/提示

\(30\%\)数据满足\(Len\leq 20\)，\(W,I,N,G\leq 6\)

\(100\%\)数据满足\(Len\leq 200\)，\(W,I,N,G\leq 16\)

请务必注意此题解可能有锅。

考场上此题被放在了\(t3\)，于是没有好好想。结果发现非常水。

简单的区间\(dp\)，符合基本的合并规律。我们用\(dp[i][j][k]\)表示区间\([i,j]\)能否合成第\(k\)号字母。我们枚举中间的端点即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cctype>
#define int long long
#define rep(i,a,n) for(register int i=a;i<=n;++i)
#define dwn(i,n,a) for(register int i=n;i>=a;--i)
using namespace std;
int W,I,N,G,dp[405][405][10];
int e[405][405][10];
char name[1050],str[1050];
static const char let[5]={'\0','W','I','N','G'};//标记四个字符的编号 
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
void write(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x==0)return;
    write(x/10);
    putchar('0'+x%10);
}

signed main()
{
    W=read(),I=read(),N=read(),G=read();
    rep(i,1,W)gets(str+1),e[str[1]-'A'+1][str[2]-'A'+1]['W'-'A'+1]=1;//e数组标记两个字符能不能合成另一个，具体方法同dp数组 
    rep(i,1,I)gets(str+1),e[str[1]-'A'+1][str[2]-'A'+1]['I'-'A'+1]=1;
    rep(i,1,N)gets(str+1),e[str[1]-'A'+1][str[2]-'A'+1]['N'-'A'+1]=1;
    rep(i,1,G)gets(str+1),e[str[1]-'A'+1][str[2]-'A'+1]['G'-'A'+1]=1;//注意e数组最后一维存的是字符ascll,dp存的是字符编号 
    gets(name+1);
    int len=strlen(name+1);
    rep(i,1,len)
    {
        char ch=name[i];
        if(ch=='W')dp[i][i][1]=1;
        if(ch=='I')dp[i][i][2]=1;
        if(ch=='N')dp[i][i][3]=1;
        if(ch=='G')dp[i][i][4]=1;
    }
    rep(i,2,len)
    {
        rep(l,1,len-i+1)
        {
            int r=l+i-1;
            rep(k,l,r-1)
            {
                rep(lef,1,4)//左区间合成了什么 
                {
                    rep(rig,1,4)//右区间合成了什么 
                    {
                        rep(merge,1,4)//最终合成了什么 
                        {
                            if(!e[let[lef]-'A'+1][let[rig]-'A'+1][let[merge]-'A'+1])continue;
                            dp[l][r][merge]=dp[l][r][merge]|dp[l][k][lef]&dp[k+1][r][rig];
                        }
                    }
                }
            }
        }
    }
    if(!(dp[1][len][1]|dp[1][len][2]|dp[1][len][3]|dp[1][len][4]))puts("The name is wrong!");
    if(dp[1][len][1])putchar('W');
    if(dp[1][len][2])putchar('I');
    if(dp[1][len][3])putchar('N');
    if(dp[1][len][4])putchar('G');
    return 0;
}

再强调一下这个题解有锅。\(luogu\)上跑不过去，校内\(oj\)可以。

自己卡一下常数。加油。

2019.12.7 玩具取名

原文：https://www.cnblogs.com/qxds/p/12001582.html