hiho一下 第五十八周 Beautiful String dp

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;
}