题解 CF2039B

· · 题解

题意：

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

思路：

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

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

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

程序如下：

#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