https://www.luogu.com.cn/problem/P10905
这题的完全思考难度比较大,需要考虑全面
什么情况下能够“Yes”?
1. 本身就是回文串
2. 本身不是回文串,但是尾部是由特殊字符组成的,去掉这个特殊的尾部之后前面的部分是回文串(前面部分可能为空)
然而这种逻辑是有纰漏的
1
babbq
上面的样例,在前面加上qb
就可以实现总体回文。但是如果按照之前的逻辑,这个本来应该是No
所以正确的做法应该是,考虑后面的特殊字符的同时也要判断前面的
- 如果开头的特殊字符组的长度大于后面的,那么无论怎么处理都不可能是回文串
- 如果开头的特殊字符组长度不大于后面的,那么我们需要判断开头的特殊组和末尾的特殊组的前面部分能否构成回文。(这里判断的是前面部分,因为末尾特殊组的后面部分可以通过在整个字符串的开头添加来匹配回文)如果能构成回文,我们把所有特殊组剔除,判断剩余部分是否回文,如果回文,那么经过操作后总体可以变成回文串,输出
Yes
如果本身不是回文,末尾又没有特殊字符,那一定就没有机会了。因为无论怎么添加,只要进行操作,首字符一定是特殊字符
在处理首部特殊组是否和后面回文匹配的时候如果对应错了,但是acwing能过,洛谷则是有一个点wa
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int t;
string s;
int main()
{
cin >> t;
while (t--)
{
cin >> s;
bool flag = false;
int len = s.length();
for (int i = 0; i < len; i++)
{
if (s[i] != s[len - 1 - i])
flag = true;
}
// 本来就是回文直接Yes
if (!flag)
{
cout << "Yes\n";
continue;
}
// 本来不是回文,末尾又不特殊,没有机会变成回文
if (s[len - 1] != 'l' and s[len - 1] != 'q' and s[len - 1] != 'b')
{
cout << "No\n";
continue;
}
bool flagSpecial = false;
bool flagReverse = false;
int cntright = 0; // 末尾特殊组的长度
int cntleft = 0; // 开头特殊组的长度
int j = 0;
for (int i = len - 1; i >= j; i--)
{
if (!flagSpecial)
{
if (s[i] == 'l' or s[i] == 'q' or s[i] == 'b')
{
cntright++;
continue;
}
else
{
// 处理完末尾特殊组,进行下一步
flagSpecial = true;
i++;
}
}
else
{
// 处理开头特殊组
for (; j < i; j++)
{
if (s[j] == 'l' or s[j] == 'q' or s[j] == 'b')
cntleft++;
else
break;
}
if (cntleft > cntright)
{
flagReverse = true;
break;
}
// 去掉所有特殊组,判断是否回文
if (s[i] != s[len - cntright + cntleft - 1 - i])
flagReverse = true;
}
}
if (flagReverse)
{
cout << "No\n";
continue;
}
else
{
flag = false;
// 看首部特殊组是否和尾部特殊组的前面部分构成回文
for (int i = 0; i < cntleft; i++)
{
if (s[i] != s[len - cntright + cntleft - i - 1])
flag = true;
}
if (!flag)
cout << "Yes\n";
else
cout << "No\n";
}
}
return 0;
}