牛客竞赛字符串专题 NC237664 Typewriter(SAM + 树上倍增 + 二分 + 线段树优化dp)

本题主要考察了如何用 SAM 求原串每个前缀对应的能与非后缀匹配的最长后缀,以及如何求 SAM 每个节点 right 集合的 min / max。很有价值的一道串串题。

在这里插入图片描述
在这里插入图片描述

题意:

你有一台打字机,你需要用它打出一段只由小写字母构成的文本S。
设某个时刻,你已经打出来的文本为 T,你可以执行两种操作:

  1. 花费 p 块钱,将T后面添加一个字符 ch,得到 T = T + ch。
  2. 花费 q 块钱,将 T 的一个 子串 S 复制一份,添加到 T 的后面,得到 T = T + S。
    问:为了得到 S,最少的花费是多少。

思路:

本题可以用 DP 解决,设 dp[i] 表示得到 S[1, i] 的最小代价。
考虑如何计算 dp[i]:

  1. 第一种操作带来的转移是:dp[i] ← dp[i - 1] + p。
  2. 第二种操作要求我们求最长的 S[1, i] 的后缀 S[i - x + 1, i],使得他在 S[1, i - x] 中也出现过,带来的转移是:dp[i] ← min(dp[i - x, …, i - 1]) + q。

Q1:对于每个前缀 S[1, i],如何预处理它最长的后缀 S[i - x+ 1, 1],使得他在 S[1, i - x] 中也出现过呢?

  • 我们可以结合在 NC237662 葫芦的考验之定位子串 这题中的思想进行思考:对于某一个前缀 S[1, i],他的所有后缀均在它所在节点与根相连的后缀链接上。因此,我们可以不断在后缀链接上找,当链上某个节点 u 代表的长度范围在 len[fa[u]] + 1 ~ len[u] 的这类子串中,存在一个长度为 anslen 的子串(注意这里是存在即可),它结束位置的最小值 mned[u] < i - anslen + 1 退出查找(贪心的找最深的节点,因为节点越深越能包含更长的子串)。还没完,我们还需要在这个节点上二分子串长度,寻找该前缀的最长后缀。

  • 显然上述查找节点的过程不能暴力地找,要使用树上倍增(dfs 预处理倍增表)。

Q2:第二步操作带来的状态转移需要求区间 min,怎么优化?

  • 线段树优化 dp。

时间复杂度:

构建 SAM:O(n)
两个预处理、线段树优化 dp:O(nlogn)

代码:

#include<bits/stdc++.h>

using namespace std;
const int N = 2e5 + 10, M = N << 1, mx = 20;
int ch[M][26], fa[M], len[M], np = 1, tot = 1;
vector<int> g[M];
//分别表示:节点代表子串最小结束位置,每个前缀对应的能与非后缀匹配的最长后缀
int mned[M], x[M];
char s[N];
int p, q;
int pa[M][mx];	//倍增表
struct node
{
	int l, r;
	long long mn;
} dp[N << 2];	//直接把线段树数组当做 dp 数组

void extend(int c)
{
	int p = np; np = ++tot;
	len[np] = len[p] + 1, mned[np] = len[np] - 1;
	while (p && !ch[p][c]) {
		ch[p][c] = np;
		p = fa[p];
	}
	if (!p) {
		fa[np] = 1;
	}
	else {
		int q = ch[p][c];
		if (len[q] == len[p] + 1) fa[np] = q;
		else {
			int nq = ++tot;
			len[nq] = len[p] + 1;
			fa[nq] = fa[q], fa[q] = fa[np] = nq;
			while (p && ch[p][c] == q) {
				ch[p][c] = nq;
				p = fa[p];
			}
			memcpy(ch[nq], ch[q], sizeof ch[q]);
		}
	}
}

void dfs(int u, int f)	//dfs 预处理树上倍增表
{
	pa[u][0] = f;
	for (int i = 1; i <= mx - 1; ++i) {
		pa[u][i] = pa[pa[u][i - 1]][i - 1];
	}
	for (auto son : g[u]) {
		dfs(son, u);
		mned[u] = min(mned[u], mned[son]);
	}
}

void init()	//预处理 x 数组
{
	int p = 1;
	for (int i = 0; s[i]; ++i)
	{
		p = ch[p][s[i] - 'a'];
		int tmp = p;
		for (int j = mx - 1; j >= 0; --j) {
			int ff = pa[tmp][j];
			int mnlen = len[fa[ff]] + 1;
			//倍增父节点不满足就一直跳,满足了立刻退出,找满足条件最深的节点
			if (mned[ff] >= i - mnlen + 1) {  
				tmp = ff;
			}
		}
		tmp = pa[tmp][0];	//再跳一格
		//首先不能是根,其次要满足条件,我们才在该节点二分答案
		if (p > 1 && mned[tmp] < i - (len[fa[tmp]] + 1) + 1)
		{
			int l = len[fa[tmp]] + 1, r = len[tmp];
			while (l < r) {
				int mid = l + r + 1 >> 1;
				if (mned[tmp] < i - mid + 1) l = mid;
				else r = mid - 1;
			}
			x[i] = r;
		}
		else x[i] = 0;	//如果是根或者不满足条件,也就是不存在对应后缀,置为 0
	}
}

void pushup(int u)
{
	dp[u].mn = min(dp[u << 1].mn, dp[u << 1 | 1].mn);
}

void build(int u, int l, int r)
{
	dp[u] = { l, r };
	if (l == r) {
		dp[u].mn = 0;
		return;
	}
	int mid = l + r >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int x, long long v)
{
	if (dp[u].l == x && dp[u].r == x) {
		dp[u].mn = v;
		return;
	}
	int mid = dp[u].l + dp[u].r >> 1;
	if (x <= mid) modify(u << 1, x, v);
	else modify(u << 1 | 1, x, v);
	pushup(u);
}

long long ask(int u, int l, int r)
{
	if (l <= dp[u].l && r >= dp[u].r) {
		return dp[u].mn;
	}
	int mid = dp[u].l + dp[u].r >> 1;
	long long ans = 1e18;	//由于是 long long 这里要尽可能大,建议直接上 1e18
	if (l <= mid) ans = min(ans, ask(u << 1, l, r));
	if (r > mid) ans = min(ans, ask(u << 1 | 1, l, r));
	return ans;
}

signed main()
{
	memset(mned, 0x3f, sizeof mned);	//这里很重要,首先要全初始化为 inf
	mned[0] = 0;	//然后节点 0 要初始化为 0
	scanf("%s%d%d", s, &p, &q);
	int n = strlen(s);
	for (int i = 0; i < n; ++i) {
		extend(s[i] - 'a');
	}
	for (int i = 2; i <= tot; ++i) {
		g[fa[i]].emplace_back(i);
	}
	dfs(1, 0);	//dfs 预处理树上倍增表
	init();	//预处理 x 数组
	build(1, 1, n), modify(1, 1, p);
	for (int i = 2; i <= n; ++i) {
		modify(1, i, ask(1, i - 1, i - 1) + p);
		if (x[i - 1]) {	//只有对应后缀存在才进行转移!
			long long tmp = min(ask(1, i, i), ask(1, i - x[i - 1], i - 1) + q);
			modify(1, i, tmp);
		}
	}
	printf("%lld\n", ask(1, n, n));

	return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/13347.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Linux基础—DHCP原理与配置

Linux基础—DHCP原理与配置 一、DHCP工作原理1.了解DHCP服务使用DHCP的优势DHCP的分配方式 2.DHCP的IP地白动获取工作原理: 二、配置DHCP服务器三、DHCP场景应用实验 一、DHCP工作原理 1.了解DHCP服务 DHCP(Dynamic HostConfiguration Protocol&#xff0c;动态主机配置协议) …

第四章 面向对象(OOP)

目录 一、编程思想 1.1. 面向对象 1.2. 面向过程 1.3.举例说明&#xff08;把大象装进冰箱&#xff09; 1.4.二者的联系与区别 1.5.面向对象的三个阶段 1.6.什么是类&#xff0c;什么是实例&#xff0c;二者的联系 二、面向对象三大特征 2.1 封装 2.2 继承 2.3 多态…

【C++11】智能指针

目录 一、异常层层嵌套执行流乱跳容易导致内存泄漏 二、使用智能指针解决上述问题 1、RAII 2、像指针一样 3、智能指针RAII运算符重载 三、C98的auto_ptr 四、C11的unique_ptr和shared_ptr 1、unique_ptr唯一指针 2、shared_ptr共享指针 2.1shared_ptr是否线程安全 …

不得不说的创建型模式-工厂方法模式

工厂方法模式是创建型模式之一&#xff0c;它定义了一个用于创建对象的接口&#xff0c;但将具体创建的过程延迟到子类中进行。换句话说&#xff0c;它提供了一种通过调用工厂方法来实例化对象的方法&#xff0c;而不是通过直接使用 new 关键字来实例化对象。 下面是一个使用 C…

浅理解JavaScript数组去重的方法(划重点),当面试官问如何实现数组去重时,你可以这样做...

文章目录 &#x1f4cb;前言&#x1f3af;什么是数组去重&#xff0c;运用场景是什么&#xff1f;&#x1f3af;常用的数组去重方法&#x1f9e9;使用 Set 对象&#x1f9e9;使用 Object&#xff08;对象、基于Hash哈希表&#xff09; 或 Map&#x1f9e9;使用 filter 方法与 i…

Smartbi电子表格软件架构与差异化特色

Smartbi电子表格软件选择与Excel结合&#xff0c;原因在于Excel一直被模仿&#xff0c;从未被超越。虽然市场上的报表软件很多&#xff0c;但存在太多的不完美。国外的产品功能复杂、难于学习&#xff08;控件方式&#xff09;&#xff0c;做不了中国式复杂格式的报表&#xff…

Python双向循环链表的操作

目录 一、双向循环链表 双向循环链表图 二、双向循环链表的操作 1、判断链表是否为空 2&#xff0c;链表长度 3&#xff0c;遍历整个链表 4&#xff0c;在链表头部添加元素 5、链表尾部添加元素 6&#xff0c;在指定位置插入元素 7&#xff0c;修改指定位置的元素 8&a…

VS Code 插件开发概览

VS Code 插件开发概览 前言 VS Code作为开发者的代码开发利器&#xff0c;越来越受开发者的喜爱。像我身边的前端&#xff0c;每天80%的开发工作都是在VS Code上完成的。随着人们对它的使用&#xff0c;不再满足简单的优雅&#xff0c;舒服写代码这一基本需求。有些人利用它进…

阿里ARouter 路由框架解析

一、简介 众所周知&#xff0c;在日常开发中&#xff0c;随着项目业务越来越复杂&#xff0c;项目中的代码量也越来越多&#xff0c;如果维护、扩展、解耦等成了一个非常头疼问题&#xff0c;随之孕育而生的诸如插件化、组件化、模块化等热门技术。 而其中组件化中一项的难点&…

深入理解Linux多线程

致前行的人&#xff1a; 昨日渐多&#xff0c;明日愈少&#xff0c;今日还在&#xff0c;不要为成功而努力&#xff0c;要为做一个有价值的人而努力。人生道路上充满了坎坷&#xff0c;谁也不可能一帆风顺。只有在最困难的时刻&#xff0c;才能体会到无助的含义。 目录 1.理解…

SpringBoot集成MyBatis-yml自动化配置原理详解

SpringBoot集成MyBatis-yml自动化配置原理详解 简介&#xff1a;spring boot整合mybatis开发web系统目前来说是市面上主流的框架&#xff0c;每个Java程序和springboot mybatis相处的时间可谓是比和自己女朋友相处的时间都多&#xff0c;但是springboot mybatis并没有得到你的真…

适用于 Windows 的 5 个最好的 PDF 转换器应用程序

由于稳定性、高分辨率、高安全性、易于传输等特点&#xff0c;PDF已经成为我们日常工作中最常用的格式。我们在享受PDF带来便利的同时&#xff0c;也发现PDF带来了一些不便&#xff0c;其中最大的问题就是PDF内容的编辑难度。同时&#xff0c;并不是所有的文件都是PDF格式的&am…

代码优化- 前端优化

常量折叠 基本思想&#xff1a;在编译期间计算表达式的值&#xff08;编译时静态计算&#xff09; 例如&#xff1a;a 3 5 > a 8&#xff0c;if (true && false) ... > if (false) 好处是&#xff1a;语法树的节点数量减少了&#xff0c;意味着编译器要维护…

Ubuntu上跑通PaddleOCR

书接上文。刚才说到我已经在NUC8里灌上了Windows Server 2019。接下来也顺利的启用了Hyper-V角色并装好了一台Ubuntu 22.04 LTS 的虚机。由于自从上回在树莓派上跑通了Paddle-Lite-Demo之后想再研究一下PaddleOCR但进展不顺&#xff0c;因此决定先不折腾了&#xff0c;还是从x6…

【论文写作】如何写科技论文?万能模板!!!(以IEEE会议论文为例)

0. 写在前面 常言道&#xff0c;科技论文犹如“八股文”&#xff0c;有固定的写作模式。本篇博客主要是针对工程方面的论文的结构以及写作链条的一些整理&#xff0c;并不是为了提高或者润色一篇论文的表达。基本上所有的论文&#xff0c;都需要先构思好一些点子&#xff0c;有…

一文搞懂Session和JWT登录认证

前言 目前在开发的小组结课项目中用到了JWT认证&#xff0c;简单分享一下&#xff0c;并看看与Session认证的异同。 登录认证&#xff08;Authentication&#xff09;的概念非常简单&#xff0c;就是通过一定手段对用户的身份进行确认。 我们都知道 HTTP 是无状态的&#xf…

强化学习技巧

此软件包处于维护模式&#xff0c;请使用Stable-Baselines3 (SB3)获取最新版本。您可以在 SB3 文档中找到迁移指南。 本节的目的是帮助您进行强化学习实验。它涵盖了有关 RL 的一般建议&#xff08;从哪里开始、选择哪种算法、如何评估算法等&#xff09;&#xff0c;以及使用自…

【Linux】System V 共享内存、消息队列、信号量

&#x1f34e;作者&#xff1a;阿润菜菜 &#x1f4d6;专栏&#xff1a;Linux系统编程 system V共享内存介绍 System V 共享内存是一种进程间通信的机制&#xff0c;它允许多个进程共享一块物理内存区域&#xff08;称为“段”&#xff09;。System V 共享内存的优点是效率高&…

OTG是什么意思?

OTG是什么意思&#xff1f; OTG是怎么样实现的&#xff1f; TYPE-C接口的手机如何实现同时充电OTG功能&#xff1f; OTG是什么意思&#xff1f; OTG是On-The-Go的缩写&#xff0c;是一项新兴技术&#xff0c;主要应用于不同的设备或移动设备间的联接&#xff0c;进行数据交…

基于遥感的自然生态环境检测——实验三:生态因子提取

实验三&#xff1a;生态因子提取 一、实验目标 生态因子生成&#xff1b;生态因子归一化&#xff1b;生态环境评价 二、实验内容 根据经过大气校正后的影像生产土地覆盖指数、土壤指数以及坡度等&#xff0c;对土地覆盖指数、土壤指数以及坡度进行密度分割归一化&#xff1…
最新文章