[原创]SPOJ KAOS [Trie]【字符串】

2017-01-05 22:17:18 Tabris_ 阅读数：399

博客爬取于2020-06-14 22:42:27
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54098779

题目连接:http://www.spoj.com/problems/KAOS/
基本都是借（chao）鉴(xi)WannaflyUnion

------------------------------------------------------.
KAOS - Kaos

kaos

Little Lovro likes to play games with words. During the last few weeks he realized that some words don’t like each other.

The words A and B don’t like each other if the word A is lexicographically before the word B, but the word B’ is lexicographically before the word A’, where X’ stands for the word X reversed (if X = “kamen”, then X’ = “nemak”). For example, the words “lova” and “novac” like each other, but the words “aron” and “sunce” don’t like each other.

Given some set of the words, we define the degree of chaos of the set as the number of pairs of different words that don’t like each other.

Write a program that, given a set of words, finds the chaos degree for the set.

input data

The first line of input contains an integer N, 2 ≤ N ≤ 100 000.

Each of the following N lines contains one word – a sequence of at most 10 lowercase letters of the English alphabet (‘a’ – ‘z’). There will be no two identical words in the set.

output data

The first and only line of output should contain a single integer – the chaos degree of the given set of words.
Note: use 64-bit signed integer type (int64 in Pascal, long long in C/C++)

examples

|||||
|-|-|-|
|input | input | input|
|2 | 4 | 14|
|lopta | lova | branimir|
|kugla | novac | vladimir|
| | aron | tom|
|output | sunce | kruz|
|0 | | bred|
| | output | pit|
|| 3 | zemlja|
|| | nije|
|| | ravna|
| | | ploca|
|| | ko|
| | | je|
| | | zapalio|
| | | zito|
| | | output|
| | | 48|

------------------------------------------------------.

题目大意：
就是给你一堆字符串，问你有多少对满足，正序时字典序a>b且逆序时字典序b>a的对数

解题思路:
很容易想到先对字符串按照字典序排序一遍,然后问题就能简化为仅仅判断逆序时字典序stri<strj,i<jstr_i<str_j,i<j的对数就好了.
但是对于如何统计这个没有什么好的思路,最后看了WannaFlyUnion的题解才想到用Trie就好了…(不会字符串的渣渣根本没有向这方面想)

然后才惊人的发现,Trie树居然也可以用静态数组来实现,…

然后学习了… 这样就成了简单的Trie入门题了…

以下借（chao）鉴(xi)WannaflyUnion的题解代码

----------------------------------------------------------------------------------.

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
# include <bits/stdc++.h>

using namespace std;

# define INF        (~(1<<31))
# define INFLL      (~(1ll<<63))
# define pb         push_back
# define mp         make_pair
# define abs(a)     ((a)>0?(a):-(a))
# define lalal      puts("*******");
# define s1(x)      scanf("%d",&x)
# define Rep(a,b,c) for(int a=(b);a<=(c);a++)
# define Per(a,b,c) for(int a=(b);a>=(c);a--)
# define no         puts("NO")

typedef long long int LL ;
typedef unsigned long long int uLL ;

const int MOD = 1e9+7;
const int N = 1000000*2+5;
const double eps = 1e-6;
const double PI = acos(-1.0);
void fre(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
}
/*************************************************/
int a[N][27],f[N],cnt;
string str[N];

/**
DAT（DFA）
就是索引而已了
cnt 来记录接下来的索引，仔细想一想就和模拟数组差不多的想法
然后记录数据用的是另一个数组，
a[k^n ? ][位数]  f[数据的范围]
*/

inline void insert(string str){
    int len = str.length(),now = 0;
    for(int i = len - 1; i >= 0; --i){
        if(!a[now][str[i]-'a'])
            a[now][str[i]-'a'] = ++cnt;
        now = a[now][str[i]-'a'];
        ++f[now];
    }
}
/**
统计就是
以abc来看
分别统计的就是
b**
c***
.
.
.

ac**
ad**
.
.

abd**
abe**
.
.

abca**
abcb**

*/

int calc(string str){
    int len = str.length(),now = 0,ans = 0;
    for(int i = len - 1 ;i >= 0;--i){
        for(int j = str[i]-'a'+1;j<26;++j)
            ans += f[a[now][j]];
        now = a[now][str[i]-'a'];
    }
    for(int i = 0;i<26;++i) ans += f[a[now][i]];
    return ans ;
}

int main(){
    int n,ind;
    LL ans;
    while(~s1(n)){
        Rep(i,1,n) cin >> str[i];
        sort(str+1,str+1+n);

        Rep(i,1,n)    cout<<str[i]<<endl;

        memset(a,0,sizeof(a));
        memset(f,0,sizeof(f));

        ans = 0ll,cnt = 0;
        Rep(i,1,n)   insert(str[i]),ans+=calc(str[i]);

        printf("%lld\n",ans);
    }
    return 0;
}