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

news/2024/5/19 14:49:25

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

暴力解法 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.mrgr.cn/p/57604644

相关文章

openGauss 函数

函数 openGauss常用的函数如下: 数学函数abs(x) 描述:绝对值。 返回值类型:和输入相同。 示例: openGauss=# SELECT abs(-17.4);abs ------17.4 (1 row)cbrt(dp) 描述:立方根。 返回值类型:double precision 示例: openGauss=# SELECT cbrt(27.0);cbrt ------3 (1 row)c…

宿舍Giwifi聚合方案

方案A: 方案B: 方案C:

在 Linux 上把 Vim 配置为默认编辑器

目录 ⛳️推荐 在 Linux 命令行中编辑 将 Vim 设置为其他程序的默认值 在 Alpine 中编辑电子邮件 总结 ⛳️推荐 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站 我使用 Linux 大概有…

SpringBoot整合AOP实现打印方法执行时间切面

pom.xml<dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-aop</artifactId></dependency>代码 创建注解 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; imp…

MySQL中什么情况下会出现索引失效?如何排查索引失效?

目录 1-引言&#xff1a;什么是MySQL的索引失效&#xff1f;(What、Why)1-1 索引失效定义1-2 为什么排查索引失效 2- 索引失效的原因及排查&#xff08;How&#xff09;2-1 索引失效的情况① 索引列参与计算② 对索引列进行函数操作③ 查询中使用了 OR 两边有范围查询 > 或 …

rust中结构体的属性默认是不能修改的,要想修改可以有两种方式

Rust中结构体里面的属性默认是不支持修改的&#xff0c;而且默认不是pub的&#xff0c;要想修改的话&#xff0c;有两种方式&#xff0c;我以为和python里面的类似呢&#xff0c;但是还是需要一点技术含量的。如果想在引到外部修改&#xff0c;需要声明pub&#xff0c;如果想在…

Ubuntu 24.04 LTS x86_64 OVF (sysin) - VMware 虚拟机模板

Ubuntu 24.04 LTS x86_64 OVF (sysin) - VMware 虚拟机模板Ubuntu 24.04 LTS x86_64 OVF (sysin) - VMware 虚拟机模板 Ubuntu 24.04 LTS (GNU/Linux 6.8-generic x86_64) 请访问原文链接:Ubuntu 24.04 LTS x86_64 OVF (sysin) - VMware 虚拟机模板,查看最新版。原创作品,转…

路由选择协议三剑客--BGP协议

一、背景 边界网关协议(Border Gateway Protocol, BGP)是用来处理像因特网规模大小的网络协议,能够妥善处理好不相关路由域间的多路连接协议。BGP一般用于企业和企业之间,也就是运营商骨干网的通信,一般使用在AS内或AS间通信,在大型企业网中实现的比较多。 内部网关协议只…

Multitouch 1.27.28 免激活版 mac电脑多点触控手势增强工具

Multitouch 应用程序可让您将自定义操作绑定到特定的魔术触控板或鼠标手势。例如&#xff0c;三指单击可以执行粘贴。通过执行键盘快捷键、控制浏览器的选项卡、单击鼠标中键等来改进您的工作流程。 Multitouch 1.27.28 免激活版下载 强大的手势引擎 精心打造的触控板和 Magic …

【分布式通信】NPKit,NCCL的Profiling工具

NPKit介绍 NPKit (Networking Profiling Kit) is a profiling framework designed for popular collective communication libraries (CCLs), including Microsoft MSCCL, NVIDIA NCCL and AMD RCCL. It enables users to insert customized profiling events into different C…

Ubuntu 22.04.4 LTS磁盘扩容

安装gpartedsudo apt updatesudo apt install gparted然后启动gpartedsudo gparted启动成功会完成一个新的对话框,直接调整磁盘大小的话会提示失败扩容查看只读文件系统的详细信息,点击Information(信息) 查看磁盘的挂载位置按顺序运行以下命令sudo -i mount -o remount -r…

K8s: 部署 kubernetes dashboard

部署 Dashboard K8s 官方有一个项目叫 dashboard&#xff0c;通过这个项目更方便监控集群的状态 官方地址: https://github.com/kubernetes/dashboard 通常我们通过命令行 $ kubectl get po -n kube-system 能够查看到集群所有的组件&#xff0c;但这样的方式比较不太直观 …

Jenkins 简述及其搭建

什么是持续集成?持续集成(CI)是在软件开发过程中自动化和集成许多团队成员的代码更改和更新的过程。在 CI 中,自动化工具在集成之前确认软件代码是有效且无错误的,这有助于检测错误并加快新版本的发布。什么是持续交付?持续交付 (CD) 是指每天多次将新软件投入生产,自动…

火山引擎VeDI:如何高效使用A/B实验,优化APP推荐系统

更多技术交流、求职机会,欢迎关注字节跳动数据平台微信公众号,回复【1】进入官方交流群在移动互联网飞速发展的时代,用户规模和网络信息量呈现出爆炸式增长,信息过载加大了用户选择的难度,这样的背景下,推荐系统应运而生,为用户提供个性化的内容推荐。推荐系统在不断迭代…

【HarmonyOS4学习笔记】《HarmonyOS4+NEXT星河版入门到企业级实战教程》课程学习笔记(三)

课程地址&#xff1a; 黑马程序员HarmonyOS4NEXT星河版入门到企业级实战教程&#xff0c;一套精通鸿蒙应用开发 &#xff08;本篇笔记对应课程第 4 - 6节&#xff09; P5《04.快速入门》 本节来实现一个 HelloWorld 效果&#xff1a; 1、打开编辑器&#xff0c;选择新建项目&…

查看svn密码

查看svn密码 下载TSvnPwd.exe, 这是一个压缩包 打开这个文件路径 C:\Users\浅笑\AppData\Roaming\Subversion\auth\svn.simple 把下载好压缩包,解压至这个目录中本文来自博客园,作者:浅笑,转载请注明原文链接:https://www.cnblogs.com/qx-blog/p/18159483

目标检测网络YOLO进化之旅

yolo系列网络在目标检测领域取得了巨大的成功&#xff0c; 尤其是在工程实践中&#xff0c; 以其出色的性能优势获得了广泛的应用落地。 YOLO的前3个版本是由同一个作者团队出品&#xff0c; 算是官方版本。 之后的版本都是各个研究团队自己改进的版本&#xff0c; 之间并无明…

amCharts使用

参考 代码如下<!DOCTYPE html> <html><head><script src="https://cdn.amcharts.com/lib/5/index.js"></script><script src="https://cdn.amcharts.com/lib/5/xy.js"></script><script src="https://c…