题目链接: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; }
Comments NOTHING