加载中…
个人资料
jackchess
jackchess
  • 博客等级:
  • 博客积分:0
  • 博客访问:42,240
  • 关注人气:37
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

J Family Name List (HDU 4409)

(2012-09-22 17:54:10)
标签:

乱搞

杂谈

#include <cstdio>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <iostream>

using namespace std;

int main(void)
{
    int n;
    
    while(scanf("%d", &n) != EOF && n)
    {
        map<string, set<string> > son;
        map<string, string> father;
        map<int, string> sta;
        map<string, int> cnt;

        char name[64];
        scanf("%s", name);
        
        sta[0] = string(name);
        cnt[name] = 0;
        
        for(int i = 1; i < n; ++i)
        {
            scanf("%s", name);
            int gen = 0;
            while(name[gen] == '.')
                ++ gen;

            cnt[name+gen] = gen;
            father[name+gen] = sta[gen-1];
            sta[gen] = name+gen;
            son[father[name+gen]].insert(name+gen);
        }
        
        int K;
        scanf("%d", &K);
        for(int i = 0; i < K; ++i)
        {
            char order[4];
            scanf("%s", order);
            
            if(order[0] == 'L')
            {
                stack<string> stk;

                stk.push(sta[0]);
                while(stk.size())
                {
                    string now = stk.top();
                    for(int j = 0; j < cnt[now]; ++j)
                        putchar('.');
                    cout << now << endl;
                    stk.pop();
                    for(set<string>::reverse_iterator it = son[now].rbegin(); it != son[now].rend(); ++it)
                    {
                        stk.push(*it);
                    }
                }
            }
            
            if(order[0] == 'b')
            {
                scanf("%s", name);
                if(cnt[name] == 0) printf("1\n");
                else printf("%d\n", son[father[name]].size());
            }
            
            if(order[0] == 'c')
            {
                string name1, name2;
                cin >> name1 >> name2;
                
                name1 = father[name1];
                name2 = father[name2];
                while(cnt[name1] != cnt[name2])
                {
                    if(cnt[name1] > cnt[name2])
                        name1 = father[name1];
                    else name2 = father[name2];
                }
                
                while(name1 != name2)
                {
                    name1 = father[name1];
                    name2 = father[name2];
                }
                cout << name1 << endl;
            }

        }
    }
}
            


0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有