QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #723399 | #9463. 基础 ABC 练习题 | hhoppitree | 0 | 0ms | 0kb | C++17 | 2.3kb | 2024-11-07 22:06:06 | 2024-11-07 22:06:06 |
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 75;
unsigned int f[2][N][N][4];
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][(!l1) | ((!l2) << 1)] = 1;
for (int k = 1; k <= n * 3; ++k) {
memset(f[k & 1], 0, sizeof(f[k & 1]));
for (int p = 0; p < k && p <= n; ++p) {
for (int q = 0; p + q <= k && q <= n; ++q) {
int r = k - 1 - p - q;
if (r < 0 || r > n) continue;
for (int a = 0; a < 4; ++a) {
unsigned int v = f[(k & 1) ^ 1][p][q][a];
if (!v) continue;
if ((S[k] == '?' || S[k] == 'A') && p - r + 1 <= r1) {
f[k & 1][p + 1][q][a | (p - r + 1 >= l1)] += v;
}
if ((S[k] == '?' || S[k] == 'B') && q - p + 1 <= r2) {
f[k & 1][p][q + 1][a | ((q - p + 1 >= l2) << 1)] += v;
}
if ((S[k] == '?' || S[k] == 'C') && r - q + 1 <= r3) {
f[k & 1][p][q][a] += v;
}
}
}
}
}
res += f[n & 1][n][n][3];
}
}
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%