HDU-4545

2018-03-07

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=4545

题目大意

给定两个字符串和一些字母的转换规则，求能否匹配。

思想

网上有的用DP做的。。看了一个DP觉得跟模拟几乎没差。。
我是用模拟做的，没想到一次A了。
正好腾出时间做PA啦，有空学习一下DP解法。

代码

HDU-4545

#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
    int T;
    scanf("%d",&T);
    for (int TT=1;TT<=T;TT++)
    {
        char xm[1005],xx[1005];
        scanf("%s%s",xx,xm);
        int m;
        char ch;
        int change[150][150];
        memset(change,0,sizeof(change));
        scanf("%d",&m);
        while (m--)
        {
            scanf("%c",&ch);
            char fr,to;
            scanf("%c %c",&fr,&to);
            change[fr][0]++;
            change[fr][change[fr][0]]=to;
        }
        int l1=strlen(xx),l2=strlen(xm);
        int len1=l1,len2=l2;
        int p1=0,p2=0;

        while (p1<l1 && p2<l2)
        {
            if (len2 < len1) break;
            if (xx[p1] == xm[p2])
            {
                p1++;
                p2++;
                continue;
            }
            int flag=0;
            for (int i=1;i<=change[xm[p2]][0];i++)
            {
                if (change[xm[p2]][i] == xx[p1])
                {
                    flag=1;
                    break;
                }
            }
            if (flag)
            {
                p1++;
                p2++;
                continue;
            }
            p2++; len2--;
        }
        if (p1 >= l1)
            printf("Case #%d: happy\n",TT);
        else
            printf("Case #%d: unhappy\n",TT);
    }
    return 0;
}

后记

做PA去。。今天就一个水题吧~