QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#136367 | #5440. P-P-Palindrome | savacska | WA | 178ms | 46464kb | C++23 | 2.9kb | 2023-08-08 05:22:25 | 2023-08-08 05:22:25 |
Judging History
answer
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = 998244353;
const int P = 73;
const int MAXLEN = 1000000;
int hashs[MAXLEN + 5], step[MAXLEN + 5];
int man_even[MAXLEN + 5], man_odd[MAXLEN + 5];
int open[MAXLEN + 5], period[MAXLEN + 5];
vector <int> spis[MAXLEN + 5];
map <int, int> max_occur;
int get_hash(int lef, int rig)
{
return (hashs[rig] - (ll) hashs[lef - 1] * step[rig - lef + 1] % MOD + MOD) % MOD;
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
int test;
cin >> test;
step[0] = 1;
for (int i = 1; i <= MAXLEN; i++) step[i] = (ll) step[i - 1] * P % MOD;
for (int rep = 1; rep <= test; rep++)
{
string s;
cin >> s;
int n = (int) s.length();
for (int i = 1; i <= n; i++)
hashs[i] = ((ll) hashs[i - 1] * P + s[i - 1] - 'a' + 1) % MOD;
for (int i = 1; i <= n; i++) open[i] = 0;
{
int lef = 0, rig = 0;
for (int i = 1; i < n; i++)
{
int len = 0;
if (rig > i) len = min(rig - i, man_even[lef + rig - i - 1]);
while (i - len - 1 >= 0 && i + len < n && s[i - len - 1] == s[i + len]) len++;
man_even[i] = len;
if (i + len > rig) rig = i + len, lef = i - len + 1;
}
for (int i = 1; i < n; i++)
if (man_even[i] != 0) open[i - man_even[i] + 1] = max(open[i - man_even[i] + 1], i + man_even[i]);
}
{
int lef = 0, rig = 0;
for (int i = 1; i <= n; i++)
{
int len = 0;
if (rig > i) len = min(rig - i, man_odd[lef + rig - i]);
while (i - len - 2 >= 0 && i + len < n && s[i - len - 2] == s[i + len]) len++;
man_odd[i] = len;
if (i + len > rig) rig = i + len, lef = i - len;
}
for (int i = 1; i <= n; i++)
open[i - man_odd[i]] = max(open[i - man_odd[i]], i + man_odd[i]);
}
for (int i = 1; i <= n; i++)
open[i] = max(open[i], open[i - 1] - 1);
for (int i = 1; i <= n; i++) spis[i].clear(), period[i] = 0;
for (int i = 1; i <= n; i++)
spis[open[i] - i + 1].pb(i);
for (int del = 1; del <= n; del++)
for (int kr = del; kr <= n; kr += del)
for (int num : spis[kr])
{
if (period[num] != 0) continue;
if (get_hash(num, num + kr - 1 - del) == get_hash(num + del, num + kr - 1)) period[num] = del;
}
for (int i = 1; i <= n; i++)
{
int hs = get_hash(i, i + period[i] - 1);
int mx = max(max_occur[hs], (open[i] - i + 1) / period[i]);
max_occur[hs] = mx;
}
}
ll ans = 0;
for (const auto &[str, kol] : max_occur) ans += (ll) kol * kol;
cout << ans << '\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 37800kb
input:
2 aaaa aaa
output:
16
result:
ok 1 number(s): "16"
Test #2:
score: 0
Accepted
time: 6ms
memory: 35372kb
input:
3 abaaa abbbba bbbaba
output:
28
result:
ok 1 number(s): "28"
Test #3:
score: 0
Accepted
time: 8ms
memory: 34548kb
input:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
output:
15130
result:
ok 1 number(s): "15130"
Test #4:
score: 0
Accepted
time: 6ms
memory: 30944kb
input:
3 aaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbb bababababababaabababababa
output:
1282
result:
ok 1 number(s): "1282"
Test #5:
score: 0
Accepted
time: 37ms
memory: 36108kb
input:
5 ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...
output:
3600000000
result:
ok 1 number(s): "3600000000"
Test #6:
score: 0
Accepted
time: 29ms
memory: 37940kb
input:
5 wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
3600000000
result:
ok 1 number(s): "3600000000"
Test #7:
score: -100
Wrong Answer
time: 178ms
memory: 46464kb
input:
3 abbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbab...
output:
133575
result:
wrong answer 1st numbers differ - expected: '133586', found: '133575'