QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #723251 | #9463. 基础 ABC 练习题 | hhoppitree | 0 | 0ms | 0kb | C++17 | 2.2kb | 2024-11-07 21:35:44 | 2024-11-07 21:35:49 |
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 65;
unsigned int f[2][N][N][2][2];
signed main() {
int T; scanf("%d%*d", &T);
while (T--) {
int n; scanf("%d", &n);
string S1, S2; cin >> S1 >> S2;
vector<int> o1, o2;
for (int i = 0; i <= n; ++i) {
if (S1[i] == '1') o1.push_back(i);
if (S2[i] == '1') o2.push_back(i);
}
string S; cin >> S, S = ' ' + S;
if (n != 60) {
puts("-1");
continue;
}
unsigned int res = 0;
for (int i = 0; i < (int)o1.size(); ++i) {
for (int j = 0; j < (int)o2.size(); ++j) {
int l1 = (!i ? 0 : o1[i - 1] + 1), r1 = o1[i],
l2 = (!j ? 0 : o2[j - 1] + 1), r2 = o2[j], r3 = n - r1 - r2;
if (r3 < 0) continue;
memset(f[0], 0, sizeof(f[0]));
f[0][0][0][0 >= l1][0 >= l2] = 1;
for (int k = 1; k <= n * 3; ++k) {
memset(f[k & 1], 0, sizeof(f[k & 1]));
for (int p = 0; p <= n; ++p) {
for (int q = 0; q <= n; ++q) {
int r = k - 1 - p - q;
if (r < 0 || r > n) continue;
for (int a = 0; a < 2; ++a) {
for (int b = 0; b < 2; ++b) {
for (int c = 0; c < 3; ++c) {
if ((S[k] != '?' && S[k] != "ABC"[c]) || !f[(k & 1) ^ 1][p][q][a][b]) continue;
int tp = p + (c == 0), tq = q + (c == 1), tr = r + (c == 2);
if (tp - tr <= r1 && tq - tp <= r2 && tr - tq <= r3) {
f[k & 1][tp][tq][a || (tp - tr >= l1)][b || (tq - tp >= l2)] += f[(k & 1) ^ 1][p][q][a][b];
}
}
}
}
}
}
}
res += f[n & 1][n][n][1][1];
}
}
printf("%u\n", res);
}
return 0;
}
詳細信息
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
input:
60 1 1 11 11 ABC 2 111 111 CABABC 3 1111 1111 CAABBCBAC 4 11111 11111 BACBBACBACAC 5 111111 111111 CABCCBBAABCCBAA 6 1111111 1111111 ABABABCACBCBCCACBA 7 11111111 11111111 BCAABACBBCBBABCCAACAC 8 111111111 111111111 CCBCBBBCAABCBCAAAAACBCBA 9 1111111111 1111111111 CCCCACABCBABAABCCAABABBCBBA 10 1111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Time Limit Exceeded
Test #22:
score: 0
Time Limit Exceeded
input:
60 3 1 11 11 ??? 2 111 111 ?????? 3 1111 1111 ????????? 4 11111 11111 ???????????? 5 111111 111111 ??????????????? 6 1111111 1111111 ?????????????????? 7 11111111 11111111 ????????????????????? 8 111111111 111111111 ???????????????????????? 9 1111111111 1111111111 ??????????????????????????? 10 1111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%