【牛客】假的字符串

链接:https://ac.nowcoder.com/acm/contest/907/E
Description
给定n个字符串,互不相等,你可以任意指定字符之间的大小关系(即重定义字典序),求有多少个串可能成为字典序最小的串,并输出它们

Input
第一行一个数表示n
之后n行每行一个字符串表示给定的字符串
Output:
第一行输出一个数x表示可行的字符串个数
之后输出x行,每行输出一个可行的字符串
输出的顺序和输入的顺序一致
SampleInput
6
mcfx
ak
ioi
wen
l
a
SampleOutput
5
mcfx
ioi
wen
l
a
Tips
对于100%的数据,
n <= 30000 , 字符串总长<= 300000
字符集为小写字符
Solution
Trie树判断前缀, 拓扑排序判环

#include <bits/stdc++.h>
 
using namespace std;
 
int trie[300010][26], tot = 1;
bool End[300010];
string s[30010];
int ans[30010], cnt = 0;
int n;
int edge[30][30], deg[30];

bool top_sort()
{
    int res(0);
    queue<int> q;
    for (int i = 0; i < 26; i++)
        if (deg[i] == 0) q.push(i), res |= (1 << i);
    while (q.size())
    {
        int x = q.front(); q.pop();
        for (int i = 0; i < 26; i++)
            if (edge[x][i])
            	if (--deg[i] == 0)
            		q.push(i), res |= (1 << i);
    }
    return res == ((1 << 26) - 1);
}

void insert(const string &a)
{
    int p = 1;
    for (int i = 0; i < a.size(); i++)
    {
        int ch = a[i] - 'a';
        if (trie[p][ch] == 0) trie[p][ch] = ++tot;
        p = trie[p][ch];
    }
    End[p] = true;
}
 
bool search(const string &a)
{
    memset(edge, 0, sizeof edge);
    memset(deg, 0, sizeof deg);
    int p = 1;
    for (int i = 0; i < a.size(); i++)
    {
        if (End[p]) return false;
        for (int j = 0; j < 26; j++)
            if (trie[p][j] && j != a[i] - 'a' && edge[a[i] - 'a'][j] == 0)
                edge[a[i] - 'a'][j] = 1, deg[j]++;
        p = trie[p][a[i] - 'a'];
    }
    return top_sort();
}
 
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
     
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        insert(s[i]);
    }
    for (int i = 1; i <= n; i++)
        if (search(s[i]))
            ans[++cnt] = i;
    cout << cnt << '\n';
    for (int i = 1; i <= cnt; i++)
        cout << s[ans[i]] << '\n';
     
    return 0;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
今天 12:10
点赞 评论 收藏
分享
06-12 17:46
门头沟学院 Java
运营你豪哥:来说重点: ​1.项目前置,时间倒序。​​ 2.​项目描述强化结果与量化效果(STAR原则里的R)。​​ ​3.个人技能精炼,明确掌握程度,突出核心。​​ ​4.增加强有力开头的个人总结部分。​​ 5.​优化教育背景(成绩排名)、合并奖项与活动。​​
听劝,我这个简历该怎么改...
点赞 评论 收藏
分享
06-15 02:05
已编辑
南昌航空大学 数据分析师
Eason三木:你如果想干技术岗,那几个发公众号合唱比赛的经历就去掉,优秀团员去掉,求职没用。然后CET4这种不是奖项,是技能,放到下面的专业技能里或者单独列一个英语能力。 另外好好改改你的排版,首行缩进完全没有必要,行间距好好调调,别让字和标题背景黏在一起,你下面说能做高质量PPT你得展现出来啊,你这简历排版我用PPT做的都能比你做的好。 然后自我评价,你如果要干数据工程师,抗压能力强最起码得有吧。
简历中的项目经历要怎么写
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务