hihoCoder week 58-1-Beautiful String 题目1 : Beautiful String 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 We say a string is beautiful if it has the equal amount of 3 or more continuous letters (in increasing order.) Here are some example of valid beautiful strings: “abc”, “cde”, “aabbcc”, “aaabbbccc”. Here are some example of invalid beautiful strings: “abd”, “cba”, “aabbc”, “zab”. Given a string of alphabets containing only lowercase alphabets (a-z), output “YES” if the string contains a beautiful sub-string, otherwise output “NO”. 输入 The first line contains an integer number between 1 and 10, indicating how many test cases are followed. For each test case: First line is the number of letters in the string; Second line is the string. String length is less than 10MB. 输出 For each test case, output a single line “YES”/”NO” to tell if the string contains a beautiful sub-string. 提示 Huge input. Slow IO method such as Scanner in Java may get TLE. 样例输入 4 3 abc 4 aaab 6 abccde 3 abb 样例输出 YES NO YES NO
本题考察字符串的基本知识。题目给出了漂亮字符串的定义，形如aa…bb…cc，保证至少3个连续升序的字符串，并且每个字符的个数相同。仔细观察可以发现，虽然aaaabbccc不是漂亮字符串，但其子串aabbcc是漂亮的，所以只要保证b的数量小于等于a和c的数量即可。 所以解法就是遍历字符串，计算每个字符重复出现的次数，判断连续3种字符是否为连续升序，且满足中间字符数量大于两边。算法复杂度为O(N)。 完整代码如下： [cpp] #include<iostream> #include<cstdio> #include<string> using namespace std; const int kMaxN = 10 * 1024 * 1024 + 5; char line[kMaxN]; int n; char same_letter[kMaxN]; int same_length[kMaxN]; bool check(int k) { if ((same_letter[k] – 1 == same_letter[k – 1]) && (same_letter[k – 1] – 1 == same_letter[k – 2])) if (same_length[k – 1] <= same_length[k] && same_length[k – 1] <= same_length[k – 2]) return true; return false; } bool IsBeautiful() { if (n < 3) return false; else { int i = 0,k=0; while (i < n) { int j = i + 1; while (j < n && line[j] == line[i]) j++; same_letter[k] = line[i]; same_length[k] = j – i; if (k >= 2) { if (check(k)) return true; } k++; i = j; } return false; } } int main() { int t; scanf("%d", &t); while (t–) { scanf("%d", &n); scanf("%s", line); if (IsBeautiful()) printf("YESn"); else printf("NOn"); } return 0; } [/cpp] 本代码提交AC，用时293MS，内存37MB。]]>
现在我们分析红色那组字符，首先s[0]==s[2]不成立，可以把s[0]改成A；也可以把s[2]改成C，如果我们把s[2]改成C的话，虽然s[0]==s[2]成立，但是s[2]==s[4]又不成立了，又要修改s[4]；但是如果我们把s[0]改成A的话，则s[0]==s[2]==s[4]都成立，且修改次数更少。那么要怎样才能使修改的次数最少呢？
我们回到问题的本源：使用红色那组字符都相同，为了使修改次数最少，我们当然是将所有字符统一成当前出现次数最多的那个字符咯，这样只需要修改较少的非同一字符，在这个例子中，就是修改成出现次数最多的A。
如果前k个字符串和后k个字符串没有重叠，那就很简单了，只需依次检查对应字符是否相等。
理解了以上内容，代码很快就能写出来了：
[cpp]
#include<iostream>
#include<string>
using namespace std;
//求4个数的最大值
int max4(int a,int b,int c,int d)
{
int maxab=a>b?a:b;
int maxcd=c>d?c:d;
return maxab>maxcd?maxab:maxcd;
}
int main()
{
int t,k,n,d,ans;//t,k为题意；n为字符串长度；d为n-k相隔为d的字符需要相等；ans表示需要修改的碱基数量。
string s;
cin>>t;
while(t–)
{
ans=0;
cin>>s>>k;
n=s.size();
d=n-k;
if(2*k<=n)//如果最前k个碱基和最后k个碱基没有重叠的话
{
for(int i=0;i<k;i++)
if(s[i]!=s[i+d])//只需要依次检查对应字符是否相等即可
ans++;
}
else//如果有重叠，则另行讨论
{
for(int i=0;i<d;i++)//把所有碱基分成d组，需要确保每组都是同一个字符
{
int A=0,T=0,G=0,C=0,num=0;
for(int j=i;j<n;j+=d)//对于每一组，求出该组中出现次数最多的碱基的个数
{
num++;
if(s[j]==’A’)
A++;
else if(s[j]==’T’)
T++;
else if(s[j]==’G’)
G++;
else
C++;
}
int maxATGC=max4(A,T,G,C);//该组全部修改成出现次数最多的碱基
int change_num=num-maxATGC;//用该组中所有碱基个数减去出现次数最多的碱基个数，就是需要修改的碱基个数
ans+=change_num;
}
}
cout<<ans<<endl;
}
return 0;
}
[/cpp]
本代码提交AC，用时1MS，内存0MB。
]]>