洛谷 3065 [USACO12DEC]第一!First!

发表于 | 更新于 | 阅读次数：
本文字数： 890 字 | 阅读时长 ≈ 4 分钟

题意简述

你珂以修改字母表的顺序，能否使得一个字符串是n个字符串中字典序最小的字符串？（没有重复）对于每个字符串，你都要输出它是否能成为最小的那个。是输出YES，否则输出NO。

n<=30000，长度和<=300000

思路框架

开TRIE树，对于每个同一层的节点，连一条有向边。然后跑一遍拓扑排序，看看是否矛盾。

具体思路

比如说两个字符串abcc<abcd，那么就表示c要比d在前面。如果还有一个ad<ac，那说明d在c前面。出现了环，所以矛盾了。

我们先把n个字符串都插入到TRIE树上。每个字符串都查询一遍，对于每个点，和它同父亲的不同节点（兄弟节点），假设深度是d，那么其它字符串和这个字符串，第一个不相同的长度就是d。那么我们要求这个字符串是字典序最小的，那么我们从这个点到同一层所有其它节点都要连一条边，表示“小于”。这样才能保证我的字典序是最小的，也就是比任何人都小。

这样建完边，跑一遍拓扑排序。复杂度是O(300000+$26^2n$ )=O(300000+2e7)。能过。

代码

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 355555
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    
    class TRIE
    {
    public:
        int tot=0;int ch[N][26],end[N];
        void Init(){FK(ch);FK(end);tot=0;}
        void Insert(string s) //插入
        {
            int p=0;
            F(i,0,(int)s.size()-1)
            {
                int id=s[i]-'a';
                if (!ch[p][id]) ch[p][id]=++tot;
                p=ch[p][id];
            }
            end[p]++;
        }

        bool g[26][26];int ideg[26];
        queue<int> Q;
        void TopoSort() //拓扑排序：每次找到入度为0的点，删除这些点，更新新的入度。如果最后有的点入度不是0，那肯定是有环了。
        {
            while(!Q.empty()) Q.pop();
            F(i,0,25) if (ideg[i]==0) Q.push(i);
            while(!Q.empty())
            {
                int u=Q.front();Q.pop();
                F(i,0,25) if (g[u][i]) 
                {
                    --ideg[i];
                    if (ideg[i]==0) Q.push(i);
                }
            }
        }
        bool Find(string x)
        {
            //g[a][b]=1：a小于b
            int p=0,len=x.size();
            FK(g);FK(ideg);
            F(i,0,len-1)
            {
                if (end[p])//这个字符串的一个前缀是其他字符串，那肯定不是最小
                {
                    return false;
                }
                int id=x[i]-'a';
                F(j,0,25) if (j!=id and ch[p][j] and !g[id][j]) 
                //j和id同父亲，j是id的兄弟节点
                {
                    g[id][j]=1;// id要是最小的，所有的j都要大于id
                    ++ideg[j]; //加边顺便维护入度
                }
                p=ch[p][id];
            }
            TopoSort();
            bool flag=true;
            F(i,0,25) if (ideg[i]) flag=false;
            return flag;
        }
    }T;
    int n;string s[N];char t[N];
    void Input()
    {
        cin>>n;
        F(i,1,n) cin>>s[i];
    }
    bool cxk[N];
    void Soviet()
    {
        T.Init();
        F(i,1,n) T.Insert(s[i]);

        int cnt=0;
        F(i,1,n) 
        {
            if (T.Find(s[i])) 
            {
                ++cnt,cxk[i]=1;
            }
        }
        
        cout<<cnt<<endl;
        F(i,1,n) if (cxk[i]) cout<<s[i]<<endl;
    }

    #define Flan void
    Flan IsMyWife()
    {
        ios::sync_with_stdio(false);cin.tie(0);
        Input();
        Soviet();
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w