首页 > ACM题库 > HDU-杭电 > HDU 2967-Morphing is fun[解题报告]HOJ
2014
02-24

HDU 2967-Morphing is fun[解题报告]HOJ

Morphing is fun

问题描述 :

Morphic is a tree that grows very rapidly, bringing happiness to its owner. It has a single trunk consisting of a number of cells stacked one on top of another. Each cell has one of n possible colors which determine the way it mutates during the night, while nobody can see it. Florists denote these colors by the first n small letters of the English alphabet and know exactly into how many cells, and of what colors, a cell of each color divides. In fact, they have wrote their knowledge down simply with n nonempty words, each word representing the resulting sequence of colors.

A seed of a Morphic has a single cell of color a and is rooted firmly in the ground. As long as the Morphic is still alive, each night all its cells simultaniously morph according to the aforementioned rules, possibly causing an exponential growth because each new cell is of the same size as the original one.

For example, if rules say that a becomes ab, and b becomes ca, then after two nights a seed will evolve to a trunk consisting of 4 cells: abca.

Therefore the top of a Morphic is usually hidden in clouds. The only way to tell if it is still alive is to check if visible part of the trunk is changing colors. In order to do so, one can build enormously high (yet still of constant height) tower, and watch from its top a fixed fragment of the trunk.

As you can easily see, it is either suficient to observe first k cells from the bottom for some fixed k, or no matter how high the tower is, you will not be able to tell for sure if a Morphic died. The latter happens when for every k, rules cause the k-th cell to eventually stop changing colors, even though the
tree is still alive and mutating.

To prevent waste of money on building such enormous towers, you are to write a program that
determines if it is possible to monitor health of a Morphic.

输入:

The input contains several Morphics descriptions. The first line contains the number of descriptions t (t <= 10^4) that follow. Each of them begins with the number of colors n (1 <= n <= 26).

Next n lines contain the rules by which the Morphic grows. The i-th one describes the sequence of colors in bottom-up order obtained from a single cell of i-th color. Each line contains at most 100 lowercase English letters.

输出:

The input contains several Morphics descriptions. The first line contains the number of descriptions t (t <= 10^4) that follow. Each of them begins with the number of colors n (1 <= n <= 26).

Next n lines contain the rules by which the Morphic grows. The i-th one describes the sequence of colors in bottom-up order obtained from a single cell of i-th color. Each line contains at most 100 lowercase English letters.

样例输入:

4
2
ab
a
3
ba
c
c
3
ba
c
b
3
bbbbbbbbbbbbbbb
ccccccccccccccc
c

样例输出:

YES
YES
NO
YES

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int maxn=110;
char s[maxn][maxn];
int visit[maxn];
int n;
int len[maxn];
int ans[maxn];
int end[maxn],fa[maxn];

int solve(int dep,int num)
{
 if (end[dep]!=0) return end[dep]-1;
 visit[dep]=num;
 for(int i=0;i<len[dep];i++)
 {
 ans[dep]=i;
 int t=s[dep][i]-'a';
 if (visit[t])
 {
 int maxs=0;
 int counts=0;
 for(int j=0;j<n;j++)
 if (visit[j]>=visit[t])
 {
 if (ans[j]>0) return 1;
 if (len[j]>maxs) maxs=len[j];
 counts++;
 }
 if (counts>1) return 2;
 if (maxs>1) return 1;
 return 0;
 }
 int now=solve(t,num+1);
 if (now==0) continue;
 return now;
 }
 visit[dep]=0;
 return 0;
}

int find_fa(int u)
{
 if (fa[u]!=u) fa[u]=find_fa(fa[u]);
 return fa[u];
}

int main()
{
 int cas;

 //freopen("in.in","r",stdin);
 // freopen("out.out","w",stdout);
 scanf("%d",&cas);
 while(cas--)
 {
 scanf("%d",&n);
 for(int i=0;i<n;i++)
 {
 scanf("%s",s[i]);
 len[i]=strlen(s[i]);
 }
 memset(end,0,sizeof(end));
 for(int i=0;i<n;i++) fa[i]=i;
 for(int i=0;i<n;i++)
 {
 int have=0;
 for(int j=0;j<n;j++)
 {
 if (end[j]!=0) continue;
 bool flag=1;
 for(int k=1;k<len[j];k++)
 if (find_fa(s[j][0]-'a')!=find_fa(s[j][k]-'a')) flag=0;
 if (flag)
 {
 int t1=find_fa(j);
 int t2=find_fa(s[j][0]-'a');

 if (t1!=t2)
 {
 if (end[t2]==0) continue;
 if (len[t2]==1) end[t1]=1;
 else end[t1]=2;
 fa[t1]=t2;
 have++;
 } else
 {
 if (len[t2]==1) end[t1]=1;
 else end[t1]=2;
 have++;
 }
 }
 }
 if (have==0) break;
 }
 //for(int i=0;i<n;i++) printf("%d %d\n",fa[i],end[i]);
 memset(visit,0,sizeof(visit));
 memset(ans,-1,sizeof(ans));
 int ans=solve(0,1);
 if (ans==2) puts("NO");
 else puts("YES");
 }
}

  1. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识,这句话用《爱屋及乌》描述比较容易理解……

  2. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge