zoj3784 String of Infinity 思维。。。

本文主要是介绍zoj3784 String of Infinity 思维。。。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

堂堂一道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 思维。。。的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---