P3065 [USACO12DEC]第一!First!

Description

Bessie has been playing with strings again. She found that by

changing the order of the alphabet she could make some strings come before all the others lexicographically (dictionary ordering).

For instance Bessie found that for the strings “omm”, “moo”, “mom”, and “ommnom” she could make “mom” appear first using the standard alphabet and that she could make “omm” appear first using the alphabet

“abcdefghijklonmpqrstuvwxyz”. However, Bessie couldn’t figure out any way to make “moo” or “ommnom” appear first.

Help Bessie by computing which strings in the input could be

lexicographically first by rearranging the order of the alphabet. To compute if string X is lexicographically before string Y find the index of the first character in which they differ, j. If no such index exists then X is lexicographically before Y if X is shorter than Y. Otherwise X is lexicographically before Y if X[j] occurs earlier in the alphabet than Y[j].

Solution

先将所有串插入Trie树中, 然后一个一个查询串是否能成为答案, 例如查询串acabd, 并且存在adabc, 若之前已经确定了关系d<c, 那么acabd不可能成为答案, 否则确定d>c.因此这就成为一个动态加边并且查询闭包的问题.也可以建出所有边后看是否存在环.

当然我随便写了个显然不对的做法(没法维护闭包)还得了74分, 233.

正确的姿势是拓扑排序或者是dfs找环.

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
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 30005;
struct Node {
Node *ch[26]; int cnt;
Node () { for (int i = 0; i < 26; i += 1) ch[i] = NULL; cnt = 0; }
};
class Trie {
Node *root;
public:
Trie() { root = new Node(); }
void Insert(std:: string &str) {
Node *node = root;
for (int i = 0; i < str.size(); i += 1) {
int p = str[i] - 'a';
if (not node->ch[p])
node->ch[p] = new Node();
node = node->ch[p];
}
node->cnt = true;
}
bool Query(std:: string &str) {
Node *node = root;
int tmp[26][26];
memset(tmp, 0, sizeof tmp);
for (int i = 0; i < str.size(); i += 1) {
int p = str[i] - 'a';
if (node->cnt) return false;
for (int i = 0; i < 26; i += 1)
if (i != p and node->ch[i]) {
if (tmp[p][i])
return false;
else {
tmp[i][p] = 1;
for (int j = 0; j < 26; j += 1)
tmp[i][j] |= tmp[p][j];
}
}
node = node->ch[p];
}
for (int i = 0; i < 26; i += 1)
for (int j = 0; j < 26; j += 1)
if (tmp[i][j] and tmp[j][i]) return false;
return true;
}
};
std:: string str[N];
bool vis[N];
int main () {
// freopen("a.out", "w", stdout);
int n;
scanf("%d", &n);
Trie* T = new Trie();
for (int i = 0; i < n; i += 1) {
std:: cin >> str[i];
T->Insert(str[i]);
}
int sum = 0;
for (int i = 0; i < n; i += 1)
if (T->Query(str[i]))
vis[i] = true, sum += 1;
printf("%d\n", sum);
for (int i = 0; i < n; i += 1)
if (vis[i]) std:: cout << str[i] << std:: endl;
return 0;
}
-------------本文结束感谢您的阅读-------------