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。]]>