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)


相关推荐

  • python自行实现支付宝证书签名&验签全流程[通俗易懂]

    python自行实现支付宝证书签名&验签全流程[通俗易懂]支付宝Pythonsdk只有密钥签名,没有证书签名,下面是本人自行实现签名全流程证书签名需要新加alipay_root_cert_sn和app_cert_sn两个参数,这两个参数需要解析支付宝根证书(alipay_root_cert_sn)和应用公钥证书(appCerPublicKey_”app_id”.crt)得到:defsn_string():root_file_li=open(alipayRootCert.crt’,’r’).read().split(‘\n\n’)

  • SVN安装与使用_刚安装ETC不能马上使用吗

    SVN安装与使用_刚安装ETC不能马上使用吗SVN(Subversion)是近年来崛起的版本管理工具,在当前的开源项目里(J2EE),几乎95%以上的项目都用到了SVN。Subversion项目的初衷是为了替换当年开源社区最为流行的版本控制软件CVS,在CVS的功能的基础上有很多的提升同时也能较好的解决CVS系统的一些不足。svn是基于客户/服务器模式,所以分客户端和服务器端,作为开发人员,自己的电脑上只需要安装客户端,又…

  • C语言输出有颜色的字体

    C语言输出有颜色的字体先看下面的一段代码:#include<stdio.h>intmain(intargc,char**argv){printf(“\033[44;37;5mhelloworld\033[0m\n”);return0;}编译后运行上述代码,结果如下:可见,此时输出的字体和背景已经有了颜色。由上可知,在输出时候加上“\033[…

  • java删除数组中指定元素_java学习中如何删除数组中的指定元素「建议收藏」

    java删除数组中指定元素_java学习中如何删除数组中的指定元素「建议收藏」java的api中,并没有提供删除数组中元素的方法。虽然数组是一个对象,不过并没有提供add()remove()或查找元素的方法。这就是为什么类似ArrayList和HashSet受欢迎的原因。不过,我们要感谢ApacheCommonsUtils,我们可以使用这个库的ArrayUtils类来轻易的删除数组中的元素。不过有一点需要注意,数组是在大小是固定的,这意味这我们删除元素后,并不会减少数组的…

  • 用LM方法的matlab求解,matlab中LM算法「建议收藏」

    用LM方法的matlab求解,matlab中LM算法「建议收藏」symsabyxreal;f=a*exp(-b*x);Jsym=jacobian(f,[ab]);%拟合用数据。参见《数学试验》,p190,例2data_1=[0.250.511.523468];obs_1=[19.2118.1515.3614.1012.899.327.455.243.01];%2.LM算法%初始猜测sa0=10;b0=0.5…

  • 提交缺陷报告

    提交缺陷报告一、软件缺陷的判定1.什么是缺陷软件存在着不符合质量需求或违背软件用户、客户、企业意愿的问题,这就是软件缺陷(Defect),又叫“Bug(臭虫)”。2.软件缺陷的判定准则软件未达到产品说明书标明的功能;产品说明书简称为说明(spec)或产品说明(productspec),是软件开发小组的一个协定。它对开发的产品进行定义,给出产品的细节、如何做、做什么、不能做什么。这种协定从简单的口头说明到正式的书面文档有多种形式。软件出现了产品说明书指明不会出现的错误;如金融软件

发表回复

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

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