CF2039B Shohag Loves Strings 题解
lun_hao
·
·
题解
洛谷题目传送门
CF 题目传送门
博客园可能食用更佳
题目大意：
对于一个字符串 p ，钦定 \operatorname{f}(p) 表示 p 的非空子串 ^\dag 的个数。
多组数据，每次给定一个字符串 s，求能否找出一个非空字符串 p，使得 p 是 s 的子串，并且满足 \operatorname{f}(p) 为偶数，存在输出任意一个满足条件的字符串 p，无解输出 -1。
数据范围：1 \leq \lvert s \rvert \leq 10^5,\sum \lvert s \rvert \leq 3 \times 10^5。
### 题目分析：
显然是不能枚举 $s$ 的每一个子串，考虑减少枚举子串长度的范围。
钦定 $t$ 为 $s$ 的子串，字符串从下标 $0$ 开始，分类讨论：
- $\lvert t \rvert = 1$ 时，
此时 $\operatorname{f}(t)$ 恒为 $1$，不满足题意，故不考虑枚举。
- $\lvert t \rvert = 2$ 时，
分类讨论：
1. 若 $t_0 \neq t_1$，则 $\operatorname{f}(t)=3$，不满足题意；
2. 若 $t_0 = t_1$，则 $\operatorname{f}(t)=2$，满足题意。
- $\lvert t \rvert = 3$ 时，
分类讨论：
1. 若 $t_0 \neq t_1 \neq t_2$，则 $\operatorname{f}(t)=6$，满足题意；
2. 若 $t_0 = t_1 \neq t_2$，则 $\operatorname{f}(t)=5$，不满足题意，其余几种包含两个字符相同的情况一致，故不再赘述；
3. 若 $t_0 = t_1 = t_2$，则 $\operatorname{f}(t)=2$，满足题意，但这种情况已在 $\lvert t \rvert = 2,t_0=t_1$ 时枚举了，故不考虑枚举。
- $\lvert t \lvert \geq 4$ 时，不难发现前面已验证过其非空真子串，故不用再进行枚举了。
综上所得，枚举每一个长度为 $2$ 和长度为 $3$ 的子串即可检验是否存在解。
### Code:
注意代码中的字符串下标从 $1$ 开始，与上文并非一致
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
char st[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s",st+1);
int n=strlen(st+1);
if(n==1)
{
puts("-1");
continue;
}
bool flag=false;
for(int i=1;i+2<=n;i++)
if(st[i]!=st[i+1]&&st[i]!=st[i+2]&&st[i+1]!=st[i+2])
{
printf("%c%c%c\n",st[i],st[i+1],st[i+2]);
flag=true;
break;
}
if(flag) continue;
for(int i=1;i+1<=n;i++)
if(st[i]==st[i+1])
{
printf("%c%c\n",st[i],st[i+1]);
flag=true;
break;
}
if(!flag) puts("-1");
}
return 0;
}
```