Acwing 5468. 最有价值字符串【挖掘性质+分类讨论】

2024-02-11 19:04
文章标签 分类 字符串 讨论 acwing 价值 挖掘 性质 最有 5468

本文主要是介绍Acwing 5468. 最有价值字符串【挖掘性质+分类讨论】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://www.acwing.com/problem/content/5471/

题目描述：

A,B,C 三人在玩一个有关字符串的游戏。

给定三人每人一个由大小写字母构成的字符串。

三人的字符串的长度相同。

规定，一个字符串的价值等于该字符串中出现次数最多的子串的出现次数。

例如，aaaaaa 的价值为 6，因为出现次数最多的子串 a 一共出现了 6 次；abab 的价值为 2，因为出现次数最多的子串 ab 一共出现了 2 次。

游戏开始后，每人都需要对自己的字符串进行恰好 n 次修改，每次修改需要将字符串中的某个字符修改为另一个不同的字符，例如将 aaab 修改为 acab。

所有修改完毕后，最有价值字符串的拥有者将获得游戏胜利。

请你计算，如果所有人都采取最优策略，那么谁将最终获胜。

输入输出描述：

输入格式

第一行包含整数 n。

第二行，包含一个由大小写字母构成的字符串，表示给 A 的字符串。

第三行，包含一个由大小写字母构成的字符串，表示给 B 的字符串。

第四行，包含一个由大小写字母构成的字符串，表示给 C 的字符串。

保证这三个人获得的字符串的长度均相同。

输出格式

共一行，A 获胜则输出 A，B 获胜则输出 B，C 获胜则输出 C，不止一人获胜则输出 D。

数据范围

前 6 个测试点满足 0≤n≤20，每个输入字符串的长度范围 [1,20]。
所有测试点满足 0≤n≤10^9，每个输入字符串的长度范围 [1,10^5]。

输入样例1：
3
abcdd
efgcd
hijgk
输出样例1：
A
输入样例2：
7
abcdefbcgfhi
igbccjbkchle
gkmnlcjnboce
输出样例2：
B
输入样例3：
1
abcabc
cbabac
ababca
输出样例3：
C
输入样例4：
15
abcdefghi
jkdlbmnop
jqrstduve
输出样例4：
D

解题思路：

这个题目只要观察一下挖掘出一个性质，那么这个题目就很简单了，但是如果没挖掘出来可能就会认为比较难了，赛时我很快就发现了这个性质，但是有一种情况一直没考虑到导致虽然赛时做出来了，但是wa了好几发，下面我举个例子描述一下我是怎么发现这个性质的。

例子1：ababab

对于上述例子1，我们可以发现子串ab出现了三次，同时这个字符串中的出现次数最多的子串出现的次数也是3，我们观察可以发现，ab出现了三次，自然ab中的a和b都出现了三次，也就是说子串a和子串b也都出现了三次， 我们可以发现对于某个子串出现了k次，那么这个子串中的每个字符都至少出现k次，当子串中有重复字符时，那么某个字符的出现次数会大于k，也就是说我们只需要考虑长度为1的子串即可，因为长度等于1的子串出现的次数肯定大于等于长度大于1的子串出现的次数。

通过上述分析，我们现在只需要考虑长度为1的子串即可，对于三个字符串中的任意一个字符串的修改操作，肯定是把当前这个字符串的所有字符都修改为同一种字符，那么我们肯定首先拿到出现次数最多的那个字符ch，把其他不等这个ch的字符都修改为字符ch.

设我们当前某个字符串出现次数最多的字符出现的次数为k，此时题目给出的修改次数为n，当前字符串长度为len，下面我们来分类讨论一下。

(1)k<len

当k+n<=len,出现次数最多的字符出现的次数就是k+n

当k+n>len，我们首先让所有字符相同，多余的操作次数我们可以放在某个位置上消耗完，例如acaaa，当n==3，我们可以先把c变为不等于a的其他字符，例如字符b，再变为字符c，然后把这个字符再变为a，就是先把多余的操作次数消耗掉，在变成需要的字符即可，此时出现次数最多的字符出现次数最终就可以是len。

(2)k==len

当n==1，最开始所有字符相同，我们必须要操作一次，我们只能某个位置的字符修改掉，那么出现次数最多的字符出现了len-1次。

当n!=1时，我们可以向上面(1)中的k+n>len这种情况一样，先消耗多余的操作，那么出现次数最多的字符出现次数仍然是len次。

时间复杂度：O(len)，len表示字符串的长度。

空间复杂度：O(len)，len表示字符串的长度。

cpp代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>using namespace std;const int N=1e5+10;int n,m;
int main()
{cin>>n;string s1,s2,s3;cin>>s1>>s2>>s3;unordered_map<char,int>cnt1,cnt2,cnt3;for(auto& t:s1)cnt1[t]++;for(auto& t:s2)cnt2[t]++;for(auto& t:s3)cnt3[t]++;int max1=0,max2=0,max3=0;for(auto& t:cnt1)max1=max(max1,t.second);for(auto& t:cnt2)max2=max(max2,t.second);for(auto& t:cnt3)max3=max(max3,t.second);bool ok1=false,ok2=false,ok3=false;int len=s1.size();if(max1==len){if(n==1)max1=len-1,ok1=true;}if(max2==len){if(n==1)max2=len-1,ok2=true;}if(max3==len){if(n==1)max3=len-1,ok3=true;}if(!ok1)max1=min(max1+n,len);if(!ok2)max2=min(max2+n,len);if(!ok3)max3=min(max3+n,len);if(max1>max(max2,max3))cout<<"A"<<endl;else if(max2>max(max1,max3))cout<<"B"<<endl;else if(max3>max(max1,max2))cout<<"C"<<endl;else cout<<"D"<<endl;return 0;
}

这篇关于Acwing 5468. 最有价值字符串【挖掘性质+分类讨论】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/700596。

相关文章

基于人工智能的图像分类系统

基于人工智能的图像分类系统

目录 引言项目背景环境准备 硬件要求软件安装与配置系统设计 系统架构关键技术代码示例 数据预处理模型训练模型预测应用场景结论 1. 引言 图像分类是计算机视觉中的一个重要任务，目标是自动识别图像中的对象类别。通过卷积神经网络（CNN）等深度学习技术，我们可以构建高效的图像分类系统，广泛应用于自动驾驶、医疗影像诊断、监控分析等领域。本文将介绍如何构建一个基于人工智能的图像分类系统，包括环境
阅读更多...
认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎，细嗅蔷薇。你好朋友，这里是锅巴的C\C++学习笔记，常言道，不积跬步无以至千里，希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目： 牛牛发明了一种新的四舍五入应用于整数，对个位四舍五入，规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数
阅读更多...
C和指针：字符串

C和指针：字符串

字符串、字符和字节 字符串基础 字符串就是一串零个或多个字符，并且以一个位模式为全0的NUL字节结尾。 字符串长度就是字符串中字符数。 size_t strlen( char const *string ); string为指针常量(const修饰string)，指向的string是常量不能修改。size_t是无符号数，定义在stddef.h。 #include <stddef.h>
阅读更多...
PHP字符串全排列

PHP字符串全排列

方法一： $str = 'abc';$a =str_split($str);perm($a, 0, count($a)-1);function perm(&$ar, $k, $m) {if($k == $m){ echo join('',$ar), PHP_EOL;}else {for($i=$k; $i<=$m; $i++) {swap($ar[$k], $ar[$i]);perm($ar
阅读更多...
用Pytho解决分类问题_DBSCAN聚类算法模板

用Pytho解决分类问题_DBSCAN聚类算法模板

一：DBSCAN聚类算法的介绍 DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种基于密度的聚类算法，DBSCAN算法的核心思想是将具有足够高密度的区域划分为簇，并能够在具有噪声的空间数据库中发现任意形状的簇。 DBSCAN算法的主要特点包括： 1. 基于密度的聚类：DBSCAN算法通过识别被低密
阅读更多...
PHP7扩展开发之字符串处理

PHP7扩展开发之字符串处理

前言 这次，我们来看看字符串在PHP扩展里面如何处理。 示例代码如下： <?phpfunction str_concat($prefix, $string) {$len = strlen($prefix);$substr = substr($string, 0, $len);if ($substr != $prefix) {return $prefix." ".$string;} else
阅读更多...
十一、C语言：字符串函数

十一、C语言：字符串函数

目录 一、strlen 二、strcpy 三、strcat  四、strcmp 五、strstr 六、strtok 七、strerror 一、strlen 注意：strlen()函数的返回值是size_t，两个size_t相减仍为无符号数 int main(){char arr[10] = "abc";char brr[10] = "abc123";if (strl
阅读更多...
PMP–一、二、三模–分类–14.敏捷–技巧–看板面板与燃尽图燃起图

PMP–一、二、三模–分类–14.敏捷–技巧–看板面板与燃尽图燃起图

文章目录 技巧一模14.敏捷--方法--看板（类似卡片）1、 [单选] 根据项目的特点，项目经理建议选择一种敏捷方法，该方法限制团队成员在任何给定时间执行的任务数。此方法还允许团队提高工作过程中问题和瓶颈的可见性。项目经理建议采用以下哪种方法？ 易错14.敏捷--精益、敏捷、看板（类似卡片）--敏捷、精益和看板方法共同的重点在于交付价值、尊重人、减少浪费、透明化、适应变更以及持续改善等方面。
阅读更多...
【AcWing】851. 求最短路

【AcWing】851. 求最短路

spfa算法其实是对贝尔曼福特算法做一个优化。 贝尔曼福特算法会遍历所有边来更新，但是每一次迭代的话我不一定每条边都会更新，SPFA是对这个做优化。 如果说dist[b]在当前这次迭代想变小的话，那么一定是dist[a]变小了，只有a变小了，a的后继(b)才会变小。 用宽搜来做优化，用一个队列，队列里边存的就是所有变小了的结点(队列里存的是待更新的点)。 基本思路就是我更新过谁，我再拿
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2