【USACO12DEC】【Bzoj3012】【Luogu3065】First!

Source and Judge

Usaco2012 Dec
Bzoj3012
Luogu3065

Problem

【Description】
给n个字符串,问如果重定义字典序,有哪些单词可能排在字典的第一名。
字典序计算:
1. 优先找不同的字母
2. 其次长度小则前
【Input】
字符串总量n
每行一个字符串
【Output】
满足条件的数量
每行一个,输出原串(按输入顺序)
【Limited conditions】
1 <= N <= 30,000
字符总数不会超过300,000
只有小写字母
【Sample input】
4
omm
moo
mom
ommnom
【Sample output】
2
omm
mom
【Sample explanation】
如果定义 o 在 m 之前,则omm 可排第一,
如果定义 m 在 o 之前,则mom 可排第一,
但余下两个单词是无论如何不可能排在第一的。

Record

2h

Analysis

请先思考

首先:

  1. 从面向数据编程的角度,看到字符串总长度,而且只有小写字母,可以考虑字典树
  2. 从字符串比较的角度,是从前往后的,也就是前缀,那也是字典树

然后可以考虑枚举每一个字符串,然后什么条件下它能够成为字典序最小的呢?

  1. 不能存在某个字符串是它的前缀
  2. 对于某个位置,如果前面都一样,则这个不一样的部分,我的将是最小的
    显然两个都跟前缀有关,可以用字典树搞一搞
    然后对于2,产生了一些不等关系

那么有三种思路(大致时间复杂度都是O(N^2)):

  1. 用拓扑排序,如果某一时刻没有入度为0的点,则无解
  2. 用差分约束,有负环无解
  3. 用强连通找环,有环无解
    那么网上的大部分都是用第一种的,事实上这也是性价比最高的,
    所以另外两种就不写了,但是理解还是一定要的。

至于空间的话……网上都说每个串不超过20,
但为了不被卡,用了string,慢也是正常的。

Code

请先思考
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
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<string>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
void chmax(int &x,int y) {if(x<y) x=y;}
void chmin(int &x,int y) {if(x>y) x=y;}
//*******************全局常量*******************
const int MAXN=31000;
//*******************全局定义*******************
string s[MAXN];
//*******************验证*******************
const int C=26;
int ru[C];
bool mp[C][C];
bool check()
{
for(int cnt=1;cnt<=C;cnt++)
{
int i;
for(i=0;i<C;i++) if(ru[i]==0) break;
if(i==C) return 0;//环
ru[i]=-1;
for(int j=0;j<C;j++) if(mp[i][j]) ru[j]--;
}
return 1;
}
//*******************Trie*******************
struct Trie
{
int s;
int ch[26];
bool ed;
};
vector<Trie> a;
void add(int x)
{
int ln=s[x].length();
int now=0;
for(int i=0;i<ln;i++)
{
int t=s[x][i]-'a';
if(a[now].ch[t]==0)
{
a.push_back((Trie){});
a[now].ch[t]=a.size()-1;
}
now=a[now].ch[t];
a[now].s++;
}
a[now].ed=1;
}
bool solve(int x)
{
memset(mp,0,sizeof(mp));
memset(ru,0,sizeof(ru));
int ln=s[x].length();
int now=0;
for(int i=0;i<ln;i++)
{
if(a[now].ed) return 0;
int t=s[x][i]-'a';
for(int j=0;j<C;j++)
if(j!=t and !mp[t][j] and a[ a[now].ch[j] ].s>0)
mp[t][j]=1,ru[j]++;
now=a[now].ch[t];
}
return check();
}
//*******************主函数*******************
char sss[310000];
bool fine[MAXN];
int main()
{
a.push_back((Trie){});
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",sss);
s[i]=sss;
add(i);
}
int cnt=0;
for(int i=1;i<=n;i++) if(solve(i)) fine[i]=1,cnt++;
printf("%d\n",cnt);
for(int i=1;i<=n;i++) if(fine[i]) printf("%s\n",s[i].c_str());
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-04/First.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%