题解 P3294 【[SCOI2016]背单词】

· · 题解

个人认为图片是最好理解的，因此本题解将按图说话

题意（已用贪心思路简化）

给定n个单词s_i，请重排序列，使每个单词的存在的后缀都在前面

设s_j为离s_i最近的后缀字符串

定义a_i=i-j

ans=min(\sum a_i)

题解

后缀显然没有前缀来的容易处理，所以自然想到翻转每个单词，建出trie树

下面是个例子：

6
a
ca
ea
gda
hda
ifb

1. 建出trie树(红点是颠倒后每个单词的末尾，注意根也是）：

    void ins(char *s){
        int x=0;
        for(int i=0;s[i];i++){
            if(!a[x].nt[s[i]-'a']) a[x].nt[s[i]-'a']=++cnt;
            x=a[x].nt[s[i]-'a'];
        }
        a[x].tag=1; //tag==1说明是红点
    }

2. 重构树

跳过白点，保留红点（白点无用，可以忽略）

    void doit(int x){
        if(a[x].tag&&x){
            g[last[x]].push_back(x); //g[x][]存重构树中点x的儿子们
            last[x]=x; //last[x]是原树里x节点上方离它最近的红点（包括自己）
        }
        for(int i=0;i<26;i++) if(a[x].nt[i]){
            last[a[x].nt[i]]=last[x];
            doit(a[x].nt[i]);
        }
    }

3. dfs遍历重构树，并将直接祖先相同的子树按节点数从小到大排序

inline bool cmp(const int &x,const int &y){
    return sz[x]<sz[y];
}
void dfs(int x){
    sz[x]=1; //sz[x]是以x为根的子树的大小
    for(int i=0;i<g[x].size();i++){
        dfs(g[x][i]);
        sz[x]+=sz[g[x][i]];
    }
    sort(g[x].begin(),g[x].end(),cmp);
}

4. 根据题意遍历重构树，用dfs序得到答案

void getans(int x){
    int dfn=cnt++; //dfn是父亲的dfs序，cnt是节点自己的dfs序
    for(int i=0;i<g[x].size();i++){
        ans+=cnt-dfn; //两者相减就是题意里的ai
        getans(g[x][i]);
    }
}

思路背后的理由

Q1. 为什么题意可以这样简化？

三条规则，规则一显然是可以被避免且没有后两种优的，规则二可以看做规则三的特殊情况，简单起见，只考虑规则三即可

Q2. 排序的正确性？

花费与最后一个填入的后缀有关,那么这个后缀的位置离当前位置越近越好,也就是应该有尽量少的单词夹在两个中间,所以我们应该选下属单词最少的那个进行拓展，而下属单词的多少就等价于重构树中子树的大小。

Q3. dfs序的正确性？

这里引用 @坐山客 的题解：

考虑重新建树之后，i节点的子树中的所有节点的后缀都是i

如果同一深度上有不止一棵子树，那么我们先在一棵上取出一个叶子节点j，再取出一个根节点i，我们发现如果j>i的话肯定不如i<j优秀

因为调整之后i的子树上所有节点对花费的贡献-=子树大小，j对花费的贡献+1，所以我们可以看到j>i的花费<=i>j的情况

最后我们经过所有的调整可以发现序列变成了dfs序

所以dfs序最优

完整代码

将以上各步骤代码合在一起就是：

tips. ANS要用long long!!!

#include <bits/stdc++.h>
using namespace std;
inline int read(int &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
inline void write(long long x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}
const int L=5.1e5+5;
struct node{ //trie树的每个节点
    int nt[26];
    bool tag;
};
long long ans;
int cnt,last[L],sz[L],n;
vector<int> g[L];
char s[L];
struct trie{ //trie及所需操作
    node a[L];
    int cnt;
    void ins(char *s){ //建树
        int x=0;
        for(int i=0;s[i];i++){
            if(!a[x].nt[s[i]-'a']) a[x].nt[s[i]-'a']=++cnt;
            x=a[x].nt[s[i]-'a'];
        }
        a[x].tag=1;
    }
    void doit(int x){ //重构树
        if(a[x].tag&&x){
            g[last[x]].push_back(x);
            last[x]=x;
        }
        for(int i=0;i<26;i++) if(a[x].nt[i]){
            last[a[x].nt[i]]=last[x];
            doit(a[x].nt[i]);
        }
    }
}tr;

inline bool cmp(const int &x,const int &y){
    return sz[x]<sz[y];
}
void dfs(int x){ //重排重构树
    sz[x]=1;
    for(int i=0;i<g[x].size();i++){
        dfs(g[x][i]);
        sz[x]+=sz[g[x][i]];
    }
    sort(g[x].begin(),g[x].end(),cmp);
}
void getans(int x){ //统计答案
    int dfn=cnt++;
    for(int i=0;i<g[x].size();i++){
        ans+=cnt-dfn;
        getans(g[x][i]);
    }
}
signed main(){
    read(n);
    for(int i=1;i<=n;i++){
        scanf("%s",s);
        reverse(s,s+strlen(s)); //反转单词
        tr.ins(s);
    }
    tr.a[0].tag=1; //根也是红点
    tr.doit(0);
    dfs(0);
    getans(0);
    write(ans);
}