[luogu3294][背单词]

题目链接

题意

读完题目就一个感受：这出题人tm不会说人话吗。真的感觉这个题理解题意比想出正解更难。

其实题目的意思就是，给出一些单词，给这些单词编个号，然后要求其他的单词中是这个单词后缀的词都在这个词的前面。每个单词的贡献是当前单词的标号减去他的后缀中标号最大的那个的标号。

希望我能表达明白吧233

思路

因为后缀不好考虑，所以先把字符串倒过来，就都变成了前缀

然后把这些字符串在全都挂到trie树上，每个字符串的结尾打的标记是这个字符串的标号。

删去trie树中的虚点(没有打标记的点)。就可以得到一棵新的树，然后发现，每个字符串的前缀肯定都是他的祖先。然后要求给这些节点编号，是的每个节点的祖先的编号都比这个节点的编号小。并且使得所有节点的编号与他父亲的编号的差值和最小。

用贪心的思想，先给子树大小最小的那棵子树编号。显然这样贪心是对的。

代码

/*
* @author: wxyww
* @date:   2018-12-17 11:02:04
* @last modified time: 2018-12-17 16:59:58
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<ctime>
#include<bitset>
using namespace std;
typedef long long ll;
const int n  = 110000;
ll read() {
   ll x=0,f=1;char c=getchar();
   while(c<'0'||c>'9') {
      if(c=='-') f=-1;
      c=getchar();
   }
   while(c>='0'&&c<='9') {
      x=x*10+c-'0';
      c=getchar();
   }
   return x*f;
}
vector<int>e[n];
int trie[n * 5][30];
char s[n * 5];
int siz[n * 5],tot,bz[n * 5];
void insert(int k) {
   int len = strlen(s + 1);
   int now = 0;
   for(int i = len;i >= 1;--i) {
      if(!trie[now][s[i] - 'a']) trie[now][s[i] - 'a'] = ++tot;
      now = trie[now][s[i] - 'a'];
   }
   bz[now] = k;
}
void dfs1(int u,int fa) {
   if(bz[u]) e[fa].push_back(bz[u]);
   for(int i = 0;i < 26;++i) {
      if(!trie[u][i]) continue;
      if(bz[u]) dfs1(trie[u][i],bz[u]);
      else dfs1(trie[u][i],fa);
   }
}
bool cmp(int x,int y) {
   return siz[x] < siz[y];
}
void dfs2(int u) {
   int k = e[u].size();
   siz[u] = 1;
   for(int i = 0;i < k;++i) {
      int v = e[u][i];
      dfs2(v);
      siz[u] += siz[v]; 
   }
   sort(e[u].begin(),e[u].end(),cmp);
}
int now,bh[n];
ll ans;
void solve(int u,int fa) {
   ans += now - fa;fa = now ++;
   int k = e[u].size();
   for(int i = 0;i < k;++i) {
      int v = e[u][i];
      solve(v,fa);
   }
}

int main() {
   int n = read();
   for(int i = 1;i <= n;++i) {
      scanf("%s",s + 1);    
      insert(i);
   }
   dfs1(0,0);
   dfs2(0);
   solve(0,0);
   cout<<ans;
   return 0;
}

一言

书足以记名姓而已。剑一人敌，不足学，学万人敌。