首页 > ACM题库 > HDU-杭电 > HDU 4409-Family Name List-模拟-[解题报告]HOJ
2015
07-16

HDU 4409-Family Name List-模拟-[解题报告]HOJ

Family Name List

问题描述 :

Kong belongs to a huge family. Recently he got a family name list which lists all men (no women) in his family over many generations.

The list shows that the whole family has a common ancestor, let’s call him Mr. X. Of course, everybody except Mr.X in the list is Mr. X’s descendant. Everybody’s father is shown in the list except that Mr. X’s father is not recorded. We define that Mr. X’s generation number is 0. His son’s generation number is 1.His grandson’s generation number is 2, and so on. In a word, everybody’s generation number is 1 smaller than his son’s generation number. Everybody’s generation number is marked in some way in the list.

Now Kong is willing to pay a lot of money for a program which can re-arrange the list as he requires ,and answer his questions such as how many brothers does a certain man have, etc. Please write this program for him.

输入:

There are no more than 15 test cases.
For each test case:
The first line is an integer N( 1 <= N <= 30,000), indicating the number of names in the list.
The second line is the name of Mr. X.
In the next N-1 lines, there is a man’s name in each line. And if the man’s generation number is K, there are K dots( ‘.’) before his name.

Please note that :
1) A name consists of only letters or digits( ’0′-’9′).
2) All names are unique.
3) Every line’s length is no more than 60 characters.
4) In the list, a man M’s father is the closest one above M whose generation number is 1 less than M.
5) For any 2 adjacent lines in the list, if the above line’s generation number is G1 and the lower line’ s generation number is G2, than G2 <= G1 +1 is guaranteed.

After the name list, a line containing an integer Q(1<=Q<=30,000) follows, meaning that there are Q queries or operations below.

In the Next Q lines, each line indicates a query or operation. It can be in the following 3 formats:
1) L
Print the family list in the same format as the input, but in a sorted way. The sorted way means that: if A and B are brothers(cousins don’t count), and A’s name is alphabetically smaller than B’s name, then A must appear earlier than B.
2) b name
Print out how many brothers does "name" have, including "name" himself.
3) c name1 name2
Print out the closest common ancestor of "name1" and "name2". "Closest" means the generation number is the largest. Since Mr. X has no ancestor in the list, so it’s guaranteed that there is no question asking about Mr. X’s ancestor.

The input ends with N = 0.

输出:

There are no more than 15 test cases.
For each test case:
The first line is an integer N( 1 <= N <= 30,000), indicating the number of names in the list.
The second line is the name of Mr. X.
In the next N-1 lines, there is a man’s name in each line. And if the man’s generation number is K, there are K dots( ‘.’) before his name.

Please note that :
1) A name consists of only letters or digits( ’0′-’9′).
2) All names are unique.
3) Every line’s length is no more than 60 characters.
4) In the list, a man M’s father is the closest one above M whose generation number is 1 less than M.
5) For any 2 adjacent lines in the list, if the above line’s generation number is G1 and the lower line’ s generation number is G2, than G2 <= G1 +1 is guaranteed.

After the name list, a line containing an integer Q(1<=Q<=30,000) follows, meaning that there are Q queries or operations below.

In the Next Q lines, each line indicates a query or operation. It can be in the following 3 formats:
1) L
Print the family list in the same format as the input, but in a sorted way. The sorted way means that: if A and B are brothers(cousins don’t count), and A’s name is alphabetically smaller than B’s name, then A must appear earlier than B.
2) b name
Print out how many brothers does "name" have, including "name" himself.
3) c name1 name2
Print out the closest common ancestor of "name1" and "name2". "Closest" means the generation number is the largest. Since Mr. X has no ancestor in the list, so it’s guaranteed that there is no question asking about Mr. X’s ancestor.

The input ends with N = 0.

样例输入:

9
Kongs
.son1
..son1son2
..son1son1
...sonkson2son1
...son1son2son2
..son1son3
...son1son3son1
.son0	
7
L
b son1son3son1
b son1son2
b sonkson2son1
b son1
c sonkson2son1 son1son2son2
c son1son3son1 son1son2
0 

样例输出:

Kongs
.son0
.son1
..son1son1
...son1son2son2
...sonkson2son1
..son1son2
..son1son3
...son1son3son1
1
3
2
2
son1son1
son1

题目:http://acm.hdu.edu.cn/showproblem.php?pid=4409

题意:给你一个家族表,同时有3种操作,问你操作后的结果。

题解:模拟题,把3个操作处理好就行了。题目有个陷阱,比如a是b的父亲,b是c的父亲,当问你b和c的最近的共同父辈是谁的时候,答案是a而不是b。还有问最开头那个祖先的兄弟时要返回1。

代码:

#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
using namespace std;
#define M 30005
map<int,string> hasht;
map<string,int> hashx;
struct cmp//排序
{
    bool operator()(const int &a, const int &b)
    {
        return hasht.find(a)->second<hasht.find(b)->second;
    }
};
struct point
{
    int pre;//父结点的位置
    set<int,cmp> son;//子结点的位置
    string name;//当前结点的名字
}node[M];
struct px
{
    int idx,len;//结点的位置,结点的辈分
} temp;
int cnt;
stack<struct px> father;
void dfs(int idx,int len)//递归输出族谱
{
    for(int i=0; i<len; ++i) printf(".");
    printf("%s\n",node[idx].name.c_str());
    for(set<int,cmp>::iterator it=node[idx].son.begin(); it!=node[idx].son.end(); ++it)
        dfs(*it,len+1);
}
void out_all()//Print the family list
{
    dfs(0,0);
}
void out_child()//Print out how many brothers does "name" have, including "name" himself.
{
    char s[70];
    scanf("%s",s);
    if(hashx.count(string(s))==0)
    {
        printf("0\n");
        return;
    }
    if(string(s)==node[0].name)
    {
        printf("1\n");
        return;
    }
    int idx=hashx.find(string(s))->second;
    printf("%d\n",node[node[idx].pre].son.size());
}
void out_pre()//Print out the closest common ancestor of "name1" and "name2".
{
    char a[70],b[70];
    scanf("%s%s",a,b);
    set<int> ax;
    int ida=hashx.find(string(a))->second;
    int idb=hashx.find(string(b))->second;
    for(; ida!=-1;)
    {
        ida=node[ida].pre;
        ax.insert(ida);
    }
    for(; idb!=-1;)
    {
        idb=node[idb].pre;
        if(ax.count(idb)!=0) break;
    }
    printf("%s\n",node[idb].name.c_str());
}
int main()
{
    int n,m,pre;
    char s[70],c,ord[10];
    string sx;
    for(; scanf("%d",&n),n;)
    {
        for(int i=0; i<=n; ++i)
        {
            node[i].pre=-1;
            node[i].son.clear();
        }
        hashx.clear();
        hasht.clear();
        for(; !father.empty(); father.pop());
        cnt=0;
        temp.idx=0;
        temp.len=0;
        scanf("%s",s);
        sx=string(s);
        node[cnt++].name=sx;
        hashx.insert(make_pair(sx,0));
        hasht.insert(make_pair(0,sx));
        father.push(temp);
        for(int i=1; i<n; ++i)
        {
            for(; getchar()!='.';);
            int ll=1;
            for(; (c=getchar())=='.'; ++ll);
            s[0]=c;
			int llt;
            for(llt=1;(s[llt]=getchar())!='\n';++llt);
			s[llt]='\0';
            temp.len=ll;
            temp.idx=cnt;
            for(;;)
            {
                struct px tx=father.top();
                if(tx.len>=temp.len)
                    father.pop();
                else
                    break;
            }
            sx=string(s);
            int tx=father.top().idx;
            node[cnt].pre=tx;
            node[cnt].name=sx;
            hasht.insert(make_pair(cnt,sx));
            hashx.insert(make_pair(sx,cnt));
            node[tx].son.insert(cnt);
            cnt++;
            father.push(temp);
        }
        scanf("%d",&m);
        for(; m--;)//处理查询
        {
            scanf("%s",ord);
            if(ord[0]=='L')
                out_all();
            else if(ord[0]=='b')
                out_child();
            else if(ord[0]=='c')
                out_pre();
        }
    }
    return 0;
}

来源:http://blog.csdn.net/acm_ted/article/details/8007857

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acm_ted/article/details/8007857