BZOJ4567 [SCOI2016]背单词

全栈程序员-站长 • 2022年7月26日下午2:36 • 未分类 • 阅读 12

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

Address

BZOJ4567 洛谷P3294

Solution

简化下题目，对于排在第 $x$ 个位置的串：
1.若存在该串的后缀排在该串后面，该串的代价为 $n^2$ 。
2.若该串没有后缀，代价为 $x$ 。
3.若该串的所有后缀都排在该串前面，记最靠近该串的后缀位置为 $y$ ，代价为 $x - y$ 。
显然只要把所有串翻转，则后缀都变成了前缀，建出 $Trie$ 树。
接下来把不是串结束位置的无关点去掉，建出一棵新树。
容易发现 1. 中代价远大于后两项，但只要按照新树的某个 $DFS$ 序排列就可以完全避免出现 1. 中情况。
则问题转化为求新树的所有父子在 $DFS$ 序中距离和的最小值。
我们有一个贪心策略：每遍历到一点，都按照子树大小从小到大往下 $DFS$ 。
因为越先遍历到的子树，就会对之后越多的点的 $DFS$ 序产生影响，因而要使先遍历到的子树大小尽量小。
时间复杂度 $O(n \log n)$ 。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <cstdlib>

using namespace std;

typedef long long ll;
const int N = 51e4 + 5, M = 1e5 + 5;
int n, T = 1, m, tis; ll Ans;
int G[N][27], a[M], fa[N], sze[N], dfn[N];  
bool vis[N]; char s[N];

struct Edge
{
    int to; Edge *nxt;
}p[M], *lst[N], *P = p;

inline void Link(int x, int y)
{
    (++P)->nxt = lst[x]; lst[x] = P; P->to = y; fa[y] = x;
} 

inline void Dfs1(int x, int fa, int lst)
{
    for (int i = 0; i < 26; ++i)
    {
        int y = G[x][i];
        if (!y) continue;
        if (vis[y]) Link(lst, y), Dfs1(y, x, y);
            else Dfs1(y, x, lst);
    }
}

inline void Dfs2(int x)
{
    sze[x] = 1; int y;
    for (Edge *e = lst[x]; e; e = e->nxt)
        Dfs2(y = e->to), sze[x] += sze[y];
}

inline bool cmp(const int &x, const int &y) {
  
  return sze[x] < sze[y];}
inline void Dfs3(int x)
{
    dfn[x] = ++tis; int lm = m + 1;
    for (Edge *e = lst[x]; e; e = e->nxt)   
        a[++m] = e->to;
    int rm = m;
    sort(a + lm, a + rm + 1, cmp);
    for (int i = lm; i <= rm; ++i) Dfs3(a[i]);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) 
    {
        scanf("%s", s + 1); 
        int len = strlen(s + 1), x = 1;
        for (int j = 1, jm = len >> 1; j <= jm; ++j)
            swap(s[j], s[len - j + 1]); 
        for (int j = 1; j <= len; ++j)
        {
            int y = s[j] - 'a';
            if (!G[x][y]) G[x][y] = ++T;
            x = G[x][y];
        }
        vis[x] = true;
    }
    Dfs1(1, 0, 1); Dfs2(1); Dfs3(1);
    for (int i = 1; i <= T; ++i)
        if (fa[i]) Ans += dfn[i] - dfn[fa[i]]; 
    cout << Ans << endl;
}