QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#642640 | #8521. Pattern Search II | Grand_Elf | WA | 0ms | 77316kb | C++17 | 1.3kb | 2024-10-15 15:26:31 | 2024-10-15 15:26:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 150005;
const int C = 32;
int n, ans, len[C], pre[C][N], cntp[C][N], suf[C][N], cnts[C][N];
string s;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
len[0] = len[1] = 1;
for (int j = 2; j < C; j++) {
len[j] = len[j - 1] + len[j - 2];
}
cin >> s;
n = s.size();
for (int i = 0; i < n; i++) {
pre[0][i] = suf[0][i] = s[i] == 'b';
cntp[0][i] = cnts[0][i] = 1;
pre[1][i] = suf[1][i] = s[i] == 'a';
cntp[1][i] = cnts[1][i] = 1;
}
ans = 0x3f3f3f3f;
for (int j = 2; j < C; j++) {
for (int i = 0; i < n; i++) {
if (pre[j - 2][i] == i + 1) {
pre[j][i] = pre[j - 2][i];
cntp[j][i] = cntp[j - 2][i];
} else {
pre[j][i] = pre[j - 2][i] + pre[j - 1][i - pre[j - 2][i]];
cntp[j][i] = len[j - 2] + cntp[j - 1][i - pre[j - 2][i]];
}
if (suf[j - 1][i] == n - i) {
suf[j][i] = suf[j - 1][i];
cnts[j][i] = cnts[j - 1][i];
} else {
suf[j][i] = suf[j - 1][i] + suf[j - 2][i + suf[j - 1][i]];
cnts[j][i] = len[j - 1] + cnts[j - 2][i + suf[j - 1][i]];
}
}
for (int i = 0; i + 1 < n; i++) {
if (pre[j - 1][i] == i + 1 && suf[j - 2][i + 1] == n - i - 1) {
ans = min(ans, cntp[j - 1][i] + cnts[j - 2][i + 1]);
}
}
}
cout << ans << '\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 77316kb
input:
aabbaab
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 75340kb
input:
a
output:
1061109567
result:
wrong answer 1st numbers differ - expected: '1', found: '1061109567'