首页 > 其他 > 详细

zoj3784 String of Infinity 思维。。。

时间:2014-05-07 08:23:12      阅读:415      评论:0      收藏:0      [点我收藏+]

堂堂一道AC自动机被我们乱搞过了 目前zoj排名第一 从run memory目测还没人像我们这样搞的 笑死了


看题目第一遍不太懂第三个条件的意思。

通过样例,第一个明显no,第二个yes的构造方法应该是abbabbbabbbb……

由此我们想到,不管题目给定几个字母,我们只要找到一个字母可以无限增长下去、一个字母有限,且两个字母组合在一起不构成banned word

只要存在这样两个字母,那么一定可以构造出来




#include<cstdio>
#include<cstring>

const int maxlen=1e3+5;
int n,m,jud[30][30],vis[30];
char s[maxlen];
void check()
{
    int vvis[30],q[30],num=0;
    memset(vvis,0,sizeof(vvis));
    for (int i=0;s[i];i++)
    {
        vvis[s[i]-‘a‘]++;
        if (vvis[s[i]-‘a‘]==1)
            q[num++]=s[i]-‘a‘;
    }
    if (num==2)
    {
        if (vvis[q[0]]==1)
            jud[q[1]][q[0]]=0;
        if (vvis[q[1]]==1)
            jud[q[0]][q[1]]=0;
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d%d",&n,&m);
        for (int i=0;i<m;i++) vis[i]=1;
        for (int i=0;i<m;i++)
            for (int j=0;j<m;j++)
                if (i==j) jud[i][j]=0;
                else jud[i][j]=1;
        for (int i=0;i<n;i++)
        {
            scanf("%s",s);
            int flag=1;
            for (int j=1;s[j];j++)
                if (s[j]!=s[0])
                {
                    flag=0;
                    break;
                }
            if (flag) vis[s[0]-‘a‘]=0;
            check();
            if (strlen(s)==1)
            {
                for (int i=0;i<m;i++)
                    jud[i][s[0]-‘a‘]=jud[s[0]-‘a‘][i]=0;
            }
        }
        int ans=0;
        for (int i=0;i<m;i++)
        {
            int flag=1;
            if (vis[i])
                for (int j=0;j<m;j++)
                    if (jud[i][j])
                        flag=0;
            if (flag==0) ans=1;
        }
        if (ans) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}


zoj3784 String of Infinity 思维。。。,布布扣,bubuko.com

zoj3784 String of Infinity 思维。。。

原文:http://blog.csdn.net/u011032846/article/details/25082645

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!