学海泛舟

spoj KAOS - Kaos 题解

发表于 | 分类于 |

原题

传送门

题目大意

给定一些字符串，要求找出符合要求的(s1,s2)的对数。
1、按照字典序，s1>s2
2、按照字典序，s1翻转后小于s2翻转后（若s1=”abc”，则翻转后为”cba”）

分析

一个要求很好满足，将字符串排序后，那么排在s1前面的字符串都会和s1满足要求一，只要在其中找到满足要求二的即可。
我们很容易想到trie树，将排序后的字符串，翻转后插入字典树中，并一遍统计满足要求二的，就能得到答案。

参考代码

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
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
const int maxn=100000+10;
struct node{
	int next[26];
	int cnt;
	void init(){
		cnt=0;
		memset(next,0,sizeof next);
	}
}T[maxn*20];
int tot;
void insert(string s){
    reverse(s.begin(),s.end());
	int i=0,p=0;
	while(s[i]){
		int x=s[i]-'a';
		if(T[p].next[x]==0){
			T[tot].init();
			T[p].next[x]=tot++;
		}
		p=T[p].next[x];
		T[p].cnt++;
		i++;
	}
}
int getans(string s)
{
    reverse(s.begin(),s.end());
    int now=0,ans=0;
    int i=0;
    while(s[i])
    {
        int x=s[i]-'a';
        for(int j=x+1;j<26;++j)
        {
            ans+=T[T[now].next[j]].cnt;
        }
        now=T[now].next[x];
        i++;
    }
    for(int j=0;j<26;++j)
    {
        ans+=T[T[now].next[j]].cnt;
    }
    return ans;
}
string s[maxn];
int main(){
	int n;
	scanf("%d",&n);
	tot=1;
	for(int i=0;i<n;++i)
    {
        cin>>s[i];
    }
    sort(s,s+n);
    long long ans=0;
    T[0].init();
    for(int i=0;i<n;++i)
    {
        insert(s[i]);
        ans+=getans(s[i]);
    }
    printf("%lld\n",ans);
	return 0;
}