QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#642640#8521. Pattern Search IIGrand_ElfWA 0ms77316kbC++171.3kb2024-10-15 15:26:312024-10-15 15:26:32

Judging History

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

  • [2024-10-15 15:26:32]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:77316kb
  • [2024-10-15 15:26:31]
  • 提交

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'