题解 P3294 【[SCOI2016]背单词】

· · 题解

题意解释（本题最重要的部分）

本篇题解过于详细，适合初学者食用

给你一些字符串，让你对其进行排列，使得按以下规则花费最少(然而题意真的不清楚，很容易就让人以为字符串的顺序是排好的)

（x为字符串在自行排定的序列中的位置，当前字符串为a)
1.如果a存在后缀且a的后缀在a之后，花费+=n^2
2.如果a不存在后缀则花费+=x
3.设y为a之前离其最近的是a的后缀的字符串的位置，a存在后缀且a的后缀在a之前，则花费+=x-y

经过转化题意就比较显然了，但是我们如果仔细读题我们发现1，2规则其实完全没有必要。

规则1我们只要把a的后缀放在a之前就好了，这样肯定优于放在a的后面因为x-y的值最大只能是n-1显然优于n^2

规则2我们发现其实就是规则三中y=0的特殊情况，直接当规则3来处理就好

大体思路

看到后缀我们显然首先想到的是后缀数组，但是本蒟蒻太弱了不会怎么办？？？（而且本蒟蒻也不知道本题能不能用后缀数组）

我们把字符串翻个顺序就会发现后缀其实就是前缀，所以我们可以翻转字符串，处理前缀。

而处理前缀我们首先就会想到trie字典树，座椅本题我们采用建立trie字典树的做法。

看懂题目的规则之后我们发现可以贪心的求解此题，只要让字符串的后缀与字符串之间所隔的字符串数目最小即可

所以第一步我们建立一颗trie树

第二步我们发现一个字符串有可能有很多后缀，所以我们需要判重，这里使用并查集
+ 优于字符串的后缀与字符串之间存在有向的关系，便建立一张有向图。x->y代表x是y的后缀

因为要保证字符串与字符串的后缀之间距离最小所以贪心的选取以x为根的最小的子树

（使用vector在算出每棵子树大小后进行排序即可）
最后按照规则求和

求和时使用dfs序的正确性的证明

经WQY查阅无误^_^

如果你有认真看我的或其他人的题解，你可以发现我们在最后求和的时候是按照dfs序的。那么为什么？（我不会）

所以我在夏令营时找了wqy神仙请教。

考虑建出一棵树之后，对于构建的任意合法的序列，都满足i的父亲一定在i之前出现，i的孩子们都一定在i之后出现

先尝试证明dfs序一定最优，对于以同一深度的节点为根的子树，在一颗中找一个叶子节点j,在另一颗里找一个根节点i(当前序列中j所在的子树的根在i之前出现

假设j<i的时候代价最小，尝试将j放在i的后面，此时i<j。那么我们发现如果j放在i与i的孩子们之间，i的孩子们和i的距离都会加1，所以总代价会增加，而j和j的父亲的距离一定也会增加，所以总代价也会增加

所以对于j所在子树的根比i在序列中出现的早的情况，j<i的情况是最优的

那么每个子树形成了一段连续的区间，对于每个节点进行调整，最后我们发现形成了一个dfs序(有时别的序列也会和dfs序列一样优秀，但是此处证明的是dfs序列是最优解之一，不是唯一解

接下来再证明先遍历子树小的更优秀。

WQY:
月明风清 2019.11.4 21:28:04
因为你所有的size排序之后

月明风清 2019.11.4 21:28:17
第i个根节点的贡献是前面所有树的size之和
所以要排序

综上所述，当我们进行dfs序且按子树大小排序时，求出代价即为最优。

Q.E.D

感谢wqy，给了我很大的帮助wucstdio

CODE

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define N 510050
#define M 100050
#define ll long long
ll ans=0;
char x[N];
int n,cnt,bo[N],tot=1,trie[5000050][27],fa[N],id[N],son[N],num;
vector<int>tu[N];
int read()
{
    int s=0,p=1;
    char ch=getchar();
    while(ch<'0' || ch>'9')
    {
        if(ch=='-')p=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        s=(s<<1)+(s<<3)+(ch^48);
        ch=getchar();
    }
    return s*p;
}
int find(int x)
{
    if(fa[x]==x)return fa[x];
    else return fa[x]=find(fa[x]);
}
void insert(char *s,int bh)
{
    int l=strlen(s);
    int u=1;
    for(int i=l-1;i>=0;i--)
    {
        int c=s[i]-'a';
        if(!trie[u][c])trie[u][c]=++tot;
        u=trie[u][c];
    }
    bo[u]=bh;
}
void make(int x)
{
    for(int i=0;i<26;i++)
    {
        int v=trie[x][i];
        if(v)
        {
            if(!bo[v])
            {
                fa[v]=find(x);
            }
            else
            {
                tu[bo[find(x)]].push_back(bo[v]);
            }
            make(v);
        }
    }
}
int cmp(int x,int y)
{
    return son[x]<son[y];
}
void sonsum(int x)
{
    son[x]=1;
    for(vector<int> :: iterator it=tu[x].begin();it!=tu[x].end();it++)
    {
        int v=*it;
        sonsum(v);
        son[x]+=son[v];
    }
    sort(tu[x].begin(),tu[x].end(),cmp);
}
void dfs(int x)
{
    id[x]=num++;
    for(vector<int> :: iterator it=tu[x].begin();it!=tu[x].end();it++)
    {
        int v=*it;
        ans+=num-id[x];
        dfs(v);
    }
}
void dfss(int x)
{
    for(vector<int> :: iterator it=tu[x].begin();it!=tu[x].end();it++)
    {
        int v=*it;
        cout<<v<<endl;
        dfss(v);
    }
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        scanf("%s",x);
        insert(x,i);
    }
    for(int i=1;i<=tot;i++)fa[i]=i;
    make(1); sonsum(0);dfs(0);
    printf("%lld",ans);
    return 0;
}

并查集去重的思路来源于此篇blog