前言

一直在想是否要写这篇题解,但最后还是打算整理帮助有需要的人,因为到现在没看到有人正经写过一篇题解。 这篇题解包含标准答案,最后几题同样给出暴力做法。 另外这些是赛后回顾代码,可能存在赛时代码正确,此处代码存在瑕疵的问题。关于解释有问题的欢迎喷。

实测最后三题都只拿暴力分的话 国一 是稳稳前排;身边数据,约莫再丢一整题分(20),大概 国一 后排。身边有不少有水平的选手,但是先天对 OI 赛制不适没能拿到好成绩,当然真有水平的选手也不会在意这点得失;另外就是太追逐正解,导致该拿到的分没有拿到,拿我个人举例,这是我第二次参加蓝桥杯,去年因为太较真拿了国二。这次本来没有打算较真附上正解,但最后想着想着就都写了正解,希望对你有帮助。

A 题:合法密码

枚举 check 一下就好,个人认为答案应该是 400,不少人答案是 618 还是对题意理解不一样。我觉得 618 的题意理解也算合理的。

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
// A: 合法密码
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define endl '\n'
using namespace std;
const int MAX = 2e5+5;

bool check(const string &s, int l, int r) {
if (r - l + 1 < 8 or 16 < r - l + 1)
return false;
bool has_digit = false, has_character = false;
for (int i = l; i <= r; i++) {
if ('0' <= s[i] and s[i] <= '9') {
has_digit = true;
} else if ('A' <= s[i] and s[i] <= 'Z' or 'a' <= s[i] and s[i] <= 'z') {
; // has_character = true; // 这种做法算出来会是 618
} else {
has_character = true;
}
}
return has_digit and has_character;
}

void solve() {
string s = "kfdhtshmrw4nxg#f44ehlbn33ccto#mwfn2waebry#3qd1ubwyhcyuavuajb#vyecsycuzsmwp31ipzah#catatja3kaqbcss2th";
const int n = s.size();

int cnt = 0;
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
if (check(s, i, j))
cnt++;
cout << cnt << endl;
}

signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);

int t = 1;
// cin >> t;
while (t--)
solve();

return 0;
}

B 题:选数概率

这应该算是一个简单数学题吧,P=2ab(a+b+c)(a+b+c1)P=\frac{2ab}{(a+b+c)(a+b+c-1)}。令 S=a+b+cS=a+b+c,可以发现 S(S1)S(S-1) 这样的分母并不多。找到一个这样的 SS 然后枚举一下 a,b,ca,b,c 即可,如果对于这个 SS 找不到一个解,那就尝试更大的 SS。事实上第一个 SS 就是有解。

答案是 55,94,56。不用代码直接手算也可以做。

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
// B: 选数概率
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define endl '\n'
using namespace std;
const int MAX = 2e5+5;

void solve() {
const int f1 = 2585, f2 = 2632, f3 = 1540, m = 10455;
// p12=f1/m, p23=f2/m, p13=f3/m
int s = 1;
while (true) {
s++;
if (s * (s - 1) % m)
continue;
const int k = s * (s - 1) / m;
for (int a = 1; a < s; a++) {
for (int b = 1; b < s - a; b++) {
int c = s - a - b;
if (2 * a * b == f1 * k and 2 * b * c == f2 * k and 2 * a * c == f3 * k) {
cout << a << ',' << b << ',' << c << endl;
return;
}
}
}
}
}

signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);

int t = 1;
// cin >> t;
while (t--)
solve();

return 0;
}

C 题:蚂蚁开会

记录所有直线经过的整点,放到 map 里,然后你会发现所有出现大于等于 2 次的都是计数点。

时间复杂度 O(nAlog2nA)O(nA\log_2nA)map 带个 log。时间卡的说实话有点紧,毕竟 nAnA5e6,但实在想不到更好的解法,应该是正解了。emmm… 我不确定但好像空间也有点紧张。

unordered_map 或者离线 (基数) 排序会快些,如果愿意写后者完全不用担心时空。

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
// C: 蚂蚁开会
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define endl '\n'
using namespace std;
const int MAX = 2e5+5;

void solve() {
map<pair<int, int>, int> M;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x, y, xx, yy;
cin >> x >> y >> xx >> yy;
const int g = __gcd(abs(xx - x), abs(yy - y));
const int a = (xx - x) / g, b = (yy - y) / g;
int nx = x, ny = y;
while (nx != xx or ny != yy) {
M[{nx, ny}]++;
nx += a;
ny += b;
}
M[{nx, ny}]++;
}
int cnt = 0;
for (const auto &p : M)
if (p.second >= 2)
cnt++;
cout << cnt << endl;
}

signed main() {
#ifdef LOCAL
cout << "LOCAL" << endl;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#else
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
#endif

int t = 1;
// cin >> t;
while (t--)
solve();

return 0;
}

D 题:立定跳远

可以发现答案满足单调性,意思是如果 AA 是可行解,则所有大于等于 AA 的值都是可行解。

因此可以二分答案,假设一个解 xx,然后 O(n)O(n) 检测其是否可行。总时间复杂度 O(nlog2A)O(n\log_2A)

这里需要注意一些细节,毕竟是 OI 赛制嘛:

  • 第 15 行中每个加一减一想清楚是否需要。
  • 第 15 行要与 0 取 max,想清楚题意 aiai1a_i \ge a_{i-1}
  • 第 27 行 llrr 的边界,rr 大多了没事。因为 ai>0a_i>0ll 最小取 1 即可,取 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
// D: 立定跳远
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define endl '\n'
using namespace std;
const int MAX = 2e5+5;

int n, m;
int a[MAX];

bool check(int x) {
int cnt = 0, pre = 0;
for (int i = 0; i < n; i++) {
cnt += max<int>((a[i] - pre + x - 1) / x - 1, 0);
pre = a[i];
}
return cnt <= m + 1;
}

void solve() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> a[i];
}

int l = 1, r = 1e8;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << l << endl;
}

signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);

int t = 1;
// cin >> t;
while (t--)
solve();

return 0;
}

E 题:最小字符串

贪心,双指针。让第二个字符串 tt 中的每个字符出现在第一个严格大于它的 ss 的字符前即可。然后可以发现对 tt 进行排序后可以用双指针线性的解决这个问题。

这里需要注意的是必须要严格大于,即 t[j]<s[i]t[j] < s[i],感谢🙏一位知友提出的问题。

不多说直接看代码吧。时间复杂度 O(n+mlog2m)O(n+m\log_2m)

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
// E: 最小字符串
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define endl '\n'
using namespace std;
const int MAX = 2e5+5;

void solve() {
int n, m;
cin >> n >> m;
string s, t;
cin >> s >> t;
sort(t.begin(), t.end());

int i = 0, j = 0;
string res;
while (i < n or j < m) {
if (j == m or i < n and s[i] <= t[j]) { // s[i] < t[j] 是错误的
res += s[i++];
} else {
res += t[j++];
}
}

cout << res << endl;
}

signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);

int t = 1;
// cin >> t;
while (t--)
solve();

return 0;
}

F 题:数位翻转

稍微需要多想一下,不知道你有没有看出来是动态规划。贪心什么都是有问题的,就不列举了。

设置 dpdp 数组 dp[i][j][0/1]dp[i][j][0/1]。其中 dp[i][j][0]dp[i][j][0] 表示第 ii 位不翻转时,恰好前 ii 位共有 jj 位翻转的最优情况;响应的 dp[i][j][1]dp[i][j][1] 表示翻转。想清楚为什么这么设置 dpdp 数组后状态转移是水到渠成的:

dp[i][j][0]=max{dp[i1][j][0],dp[i1][j][1]+a[i],dp[i][j][1]=max{dp[i1][j1][0],dp[i][j][1]+f[i]\begin{array}{ll} dp[i][j][0] = \max\left\{\begin{array}{l} dp[i-1][j][0], \\ dp[i-1][j][1] \end{array}\right. & + a[i], \\ dp[i][j][1] = \max\left\{\begin{array}{l} dp[i-1][j-1][0], \\ dp[i][j][1] \end{array}\right. & + f[i] \\ \end{array}

时间复杂度 O(n2+nlog2A)O(n^2+n\log_2A)O(n2log2A)O(n^2\log_2A)

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
// F: 数位翻转
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define endl '\n'
using namespace std;
const int MAX = 1e3+5;
const int INF = 0x3f3f3f3f3f3f3f3fll;

int f(int x) {
int res = 0;
while (x) {
res = res << 1 | x & 1;
x >>= 1;
}
return res;
}

int a[MAX];
int dp[MAX][MAX][2];

void solve() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}

for (int j = 0; j <= m; j++) {
dp[0][j][0] = -INF - 1;
dp[0][j][1] = -INF - 1;
}
dp[0][0][0] = 0;

for (int i = 1; i <= n; i++) {
const int ff = f(a[i]);
dp[i][0][0] = dp[i - 1][0][0] + a[i];
dp[i][0][1] = -INF - 1;
for (int j = 1; j <= m; j++) {
dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1]) + a[i];
dp[i][j][1] = max(dp[i - 1][j - 1][0], dp[i - 1][j][1]) + ff;
}
}

int res = 0;
for (int j = 0; j <= m; j++) {
res = max(res, max(dp[n][j][0], dp[n][j][1]));
}
cout << res << endl;
}

signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);

int t = 1;
// cin >> t;
while (t--)
solve();

return 0;
}

G 题:数星星

有多少人不会求逆元?

在一棵树上数有多少个星星结构,且这个星星节点数属于 [L, R][L,~R] ?设节点 xx 的度为 deg(x)deg(x),则以这个点为中心的有效星星为 i=L1R1(deg(x)i)\sum_{i=L-1}^{R-1}\binom{deg(x)}{i}(括号表示组合数),所以总数是:

x=1ni=L1R1(deg(x)i)(mod1e9+7)\sum_{x=1}^{n}\sum_{i=L-1}^{R-1}\binom{deg(x)}{i} \pmod{1e9+7}

比上一题简单吧,但是组合数怎么求?这不是板子嘛,没学过逆元那没办法。

时间复杂度 O(nlog2n)O(n\log_2n),使用线性递推求逆元可以做到 O(n)O(n)。因为 x=1ndeg(x)=2n2\sum_{x=1}^{n}{deg(x)}=2n-2,求和次数是 O(n)O(n) 的。

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
// 数星星
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define endl '\n'
using namespace std;
const int MAX = 2e5+5;
const int MOD = 1e9+7;

inline int quick_pow(int b, int e) {
int res = 1;
while (e) {
if (e & 1)
res = res * b % MOD;
b = b * b % MOD;
e >>= 1;
}
return res;
}
inline int inv(int x) { return quick_pow(x, MOD - 2); }

int fac[MAX];
int inf[MAX];
void load_C(int n) {
fac[0] = 1;
inf[0] = 1;
for (int i = 1; i <= n; i++) {
fac[i] = fac[i - 1] * i % MOD;
inf[i] = inf[i - 1] * inv(i) % MOD;
}
}
inline int C(int n, int m) {
if (m < 0 or m > n)
return 0;
return fac[n] * inf[m] % MOD * inf[n - m] % MOD;
}

int deg[MAX];

void solve() {
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
deg[u]++;
deg[v]++;
}
int l, r;
cin >> l >> r;
l--, r--;

int res = 0;
for (int x = 1; x <= n; x++) {
for (int i = l; i <= r; i++) {
res += C(deg[x], i);
}
}
cout << res << endl;
}

signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);

load_C(MAX - 1);

int t = 1;
// cin >> t;
while (t--)
solve();

return 0;
}

H 题:套手镯

赛时暴力解法:

O(n3)O(n^3) 的解法都能写吧,这道题占 50%50\% 的分数很划得来。

首先可以将所有手镯看成正方形,这是等价的。然后可以确定套圈的一个角一定可以属于所有正方形的边的交点,这样的交点的数量是 n2n^2 个,然后对每个可能的情况 O(n)O(n) check。

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
// H: 套手镯
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define endl '\n'
using namespace std;
const int MAX = 1e3+5;

int n, w, h;
struct Circle {
int x, y, r;
} c[MAX];

int work() {
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int cnt = 0;
int sx = c[i].x - c[i].r, sy = c[j].y - c[j].r;
int ex = sx + w, ey = sy + h;
for (int k = 0; k < n; k++) {
if (sx <= c[k].x - c[k].r and c[k].x + c[k].r <= ex and sy <= c[k].y - c[k].r and c[k].y + c[k].r <= ey) {
cnt++;
}
}
res = max(res, cnt);
}
}
return res;
}

void solve() {
cin >> n >> w >> h;
for (int i = 0; i < n; i++) {
cin >> c[i].x >> c[i].y >> c[i].r;
}

int res = work();
swap(w, h);
res = max(res, work());

cout << res << endl;
}

signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);

int t = 1;
// cin >> t;
while (t--)
solve();

return 0;
}

赛后解法:

首先我们可以将数据离散化处理。然后对于 xx 轴使用双指针维护在区间 [l, r][l,~r]xx 坐标合法索引,使用 visvis 数组标记,注意这时候只保证区间 xx 的最大最小值差(极差) 小于等于 ww,但并未保证任何 yy。对于上面的每个状态,再次使用双指针 [l, r][l',~r'] 维护在 yy 坐标上的合法索引,只是此时忽略无 vis 标记的索引,因此此时区间维护的合法索引同时满足 xxyy 的约束,此时得到的就是一种情况的计数,求它们的最大值即可。

在下面的代码中,第一维的处理为 workX 函数,第二维的处理为 workY 函数。可以看到 workX 调用 workYworkY 的区别只是多了一个 vis 的判定。总时间复杂度 O(n2)O(n^2)

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
// H: 套手镯
#include <bits/stdc++.h>
// #pragma GCC optimize(2)
#define int long long
#define endl '\n'
using namespace std;
const int MAX = 2e3+5;

int n, w, h;
struct Circle {
int x, y, r;
} c[MAX];

pair<int, int> Mx[MAX]; // {value, index}
int cntMx = 0;
pair<int, int> My[MAX]; // {value, index}
int cntMy = 0;

int res = 0;
bool vis[MAX];

void workY() {
int cnt = 0;
int r = 0, ri = My[r].second;
for (int l = 0; l < cntMy; l++) {
if (l == 0 or My[l - 1].first < My[l].first) {
while (r < cntMy and My[r].first <= My[l].first + h) {
if (vis[ri] and My[r].first > c[ri].y and My[l].first <= c[ri].y - c[ri].r and c[ri].y + c[ri].r <= My[l].first + h) {
cnt++;
}
r++, ri = My[r].second;
}
res = max(res, cnt);
}
int li = My[l].second;
if (vis[li] and My[l].first < c[li].y and My[l].first <= c[li].y - c[li].r and c[li].y + c[li].r <= My[l].first + h) {
cnt--;
}
}
}

void workX() {
int r = 0, ri = Mx[r].second;
for (int l = 0; l < cntMx; l++) {
if (l == 0 or Mx[l - 1].first < Mx[l].first) {
while (r < cntMx and Mx[r].first <= Mx[l].first + w) {
if (Mx[r].first > c[ri].x and Mx[l].first <= c[ri].x - c[ri].r and c[ri].x + c[ri].r <= Mx[l].first + w) {
vis[ri] = true;
}
r++, ri = Mx[r].second;
}
workY();
}
int li = Mx[l].second;
if (Mx[l].first < c[li].x and Mx[l].first <= c[li].x - c[li].r and c[li].x + c[li].r <= Mx[l].first + w) {
vis[li] = false;
}
}
}

void solve() {
cin >> n >> w >> h;
for (int i = 0; i < n; i++) {
cin >> c[i].x >> c[i].y >> c[i].r;
Mx[cntMx++] = {c[i].x - c[i].r, i};
Mx[cntMx++] = {c[i].x + c[i].r, i};
My[cntMy++] = {c[i].y - c[i].r, i};
My[cntMy++] = {c[i].y + c[i].r, i};
}
sort(Mx, Mx + cntMx);
sort(My, My + cntMy);

workX();
swap(w, h);
workX();

cout << res << endl;
}

signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);

int t = 1;
// cin >> t;
while (t--)
solve();

return 0;
}

I 题:跳石头

玄学剪枝:

大致思路就是玄学剪枝骗分,实在想不到什么靠谱的做法。

我的做法就是对每个可能为答案的点做搜索做完,那每个点搜索的复杂度是 O(n)O(n),当然去掉搜索重复点不然就 O(2n)O(2^n) 了。然后发现被搜索到的点不用再搜索了,例如从 11 开始搜到了 1,2,4,7,81,2,4,7,8 那这些点都不用再搜了,随机条件下可以过滤掉大量点。室友还帮忙测了如果数据是在 ci4e4c_i \le 4e4 随机的,跑得飞快;如果数据实在 ci100c_i \le 100 这样的小数值随机的,大概本地 6s6s

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
// I: 跳石头
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define endl '\n'
using namespace std;
const int MAX = 4e4+5;

int c[MAX];
bool vis[MAX];
int col[MAX];

void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> c[i];
}

int res = 0;
for (int i = 1; i <= n; i++) {
if (vis[i])
continue;
vis[i] = true;
set<int> S;
queue<int> que;
que.push(i);
while (not que.empty()) {
int x = que.front();
que.pop();
if (col[x] == i)
continue;
col[x] = i;
S.insert(c[x]);
if (x * 2 <= n)
que.push(x * 2);
if (x + c[x] <= n)
que.push(x + c[x]);
}
res = max<int>(res, S.size());
}

cout << res << endl;
}

signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);

int t = 1;
// cin >> t;
while (t--)
solve();

return 0;
}

应该是正解:

好像一个 bitset 就搞定了,刚开始看人说 bitset 还没意识过来… 仔细算了下内存,bitset 可以把所有状态存下,大概 200MB200MB。也不用暴搜剪枝什么奇技淫巧,大概后面脑子都糊了。

时间复杂度:O(n264)O(\frac{n^2}{64}),空间复杂度:O(n28)O(\frac{n^2}{8})

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
// I: 跳石头
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define endl '\n'
using namespace std;
const int MAX = 4e4+5;

int c[MAX];
bitset<MAX> bits[MAX];

void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> c[i];

int res = 0;
for (int i = n; i >= 1; i--) {
bits[i][c[i]] = 1;
if (i * 2 <= n)
bits[i] |= bits[i * 2];
if (i + c[i] <= n)
bits[i] |= bits[i + c[i]];
res = max<int>(res, bits[i].count());
}

cout << res << endl;
}

signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);

int t = 1;
// cin >> t;
while (t--)
solve();

return 0;
}

J 题:最长回文前后缀

贪心然后二分哈希。

先贪心的掐头去尾,把能匹配的匹配上了;然后读剩余的串再枚举掐掉多少的头(或者尾),对剩余部分二分哈希找到最长回文。

时间复杂度:O(nlog2n)O(n\log_2n)。感觉有希望线性解法,但是本人水平有限。

关于暴力做法就把二分哈希替换为顺序比较即可。事实上因为我哈希经常默错而且一对神秘数字的哈希不好调,赛时时间不太够就直接暴力了。反正无所谓了,前面感觉都挺稳的就随心骗了。

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
// J: 最长回文前后缀
#include <bits/stdc++.h>
// #pragma GCC optimize(2)
#define int long long
#define endl '\n'
using namespace std;
const int MAX = 5e5+5;
const int H1 = 131, H2 = 13331, M1 = 1000000007, M2 = 998244353;

typedef int HashCode;
#define mm1(x, m) ((x) % (m))
#define mm2(x, m) (((x) % (m) + (m)) % (m))

int h1[MAX], p1[MAX];
int h2[MAX], p2[MAX];
int g1[MAX];
int g2[MAX];

int hash_init = []() {
p1[0] = 1;
p2[0] = 1;
for (int i = 1; i < MAX; i++) {
p1[i] = mm1(p1[i - 1] * H1, M1);
p2[i] = mm1(p2[i - 1] * H2, M2);
}
return 0;
}();

inline void hash_it(const char *s, int n) {
h1[0] = 0;
h2[0] = 0;
for (int i = 0; i < n; i++) {
h1[i + 1] = mm1(h1[i] * H1 + s[i], M1);
h2[i + 1] = mm1(h2[i] * H2 + s[i], M2);
}
g1[n + 1] = 0;
g2[n + 1] = 0;
for (int i = n - 1; i >= 0; i--) {
g1[i + 1] = mm1(g1[i + 2] * H1 + s[i], M1);
g2[i + 1] = mm1(g2[i + 2] * H2 + s[i], M2);
}
}

template <bool reverse = false>
inline HashCode hash_sub(int l, int r) {
if (reverse) {
int s1 = mm2(g1[l + 1] - g1[r + 2] * p1[r - l + 1], M1);
int s2 = mm2(g2[l + 1] - g2[r + 2] * p2[r - l + 1], M2);
return s1 << 32 | s2;
}
int s1 = mm2(h1[r + 1] - h1[l] * p1[r - l + 1], M1);
int s2 = mm2(h2[r + 1] - h2[l] * p2[r - l + 1], M2);
return s1 << 32 | s2;
}

int work(const char *s, int n) {
int i = 0, j = n - 1;
while (i < j and s[i] == s[j]) i++, j--;

int res = 0;
hash_it(s, n);
for (int k = i; k <= j; k++) {
int l = 1, r = (j - k + 1) / 2;
while (l <= r) {
int m = (l + r) / 2;
if (hash_sub(k, k + m - 1) == hash_sub<true>(j - m + 1, j)) {
l = m + 1;
} else {
r = m - 1;
}
}
res = max(res, i + r);
}

return res;
}

void solve() {
string s;
cin >> s;
const int n = s.size();

int res = work(s.c_str(), n);
reverse(s.begin(), s.end());
res = max(res, work(s.c_str(), n));

cout << res << endl;
}

signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);

int t = 1;
// cin >> t;
while (t--)
solve();

return 0;
}

OK!结束。