题解 CF2039B

题意：

给定一个字符串，问其是否包含一个非空子串，使该子串本质不同的非空子串数量是偶数。

思路：

发现如果字符串很长，本质非空子串的数量不好处理。不妨直接从最短的一些子串考虑，手搓一些性质。

子串长度为 $1$ ：本质不同的子串个数必然为 $1$ ，不符合；
子串长度为 $2$ ：如果两个字符相同（如 aa），本质不同子串个数是 $2$ ，符合条件；如果两个字符不同（如 ab），本质不同的子串个数是 $3$ ，不符合；
子串长度为 $3$ ：如果存在两个相邻相同的字符，则必然符合 $2$ 中的情况，符合条件。于是我们只剩下 aba、abc 的两种情况。前者不符合条件，后者符合；

由上述情况继续推算，不难发现，只有原字串是类似 abababababab 这样 ab 交替的字符串，才不存在符合条件的子串，输出 -1，其它字符串都一定存在子串符合条件。

程序如下：

CPP

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1e5+5;
int T;
char ch[N];
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%s",ch+1);
		int n=strlen(ch+1);
		bool flag=false;
		for(int i=1;i<n;i++){
			if(ch[i]==ch[i+1]){
				printf("%c%c\n",ch[i],ch[i+1]);
				flag=true;
				break;
			}
			if(ch[i]!=ch[i+1]&&ch[i+1]!=ch[i+2]&&ch[i]!=ch[i+2]&&i+2<=n){
				printf("%c%c%c\n",ch[i],ch[i+1],ch[i+2]);
				flag=true;
				break;
			}
		}
		if(!flag)printf("-1\n");
	}
	return 0;
}

文章操作

题意：

思路：

程序如下：

THE END

相关推荐

评论

题解 CF2039B