QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#856278#6218. 扭动的回文串LaDeX100 ✓51ms7856kbC++171.9kb2025-01-13 20:22:272025-01-13 20:22:29

Judging History

你现在查看的是最新测评结果

  • [2025-01-13 20:22:29]
  • 评测
  • 测评结果:100
  • 用时:51ms
  • 内存:7856kb
  • [2025-01-13 20:22:27]
  • 提交

answer

#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N = 1e5 + 10;
const ull P = 1145141;
int n; char S[N], T[N];
ull hsh1[N], hsh2[N], hsh3[N], hsh4[N], base[N];
ull H2(int tp, int l, int r) {
	if (tp == 1) return hsh1[r] - hsh1[l - 1] * base[r - l + 1];
	return hsh2[r] - hsh2[l - 1] * base[r - l + 1];
}
ull H1(int tp, int l, int r) {
	if (tp == 1) return hsh3[l] - hsh3[r + 1] * base[r - l + 1];
	return hsh4[l] - hsh4[r + 1] * base[r - l + 1];
}
int Solve(int k1, int s, int k2, int t) {
	int L = 0, R = min(s, n - t + 1);
	while (L + 1 < R) {
		int mid = (L + R) >> 1;
		if (H1(k1, s - mid + 1, s) == H2(k2, t, t + mid - 1)) L = mid;
		else R = mid;
	}
	if (H1(k1, s - R + 1, s) == H2(k2, t, t + R - 1)) return R;
	return L;
}
int main() {
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> (S + 1) >> (T + 1);
	base[0] = 1;
	for (int i = 1; i <= n; i ++) base[i] = base[i - 1] * P;
	for (int i = 1; i <= n; i ++) hsh1[i] = hsh1[i - 1] * P + S[i];
	for (int i = 1; i <= n; i ++) hsh2[i] = hsh2[i - 1] * P + T[i];
	for (int i = n; i >= 1; i --) hsh3[i] = hsh3[i + 1] * P + S[i];
	for (int i = n; i >= 1; i --) hsh4[i] = hsh4[i + 1] * P + T[i];
	int Ans = 1;
	for (int i = 1; i <= n; i ++) {
		int even = Solve(1, i, 1, i + 1), odd = Solve(1, i, 1, i);
		Ans = max(Ans, even * 2);
		Ans = max(Ans, odd * 2 - 1);
		Ans = max(Ans, Solve(1, i - even, 2, i + even) * 2 + even * 2);
		Ans = max(Ans, Solve(1, i - odd, 2, i + odd - 1) * 2 + odd * 2 - 1);
	}
	for (int i = 1; i <= n; i ++) {
		int even = Solve(2, i, 2, i + 1), odd = Solve(2, i, 2, i);
		Ans = max(Ans, even * 2);
		Ans = max(Ans, odd * 2 - 1);
		Ans = max(Ans, Solve(1, i - even + 1, 2, i + even + 1) * 2 + even * 2);
		Ans = max(Ans, Solve(1, i - odd + 1, 2, i + odd) * 2 + odd * 2 - 1);
	}
	for (int i = 1; i <= n; i ++)
		Ans = max(Ans, Solve(1, i, 2, i) * 2);
	cout << Ans;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 1ms
memory: 3584kb

input:

30
AABABAAAAABBBAAAAAABBAABAABABA
AAAAAAABABBAAAAAABABAAAABAAAAB

output:

23

result:

ok single line: '23'

Test #2:

score: 10
Accepted
time: 1ms
memory: 3712kb

input:

200
ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAAB
ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAABBAAAAAAAABAAAAAAAAABAAAAAAAAAAAAAAAA...

output:

75

result:

ok single line: '75'

Test #3:

score: 10
Accepted
time: 0ms
memory: 5728kb

input:

200
AABAAAAAAAAAAAAAAAAAAAAABAAAAABAAABAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAABABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABABAAAAAAAABAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAABAAAAAAAAABBAAAAABAAAAAAAAAAAAAABAAAAABAAAAABBAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

117

result:

ok single line: '117'

Test #4:

score: 10
Accepted
time: 0ms
memory: 5864kb

input:

2000
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAA...

output:

429

result:

ok single line: '429'

Test #5:

score: 10
Accepted
time: 0ms
memory: 3840kb

input:

2000
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAA...

output:

660

result:

ok single line: '660'

Test #6:

score: 10
Accepted
time: 48ms
memory: 7740kb

input:

100000
ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

10486

result:

ok single line: '10486'

Test #7:

score: 10
Accepted
time: 50ms
memory: 7856kb

input:

100000
ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

16715

result:

ok single line: '16715'

Test #8:

score: 10
Accepted
time: 47ms
memory: 7680kb

input:

100000
ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

50035

result:

ok single line: '50035'

Test #9:

score: 10
Accepted
time: 51ms
memory: 7632kb

input:

100000
ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

20929

result:

ok single line: '20929'

Test #10:

score: 10
Accepted
time: 48ms
memory: 7808kb

input:

100000
ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

40448

result:

ok single line: '40448'