题目链接：https://codeforces.com/gym/103729/problem/J
赛场上没做出这题，可惜了。其实一开始就想到了字符串hash，甚至思路都和题解一样，但是由于忘记了字符串hash的板子，然后一时着急就没做出来。其实不难。
题意
给定一个字符串S，问能否通过将一个连续区间[l ,r](l <= r)翻转一次使得字符串S变为一个回文串。
输出任意一种可行方案即可。
如果不存在就输出-1 -1。
思路
第一步，如果这个字符串本身就是回文就不需要修改，直接输出1 1就行。
第二步，将字符串左右两边的回文部分删除，记录下删除了多少（记录为dl），输出答案的时候需要补上。
第三步，将当前字符串S初始化成hash串，要做两个hash，一个正向一个反向，同时把进制数base求一下连续的幂（后面求子串的hash会用到）。
第四步，以1作起点，向右枚举终点，如果找到了一个区间翻转可以使得字符串变为回文，那么就直接输出。如果没有，再从N为终点，向左枚举起点，如果有答案也直接输出。记得加上dl。
为什么从1和N开始枚举呢，因为可以翻转变为回文的一定是以下三种情况。
如果没答案就输出-1 -1。
真实惨痛的经历，下次一定要带全板子！
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef unsigned long long ULL;
const ULL maxn = 1e5 + 9, base = 131;
ULL h1[maxn], h2[maxn], b[maxn];
char s[maxn];
int N = 0;
void initHash(char s[], int N)
{
b[0] = 1;
for(int i = 1;i <= N; ++ i)b[i] = b[i - 1] * base;
for(int i = 1;i <= N; ++ i)h1[i] = h1[i - 1] * base + s[i];
for(int i = N;i >= 1; -- i)h2[i] = h2[i + 1] * base + s[i];
}
ULL getHash1(int l,int r){return h1[r] - h1[l - 1] * b[r - l + 1];}
ULL getHash2(int l,int r){return h2[l] - h2[r + 1] * b[r - l + 1];}
bool isRe(int l,int r)//将[l, r]翻转是否回文
{
ULL res1 = getHash1(1, l - 1) * b[N - l + 1] + getHash2(l, r) * b[N - r] + getHash1(r + 1, N);
ULL res2 = getHash2(r + 1, N) * b[r] + getHash1(l, r) * b[l - 1] + getHash2(1, l - 1);
return res1 == res2;
}
signed main()
{
cin >> s + 1;
int l = 1, r = strlen(s + 1);
while(l <= r && s[l] == s[r])l ++, r --;
int dl = l - 1;
if(l > r)return printf("1 1\n"), 0;
for(int i = l;i <= r; ++ i)s[++ N] = s[i];
s[N + 1] = '\0';
initHash(s, N);
for(int i = 1;i <= N; ++ i)if(isRe(1, i))return printf("%lld %lld\n", 1 + dl, i + dl), 0;
for(int i = N;i >= 1; -- i)if(isRe(i, N))return printf("%lld %lld\n", i + dl, N + dl), 0;
printf("-1 -1\n");
return 0;
}
文章评论