BZOJ4567 [SCOI2016]背单词

BZOJ4567 [SCOI2016]背单词AddressBZOJ4567洛谷P3294Solution简化下题目,对于排在第xxx个位置的串:1.若存在该串的后缀排在该串后面,该串的代价为n2n2n^2。2.若该串没有后缀,代价为xxx。3.若该串的所有后缀都排在该串前面,记最靠近该串的后缀位置为yyy,代价为x−yx−yx-y。显然只要把所有串翻转,则后缀都变成了前缀,建出Trie…

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

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

Address


Solution

  • 简化下题目,对于排在第 x x 个位置的串:
    1.若存在该串的后缀排在该串后面,该串的代价为
    n2



    n


    2



    2.若该串没有后缀,代价为 x x
    3.若该串的所有后缀都排在该串前面,记最靠近该串的后缀位置为
    y


    y

    ,代价为 xy 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账号...

(0)


相关推荐

  • nginx自动重启_nginx无法启动

    nginx自动重启_nginx无法启动http://blog.csdn.net/zqinghai/article/details/71125045ps-ef|grepnginx平滑重启命令:kill-HUP住进称号或进程号文件路径或者使用/usr/nginx/sbin/nginx-sreload注意,修改了配置文件后最好先检查一下修改过的配置文件是否正确,以免重启后Nginx出现错误影响服务器稳定运行。判断Nginx配置…

  • idea激活码2021【2021.8最新】

    (idea激活码2021)本文适用于JetBrains家族所有ide,包括IntelliJidea,phpstorm,webstorm,pycharm,datagrip等。https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~B…

  • pycharm配置pyqt5_python pyqt5教程

    pycharm配置pyqt5_python pyqt5教程pycharm配置PyQt5说明打开配置的位置配置QtDesigner配置PyUIC配置PyRCC说明Program目录:此处直接用的虚拟环境下的文件,也可用安装目录下的文件打开配置的位置File-SettingsTools-ExternalTools-点击+配置QtDesignerProgram:D:\ProgramFiles\Python\virtualenvs\…

  • 51单片机按键控制步进电机加减速及正反转

    51单片机按键控制步进电机加减速及正反转之前尝试用单片机控制42步进电机正反转,电机连接导轨实现滑台前进后退,在这里分享一下测试程序及接线图,程序部分参考网上找到的,已经实际测试过,可以实现控制功能。所用硬件:步进电机及驱动器、STC89C52单片机、直流电源1、硬件连接图注意:上图为共阳极接法,实际连接参考总体线路连接。 驱动器信号端定义:PUL+:脉冲信号输入正。(C…

  • 焦点科技怎么老是招人_选错对焦点,错失好照片,你了解相机的对焦吗?

    焦点科技怎么老是招人_选错对焦点,错失好照片,你了解相机的对焦吗?对焦一直是衡量相机的性能的重要参数,在很长的一段时间里,我们因为相机的对焦系统不够强大,而习惯的单点手动设置对焦。而近几年微单相机的对焦快速发展,眼部自动对焦已经比较成熟,而我们的习惯也应该发生改变……选错对焦点,错失好照片多好的构图,妹子笑的多甜,然而就是因为焦点没有对准,成功的变成一张废片。很多人和我抱怨过,什么镜头跑焦,机身跑焦,可是你们有没有从自身找过原因,当真找到正确的焦点,准确合…

  • J2EE架构师之路「建议收藏」

    J2EE架构师之路「建议收藏」不经意的回首,工作进入第五个年头了,发现走过了从Java程序员到J2EE架构师的历程。发现电脑上安装了各种各样的J2EE工具:JBuilder,WSAD,Eclipse,Rose,Together,Weblogic,Jtest,Optimizator,Mysql…发现电脑上保存了各种各样的OpenSource项目:Tomcat,JBoss,Ant,Hibernate,Spr

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号