大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
Address
Solution
- 简化下题目,对于排在第 x x 个位置的串:
1.若存在该串的后缀排在该串后面,该串的代价为
n2
。
2.若该串没有后缀,代价为 x x 。
3.若该串的所有后缀都排在该串前面,记最靠近该串的后缀位置为
y
,代价为 x−y x − y 。 - 显然只要把所有串翻转,则后缀都变成了前缀,建出 Trie T r i e 树。
- 接下来把不是串结束位置的无关点去掉,建出一棵新树。
- 容易发现 1. 中代价远大于后两项,但只要按照新树的某个 DFS D F S 序排列就可以完全避免出现 1. 中情况。
- 则问题转化为求新树的所有父子在 DFS D F S 序中距离和的最小值。
- 我们有一个贪心策略:每遍历到一点,都按照子树大小从小到大往下 DFS D F S 。
- 因为越先遍历到的子树,就会对之后越多的点的 DFS D F S 序产生影响,因而要使先遍历到的子树大小尽量小。
- 时间复杂度 O(nlogn) 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;
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/159335.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...