22湖北省赛 - J. Palindrome Reversion（回文，哈希拼接）

https://codeforces.com/gym/103729/problem/J

题意
给定一个小写字母组成的字符串，判断能否通过操作一次，将其变为回文串：选择一段区间 $[l,r]$ 将其翻转。
$1\le |s|\le 10^5$

思路
首先发现如果串两端存在相同字符的话，这两端已经是回文的了，把这两端去掉，只考虑中间部分如何变。

法1：分类讨论
如果能变成回文串，那么原串只有三种格式：

• AAB，翻转后面 AB 两段，变成回文串；
• BAA，翻转前面 BA 两段，变成回文串；
• ABA，翻转最后 A 段或者前面 A 段，变成回文串。

暴力枚举 A 段长度即可。

//双哈希
#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long

const int N = 200010, mod = 1e9+7;
int T, n, m;
char a[N];
int h1[N], h2[N], P1 = 13331, p1[N], mod1 = 1e9+7;
int h11[N], h22[N], P2 = 1333331, p2[N], mod2 = 1e9+17;

int queryl(int l, int r)
{
	return (h1[r] - h1[l-1] * p1[r-l+1] % mod1 + mod1) % mod1;
}
int queryl2(int l, int r)
{
	return (h11[r] - h11[l-1] * p2[r-l+1] % mod2 + mod2) % mod2;
}

int queryr(int l, int r)
{
	return (h2[l] - h2[r+1] * p1[r-l+1] % mod1 + mod1) % mod1;
}
int queryr2(int l, int r)
{
	return (h22[l] - h22[r+1] * p2[r-l+1] % mod2 + mod2) % mod2;
}

int pd(int l, int r)
{
	if((r-l+1) % 2 == 1)
	{
		int mid = (r-l+1)/2;
		if(queryl(l, l+mid) == queryr(l+mid, r) && 
			queryl2(l, l+mid) == queryr2(l+mid, r)) return 1;
		return 0;
	}
	else
	{
		int mid = (r-l+1)/2;
		if(queryl(l, l+mid-1) == queryr(l+mid, r) && 
			queryl2(l, l+mid-1) == queryr2(l+mid, r)) return 1;
		return 0;
	}
}

signed main(){
	Ios;
	cin >> a + 1;
	n = strlen(a + 1);
	
	p1[0] = p2[0] = 1;
	for(int i=1;i<=n;i++){
		p1[i] = p1[i-1] * P1 % mod1;
		p2[i] = p2[i-1] * P2 % mod2;
		h1[i] = (h1[i-1] * P1 % mod1 + a[i]) % mod1;
		h11[i] = (h11[i-1] * P2 % mod2 + a[i]) % mod2;
	}
	for(int i=n;i>=1;i--){
		h2[i] = (h2[i + 1] * P1 % mod1 + a[i]) % mod1;
		h22[i] = (h22[i + 1] * P2 % mod2 + a[i]) % mod2;
	}
	
	int l = 1;
	while(l < n && a[l] == a[n]) l ++, n --;
	
	if(l >= n)
	{
		cout << l-1 << ' ' << n + 1;
		return 0;
	}
	
	for(int len = 1; len <= (n-l+1)/2; len ++)
	{
		if(queryl(l, l+len-1) == queryl(l+len, l+2*len-1) && 
			queryl2(l, l+len-1) == queryl2(l+len, l+2*len-1))
		{
			if(pd(l+2*len, n))
			{
				cout << l+len << ' ' << n;
				return 0;
			}
		}
		if(queryl(n-len+1, n) == queryl(n-2*len+1, n-len) && 
			queryl2(n-len+1, n) == queryl2(n-2*len+1, n-len))
		{
			if(pd(l, n-2*len))
			{
				cout << l << ' ' << n-len;
				return 0;
			}
		}
		if(queryl(l, l+len-1) == queryl(n-len+1, n) && 
			queryl2(l, l+len-1) == queryl2(n-len+1, n))
		{
			if(pd(l+len, n-len))
			{
				cout << n-len+1 << ' ' << n;
				return 0;
			}
		}
	}
	cout << "-1 -1";
	
	return 0;
}
/*
aaabccdedcabcaa
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

法2：哈希拼接
发现选择的区间肯定是从串首开始到串中某个位置，或者从串中某个位置到串尾，所以可以枚举串中的这个位置。
到串首或者到串尾两种情况，对于到串首的情况来说，如果发现某个字符和串首元素相同，判断该位置到串尾位置这个区间翻转后是否为回文串，枚举所有位置。
翻转之后的区间和原串剩余部分进行哈希拼接，判断整个串是否回文。

例如串 ababcdc，要把 [abcdc] 这一区间翻转，变成 abcdcba。
那么翻转之后串的正向哈希就为：[ab] 的正向哈希乘以 p[5] 加上 区间 [abcdc] 的反向哈希；
翻转之后串的反向哈希为：区间 [abcdc] 的正向哈希乘以 p[2] 加上 [ab] 的反向哈希。
如果这两个哈希值相同，就说明翻转之后的串是回文的。

//单哈希
#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long

const int N = 200010, mod = 1e9+7;
int T, n, m;
char a[N];
unsigned long long hl[N], hr[N], p[N], P = 13331;

int queryl(int l, int r){
	return hl[r] - hl[l-1] * p[r-l+1];
}
int queryr(int l, int r){
	return hr[l] - hr[r+1] * p[r-l+1];
}

signed main(){
	Ios;
	cin >> a + 1;
	n = strlen(a + 1);
	
	p[0] = 1;
	for(int i=1;i<=n;i++)
		p[i] = p[i-1] * P, hl[i] = hl[i-1] * P + a[i];
	for(int i=n;i>=1;i--)
		hr[i] = hr[i+1] * P + a[i];
	
	int l = 1;
	while(l < n && a[l] == a[n]) l ++, n --;
	
	if(l >= n){
		cout << l-1 << ' ' << n+1;
		return 0;
	}
	
	for(int i=l;i<n;i++)
	{
		if(a[i] != a[n]) continue;
		if(queryr(l, i) * p[n-i] + queryl(i+1, n) == queryr(i+1, n) * p[i-l+1] + queryl(l, i)){
			cout << l << " " << i;
			return 0;
		}
	}
	for(int i=l+1;i<=n;i++)
	{
		if(a[i] != a[l]) continue;
		if(queryl(l, i-1) * p[n-i+1] + queryr(i, n) == queryl(i, n) * p[i-l] + queryr(l, i-1)){
			cout << i << " " << n;
			return 0;
		}
	}
	cout << "-1 -1";
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

---

现在看其实这道题并不难，但是场上却过的很慢，应该是榜带歪了，所以不能太相信榜，看看有思路就可以写。
另外这道题场上的时候是想到第一种做法的，但是还是犯了上次网络赛的那个错误，有了思路没试样例就直接去写了，写完之后发现第二个样例过不去，然后就觉得自己的思路有问题，加上这道题过的人少，就觉得自己的思路不对，没有这么简单。。其实第二个样例本应该是对的，只不过有点特殊，但是思路是对的，而写的时候 r 和 n 混用了，导致第二个样例没对，但是我却以为是思路问题，就没有继续往下想。
如果一开始有思路的时候先看一下这个样例，发现也是能用这个思路做的，后面写挂的时候也知道自己写的有问题，而不是怀疑思路，直接不去想了！

有些题并不是很难，自己的思路很可能就是对的，不要轻易放弃这个思路！

总结经验。