【CCCC】L3-031 千手观音 (30分) ,离散化,拓扑排序,链式前向星

举报
小哈里 发表于 2022/05/03 00:34:53 2022/05/03
【摘要】 problem L3-031 千手观音 分数 30 作者 陈越 单位 浙江大学 qsgy.JPG 人类喜欢用 10 进制,大概是因为人类有一双手 10 根手指用于计数。于是在千手观音的世界里,数字都是...

problem

L3-031 千手观音
分数 30
作者 陈越
单位 浙江大学
qsgy.JPG

人类喜欢用 10 进制,大概是因为人类有一双手 10 根手指用于计数。于是在千手观音的世界里,数字都是 10 000 进制的,因为每位观音有 1 000 双手 ……

千手观音们的每一根手指都对应一个符号(但是观音世界里的符号太难画了,我们暂且用小写英文字母串来代表),就好像人类用自己的 10 根手指对应 0 到 9 这 10 个数字。同样的,就像人类把这 10 个数字排列起来表示更大的数字一样,ta们也把这些名字排列起来表示更大的数字,并且也遵循左边高位右边低位的规则,相邻名字间用一个点 . 分隔,例如 pat.pta.cn 表示千手观音世界里的一个 3 位数。

人类不知道这些符号代表的数字的大小。不过幸运的是,人类发现了千手观音们留下的一串数字,并且有理由相信,这串数字是从小到大有序的!于是你的任务来了:请你根据这串有序的数字,推导出千手观音每只手代表的符号的相对顺序。

注意:有可能无法根据这串数字得到全部的顺序,你只要尽量推出能得到的结果就好了。当若干根手指之间的相对顺序无法确定时,就暂且按它们的英文字典序升序排列。例如给定下面几个数字:

pat
cn
lao.cn
lao.oms
pta.lao
pta.pat
cn.pat
我们首先可以根据前两个数字推断 pat < cn;根据左边高位的顺序可以推断 lao < pta < cn;再根据高位相等时低位的顺序,可以推断出 cn < oms,lao < pat。综上我们得到两种可能的顺序:lao < pat < pta < cn < oms;或者 lao < pta < pat < cn < oms,即 pat 和 pta 之间的相对顺序无法确定,这时我们按字典序排列,得到 lao < pat < pta < cn < oms。

输入格式:
输入第一行给出一个正整数 N (≤10
5
),为千手观音留下的数字的个数。随后 N 行,每行给出一个千手观音留下的数字,不超过 10 位数,每一位的符号用不超过 3 个小写英文字母表示,相邻两符号之间用 . 分隔。

我们假设给出的数字顺序在千手观音的世界里是严格递增的。题目保证数字是 10
4
进制的,即符号的种类肯定不超过 10
4
种。

输出格式:
在一行中按大小递增序输出符号。当若干根手指之间的相对顺序无法确定时,按它们的英文字典序升序排列。符号间仍然用 . 分隔。

输入样例:
7
pat
cn
lao.cn
lao.oms
pta.lao
pta.pat
cn.pat
输出样例:
lao.pat.pta.cn.oms

solution

//题意:依次给出大小递增的字符串,用.分隔,求字符串大小规则
//思路:将读入的字符串用.分隔后和上一个逐位比较(当前仅当长度相等时才行),然后建图跑拓扑排序即可。
//1,对于相对顺序无法确定,队列换成优先队列,按字典序小的排列
//2. 对于vector存图会超时,用链式前向星存图
//3. 大点指向小点建图会WA,图的结构不同  
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;

//离散化
unordered_map<string, int> mp;
string st[maxn];
int tot=0;

//建图
int head[maxn], in[maxn];
struct Edge{ int to, next; }edge[maxn]; int m=0;
void add_edge(int u, int v){
    edge[m].to = v;
    edge[m].next = head[u];
    head[u] = m++;
}
struct node{
    int id; string s; 
    friend bool operator <(node a, node b) { return a.s > b.s; }
};

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    memset(head,-1,sizeof head);
    //input
    int n;  cin>>n;
    vector<string>pre;
    for(int i = 1; i <= n; i++){
        string s;  cin>>s;
        vector<string>now;
        int cnt = 0;
        for(int j = 0; j < s.size(); j++){
            if(s[j]=='.'){
                string t = s.substr(j-cnt, cnt);
                if(!mp[t])mp[t]=++tot, st[tot]=t;
                now.push_back(t);
                cnt = 0;
            }else if(j == s.size()-1){
                string t = s.substr(j-cnt, cnt+1);
                if(!mp[t])mp[t]=++tot, st[tot]=t;
                now.push_back(t);
            }else{
                cnt++;
            }
        }
        //creat graph
        if(i==1)pre = now;
        else{
            if(pre.size()==now.size()){
                for(int i = 0; i < pre.size(); i++){
                    if(pre[i] != now[i]){
                        add_edge(mp[pre[i]], mp[now[i]]);//小的向大的连一条边
                        in[mp[now[i]]]++;
                        break;
                    }else continue;
                }
            }
            pre = now;
        }
    }
    //topu sort
    priority_queue<node>q;
    for(int i = 1; i <= tot; i++){
        if(in[i]==0)q.push({i, st[i]});
    }
    vector<string>res;
    while(q.size()){
        node t = q.top();  q.pop();
        res.push_back(t.s);
        for(int j = head[t.id]; j != -1; j = edge[j].next){
            in[edge[j].to]--;
            if(in[edge[j].to]==0)q.push({edge[j].to,st[edge[j].to]});
        }
        if(res.size() == tot)break;
    }
    for(int i = 0; i < res.size(); i++){
        if(i!=0)cout<<".";
        cout<<res[i];
    }
    return 0;
}



  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89

文章来源: gwj1314.blog.csdn.net,作者:小哈里,版权归原作者所有,如需转载,请联系作者。

原文链接:gwj1314.blog.csdn.net/article/details/124521306

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200