AT3590 Inserting ‘x‘ 题解

本题是一道双指针的模拟题。

题意

给你一个字符串 s s s，你可以在 s s s 的任意位置插入 x x x，是 s s s 变为回文。

解决

定义双指针 l l l 和 r r r， l l l 和 r r r 初始化为 s s s 的两端。

定义一个计数的 a n s ans ans，用来计算到底需要插入多少个 x x x。

模拟规则如下：

• 如果 l l l 所在的位置的值和 r r r 所在的位置的值相同，则构成回文，不用插入 x x x，可忽略这个位置，跳过 l l l，向前跳过 r r r。

• 如果 l l l 所在位置的值是 x x x，则我们要把 r r r 所在位置的值插入一个 x x x，现在 l l l 和 r + 1 r+1 r+1 对称构成回文，然后跳过 l l l。

• 如果 r r r 所在位置的值是 x x x，则我们要把 l l l 所在位置的值插入一个 x x x，现在 − 1 l -1l −1l 和 r r r 对称构成回文，然后向前跳过 r r r。

• 如果都不满足，则原串无论如何也无法构成回文，则输出 − 1 -1 −1，跳出程序。

样例解释

首先 l l l 指向 0 0 0， r r r 指向 4 4 4，两个位置的数值不等，满足上述第 2 2 2 条，所以要向末尾插入 x x x， a n s ans ans 自增 1 1 1， l l l 自增 1 1 1。

现在 l l l 指向 1 1 1， r r r 指向 4 4 4，两个位置的数值相等， l l l 自增 1 1 1， r r r 自减 1 1 1。

现在 l l l 指向 2 2 2， r r r 指向 3 3 3，两个位置的数不同，满足上述第 3 3 3 条，所以在 l l l 前插入一个 x x x， a n s ans ans 自增 1 1 1， r r r 自减 1 1 1。

现在 l l l 指向 2 2 2， r r r 指向 2 2 2，两个位置的数值相等， l l l 自增 1 1 1， r r r 自减 1 1 1。

现在 l l l 指向 3 3 3， r r r 指向 1 1 1，不满足循环条件，退出程序。

代码

#include<bits/stdc++.h>
using namespace std;
string s;
int l,r,ans;
int main()
{
	ios::sync_with_stdio(false);
	cin>>s,r=s.size()-1;
	while(l<=r)//这个双指针越看越像二分 
	{
		if(s[l]==s[r]) l++,r--;
		else if(s[l]=='x') l++,ans++;
		else if(s[r]=='x') r--,ans++;
		else
		{
			cout<<-1;
			return 0;
		}
	}
	cout<<ans;
	return 0;
}