本文主要是介绍hiho一下 第五十八周 Beautiful String dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目1 : Beautiful String
-
4 3 abc 4 aaab 6 abccde 3 abb
样例输出 -
YES NO YES NO
-
题意，给一个字符串，是否存在一个连续子串，满足子串有大于3种字符，是递增的顺序且每种字符个数相同，如a..ab...bc...c其中a b c个数相等，且是递增的。由于，当大于3个的时候，总会3个字符是满足的，所以只用考虑是3个的情况，num[i] 表示，第i个位置，向后最多有num[i]个字符是相同的。如果，有这样的x1...x2...x3...,x1x2x3递增，且num[x2] == num[x3] ,num[x3] >= num[x1](由于可以存在这样的串aabbccc,所以只要，num[x3] >= x[1])，str[x1] == str[i] + 1 && str[x2] == str[i] + 2&& num[x1] == num[i] && num[x2] >= num[i] 则说明存在。
-
#define N 10000050 #define M 100005 #define maxn 205 #define MOD 1000000000000000007 int n,num[N],len; char str[N]; int main() {while(S(n)!=EOF){while(n--){S(len);gets(str);FI(len){str[i] = getchar();}num[len - 1] = 1;for(int i = len - 2 ;i>=0;i--){if(str[i] == str[i+1])num[i] = num[i+1] + 1;elsenum[i] = 1;}bool flag = false;FI(len){int x1 = i + num[i],x2 = i + 2 * num[i],x3 = i + 3 * num[i];if(x3 <= len && str[x1] == str[i] + 1 && str[x2] == str[i] + 2&& num[x1] == num[i] && num[x2] >= num[i] ){flag = true;break;}}if(flag){printf("YES\n");}else {printf("NO\n");}}}return 0; }
描述
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.
这篇关于hiho一下 第五十八周 Beautiful String dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
