本文主要是介绍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. 最有价值字符串【挖掘性质+分类讨论】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
