CF1789B Serval and Inversion Magic

CF1789B Serval and Inversion Magic

---

思路

由于讨论回文性我会将下面所有示例字符串以|分成两半

1.先思考我的[l,r]区间有哪些可能呢？

第一种：区间跨左右不对称
1011|1110
如果想要这种区间反转后回文，至少要先保证11|11回文
如果11|11是回文的，区间完全可以缩小为
1011|1110
即可以归纳为第三种

第二种：区间跨左右对称
101111101
这种一定本来就是回文串，直接YES

第三种：区间在一侧
11011|11101
从外层向内，由内层向外，如果本来就满足回文，区间完全可以缩小为
11011|11101

2.从区间的分析已经得到了本题算法

(1)本来就是回文串，直接YES
(2)从外层向内，由内层向外,找最小区间
(3)最小区间反转后回文即为YES
(4)否则为NO

---

时间复杂度 O(n)

---

AC代码

#include <bits/stdc++.h>
using namespace std;
int main()
{int t;cin >> t;while (t--){int n;cin >> n;string s;cin >> s;if (n == 1){cout << "Yes\n";continue;}int i = 0, j = n - 1, x = floor((n - 1) / 2), y = n / 2;while (i < j && s[i] == s[j]){i++, j--;}while (i <= x && y <= j && s[x] == s[y]){x--, y++;}if (i == x + 1){cout << "Yes\n";continue;}else{while (((s[i] - '0') == 1 - (s[j] - '0')) && (i <= x)){i++, j--;}if (i == x + 1){cout << "Yes\n";}else{cout << "No\n";}}}
}