第十五届蓝桥杯省赛第二场C/C++B组D题【前缀总分】题解(AC)

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

暴力解法 O ( 26 n 5 ) O(26n^5) O(26n5)

枚举将第 i i i 个字符串的第 j j j 个字符改为 c c c 的所有方案,时间复杂度 O ( 26 n 2 ) O(26n^2) O(26n2),修改并计算总分, O ( n 3 ) O(n^3) O(n3)

暴力优化 O ( 26 n 3 log ⁡ n ) O(26n^3\log n) O(26n3logn)

我们可以使用字符串哈希来优化判断两个字符串是否相等。

另外,可以用二分来优化求两个字符串的最大前缀。

枚举所有方案的时间复杂度为 O ( 26 n 2 ) O(26n^2) O(26n2),处理修改以及计算总分的复杂度为 O ( n log ⁡ n ) O(n\log n) O(nlogn)

再优化 O ( 26 n 3 ) O(26n^3) O(26n3)

首先,我们依旧使用上述暴力解法中的枚举方式——所有将第 i i i 个字符串的第 j j j 个字符改为 k k k,时间复杂度 O ( 26 n 2 ) O(26n^2) O(26n2)

接下来我们考虑,如果用不大于 O ( n ) O(n) O(n) 的时间去完成计算一个枚举的分数。

将第 i i i 个字符串的第 j j j 个字符改为 k k k 时,所影响答案的只有 P ( s 1 , s i ) , P ( s 2 , s i ) , P ( s 3 , s i ) , … , P ( s n , s i ) P(s_1, s_i), P(s_2, s_i), P(s_3, s_i), \dots, P(s_n, s_i) P(s1,si),P(s2,si),P(s3,si),,P(sn,si)

所以我们可以计算出未修改时的总得分的 t o t tot tot,计算出未修改时第 i i i 个字符串对答案的贡献 g [ i ] g[i] g[i]。设修改之后第 i i i 个字符串对答案的贡献为 r e s res res,那么修改之后的答案即为 t o t − g [ i ] + r e s tot - g[i] + res totg[i]+res

那么接下来,我们要尝试处理计算,将第 i i i 个字符串的第 j j j 个字符改为 k k k 之后,第 i i i 个字符串对答案的贡献。

那么显而易见,我们需要计算修改之后的第 i i i 字符串与剩下 n − 1 n-1 n1 个字符串的最大前缀。

设其中一个字符串为 s u s_u su,计算修改之后的 s i s_i si 与修改之前,只有第 j j j 个字符被改变, j j j 左侧的字符,以及右侧的字符均为改变。

那么我们可以尝试比较修改前的 s i s_i si s u s_u su 0 0 0 开始的最大前缀长度 l e f t left left

  • l e f t < j − 1 left < j - 1 left<j1,那么 s i s_i si s u s_u su 的最大前缀长度即为 l e f t left left
  • l e f t ≥ j − 1 left \geq j - 1 leftj1,那么说明 s i s_i si s u s_u su 的前 j − 1 j - 1 j1 个字符相等,此时我们需要判断修改之后的第 j j j 个字符是否相等:
    • 若第 j j j 个字符相等,则 s i s_i si s u s_u su 的最大前缀即为 l e f t + 1 + left + 1 + left+1+ s i s_i si s j s_j sj 的第 j + 1 j + 1 j+1 个字符开始的最大前缀)。
    • 若第 j j j 个字符不相等,则 s i s_i si s u s_u su 的最大前缀即为 l e f t left left

上述分析中,我们多次需要用到第 i i i 个字符串与第 j j j 个字符串从 k k k 开始的最大前缀。

考虑动态规划: f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k] 表示第 i i i 个字符串与第 j j j 个字符串从 k k k 开始的最大前缀长度。

考虑动态转移:

  • s [ i ] [ k ] = s [ j ] [ k ] s[i][k] = s[j][k] s[i][k]=s[j][k],则 f [ i ] [ j ] [ k ] = f [ i ] [ j ] [ k + 1 ] + 1 f[i][j][k] = f[i][j][k + 1] + 1 f[i][j][k]=f[i][j][k+1]+1
  • s [ i ] [ k ] ≠ s [ j ] [ k ] s[i][k] \neq s[j][k] s[i][k]=s[j][k],则 f [ i ] [ j ] [ k ] = 0 f[i][j][k] = 0 f[i][j][k]=0

由于计算 f [ i ] [ j ] [ k + 1 ] f[i][j][k + 1] f[i][j][k+1] 时,需要用到 f [ i ] [ j ] [ k + 1 ] f[i][j][k + 1] f[i][j][k+1],故预处理 f f f 数组时需要倒序处理。

暴力优化 O ( 26 n 3 log ⁡ n ) O(26n^3\log n) O(26n3logn)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>using namespace std;const int N = 2e2 + 10, P = 131;typedef unsigned long long ULL;int n;
string str[N];
ULL f[N][N], p[N];
int g[N];
int tot;ULL query(int u, int l, int r)
{return f[u][r] - f[u][l - 1] * p[r - l + 1];
}int calc(int u, bool flag)
{int res = 0;for (int i = 1; i <= n; ++ i )if (i != u){int l = 1, r = min(str[u].size() - 1, str[i].size() - 1);while (l < r){int mid = l + r + 1 >> 1;if (query(i, 1, mid) == query(u, 1, mid))l = mid;elser = mid - 1;}if (query(i, 1, l) == query(u, 1, l))res += l;}if (flag){g[u] = res;tot += res;}return res;
}int modify(int u, int k, int c)
{char t = str[u][k];str[u][k] = 'a' + c;for (int i = 1; i < str[u].size(); ++ i )f[u][i] = f[u][i - 1] * P + str[u][i];int res = tot - g[u] * 2 + calc(u, false) * 2;str[u][k] = t;for (int i = 1; i < str[u].size(); ++ i )f[u][i] = f[u][i - 1] * P + str[u][i];return res / 2;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n;for (int i = 1; i <= n; ++ i ){cin >> str[i];str[i] = ' ' + str[i];}p[0] = 1;for (int i = 1; i < N; ++ i )p[i] = p[i - 1] * P;for (int i = 1; i <= n; ++ i )for (int j = 1; j < str[i].size(); ++ j )f[i][j] = f[i][j - 1] * P + str[i][j];for (int i = 1; i <= n; ++ i )calc(i, true);int res = 0;for (int i = 1; i <= n; ++ i )for (int j = 1; j < str[i].size(); ++ j )for (int k = 0; k < 26; ++ k )res = max(res, modify(i, j, k));cout << res << endl;return 0;
}

再优化 O ( 26 n 3 ) O(26n^3) O(26n3)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>using namespace std;const int N = 2e2 + 10;int n;
string str[N];
int g[N];
int tot;
int f[N][N][N];     //  [i, j, k] 第i个字符串和 第j个字符串 k个字符起最大连续数量void init()
{for (int i = 1; i <= n; ++ i )for (int j = i + 1; j <= n; ++ j ){int mn = min(str[i].size(), str[j].size());for (int k = mn - 1; k >= 0; -- k )if (str[i][k] == str[j][k])f[i][j][k] = f[j][i][k] = f[i][j][k + 1] + 1;}for (int i = 1; i <= n; ++ i ){for (int j = 1; j <= n; ++ j )g[i] += f[i][j][0];tot += g[i];}tot /= 2;
}int modify(int u, int k, int c)
{int res = 0;for (int i = 1; i <= n; ++ i )if (i != u){int left = min(f[u][i][0], k);res += left;if (left == k && str[i].size() > k && str[i][k] - 'a' == c){res ++;res += f[u][i][k + 1];}}return tot - g[u] + res;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n;for (int i = 1; i <= n; ++ i )cin >> str[i];init();int res = 0;for (int i = 1; i <= n; ++ i )for (int j = 0; j < str[i].size(); ++ j )for (int k = 0; k < 26; ++ k )res = max(res, modify(i, j, k));cout << res << endl;return 0;
}

【在线测评】

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Pytorch】(十四)C++ 加载TorchScript 模型

文章目录 &#xff08;十四&#xff09;C 加载TorchScript 模型Step 1: 将PyTorch模型转换为TorchScriptStep 2: 将TorchScript序列化为文件Step 3: C程序中加载TorchScript模型Step 4: C程序中运行TorchScript模型 【Pytorch】&#xff08;十三&#xff09;PyTorch模型部署: T…

什么是langchain

概念 LangChain 是一个用于开发由语言模型驱动的应用程序的框架。他主要拥有 2 个能力&#xff1a; -可以将 LLM 模型&#xff08;大规模语言模型&#xff09;与外部数据源进行连接 -允许与 LLM 模型进行交互基础功能 支持多种模型接口&#xff0c;比如 OpenAI、Hugging Fac…

Delta模拟器:iOS上的复古游戏天堂

Delta模拟器&#xff1a;iOS上的复古游戏天堂 在数字时代&#xff0c;我们有时会怀念起那些早期的电子游戏&#xff0c;它们简单、纯粹&#xff0c;带给我们无尽的乐趣。虽然现在的游戏在画质和玩法上都有了巨大的提升&#xff0c;但那种复古的感觉却始终无法替代。幸运的是&a…

Ceph 分布式文件系统 搭建及使用

一、Ceph 介绍 在当今数据爆炸式增长的时代&#xff0c;企业对于可靠、可扩展的存储解决方案的需求日益迫切。Ceph 作为一种开源的、可伸缩的分布式存储解决方案&#xff0c;正逐渐成为企业级存储领域的热门选择。Ceph是一种由Radicalbit公司开发的开源分布式存储系统&#xf…

公网IP地址如何申请SSL证书?有免费的IP ssl吗?

如果用户没有域名或只有公网IP地址或者不方便使用域名&#xff0c;IP地址ssl证书这一特殊的证书可以为IP地址实现HTTPS的安全保护&#xff0c;提高网站数据传输的安全性。 IP地址申请SSL证书的基本步骤 IP ssl证书下载---注册填写230916https://www.joyssl.com/certificate/sel…

MySQL——运维

日志 错误日志 错误日志是 MySQL 中最重要的日志之一&#xff0c;它记录了当 mysqld 启动和停止时&#xff0c;以及服务器在运行过程中发生任何严重错误时的相关信息。当数据库出现任何故障导致无法正常使用时&#xff0c;建议首先查看此日志。 查看日志位置&#xff1a; sho…

信息系统项目管理师0070:数据开发利用(5信息系统工程—5.2数据工程—5.2.4数据开发利用)

点击查看专栏目录 文章目录 5.2.4数据开发利用1.数据集成2.数据挖掘3.数据服务4.数据可视化5.信息检索5.2.4数据开发利用 数据只有得到充分的开发利用才能发挥出它的作用。通过数据集成、数据挖掘和数据服务(目录服务、查询服务、浏览和下载服务、数据分发服务)、数据可视化、信…

# 从浅入深 学习 SpringCloud 微服务架构(六)Feign(3)

从浅入深 学习 SpringCloud 微服务架构&#xff08;六&#xff09;Feign&#xff08;3&#xff09; 一、组件的使用方式总结 1、注册中心 1&#xff09; Eureka 搭建注册中心 引入依赖 spring-cloud-starter-netflix-eureka-server。 配置 EurekaServer。 通过 EnableEure…

安全AI未来 | C3安全大会 · 2024,数据驱动 AI原生

数字为时代变革注入动力&#xff0c;AI为重塑社会文明带来原力。数智浪潮中&#xff0c;我们见证着时代跃迁的巨变&#xff0c;面临着适变、应变、驭变的挑战。 数字驱动、AI原生。数字的流动不仅承载着信息&#xff0c;更将激活未来的无限价值&#xff1b;AI&#xff0c;不…

基于OpenCV的人脸签到系统

效果图 目录文件 camerathread.h 功能实现全写在.h里了 class CameraThread : public QThread {Q_OBJECT public:CameraThread(){//打开序号为0的摄像头m_cap.open(0);if (!m_cap.isOpened()) {qDebug() << "Error: Cannot open camera";}//判断是否有文件,人脸…

restful请求风格的增删改查-----查询and添加

一、restful风格的介绍 restful也称之为REST ( Representational State Transfer )&#xff0c;可以将它理解为一种软件架构风格或设计风格&#xff0c;而不是一个标准。简单来说&#xff0c;restful风格就是把请求参数变成请求路径的一种风格。例如&#xff0c;传统的URL请求…

PHP项目搭建与启动

1、拉取项目 2、安装phpstudy 下载地址&#xff1a; Windows版phpstudy下载 - 小皮面板(phpstudy) (xp.cn) 软件安装&#xff1a; Apache2.4.39、Nginx1.15.11、MySQL8.0.12、 composer2.5.8 添加伪静态 将下面代码写入到伪静态配置文本域框内&#xff1a; location ~* (ru…

多线程(安全 同步 线程池)

线程安全问题 多线程给我们的程序带来了很大性能上的提升&#xff0c;但是也可能引发线程安全问题线程安全问题指的是当多个线程同时操作同一个共享资源的时候&#xff0c;可能会出现的操作结果不符预期问题 取钱的线程安全问题 线程安全问题出现的原因&#xff1f; 存在多线…

创新科技赋能旅游服务:智慧文旅引领旅游发展新篇章,智能体验助力产业转型升级

随着科技的飞速发展和人们生活水平的提高&#xff0c;旅游业正迎来前所未有的发展机遇。创新科技在旅游服务领域的广泛应用&#xff0c;不仅提升了旅游体验的品质&#xff0c;也为旅游产业的转型升级注入了新的动力。智慧文旅作为旅游业与信息技术深度融合的产物&#xff0c;正…

matlab新手快速上手5(蚁群算法)

本文根据一个较为简单的蚁群算法框架详细分析蚁群算法的实现过程&#xff0c;对matlab新手友好&#xff0c;源码在文末给出。 蚁群算法简介&#xff1a; 蚁群算法是一种启发式优化算法&#xff0c;灵感来源于观察蚂蚁寻找食物的行为。在这个算法中&#xff0c;解决方案被看作是…

如何利用交易形态的失败进行现货黄金?

进行现货黄金理财&#xff0c;除了需要投资者对黄金投资有热情之外&#xff0c;有方法也是很重要的&#xff0c;光有热情而没有技术&#xff0c;我们的资金很可能会成为其他人的囊中之物。但如果有了现货黄金理财的技术&#xff0c;情况就可能扭转过来。下面我们就从买入的角度…

vue2实现字节流byte[]数组的图片预览

项目使用vantui框架&#xff0c;后端返回图片的字节流byte[]数组&#xff0c;在移动端实现预览&#xff0c;实现代码如下&#xff1a; <template><!-- 附件预览 --><div class"file-preview-wrap"><van-overlay :show"show"><…

【draw.io的使用心得介绍】

&#x1f308;个人主页: 程序员不想敲代码啊 &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共…

14.MMD导入Blender及贴图步骤

MMD导出.abc文件 在MMD十周年桥版本导入一个人物模型&#xff0c;这里导入仆人 注意MMD的路径不能有中文 点击上面的MMDBridge 设定 第一个选择blender by 第二个选择实行 这里是选择帧数范围和帧率 帧率一定要是30&#xff0c;不然后面可能会出问题 点击文件导出视频…

机器学习 -- 分类问题

场景 探讨了一个回归任务——预测住房价格&#xff0c;用到了线性回归、决策树以及随机森林等各种算法。本次中我们将把注意力转向分类系统。我们曾经对MNIST进行了分类任务&#xff0c;这次我们重新回到这里&#xff0c;细致的再来一次。 开始 获取数据 Scikit-Learn提供了…