QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #738124 | #9536. Athlete Welcome Ceremony | RWeakest | WA | 1ms | 7776kb | C++17 | 2.8kb | 2024-11-12 17:48:18 | 2024-11-12 17:48:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 100;
const ll mod = 1e9 + 7;
ll n, Q;
ll na, nb, nc;
ll dp[3][310][310], nxt[3][310][310];
ll sum[310][310];
string str;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
cin >> n >> Q;
cin >> str;
str = "X" + str;
for (int i = 1; i <= n; i++) {
if (str[i] == 'a') na++;
if (str[i] == 'b') nb++;
if (str[i] == 'c') nc++;
}
if (str[1] == '?') dp[0][1][0] = dp[1][0][1] = dp[2][0][0] = 1;
if (str[1] == 'a') dp[0][1][0] = 1;
if (str[1] == 'b') dp[1][0][1] = 1;
if (str[1] == 'c') dp[2][0][0] = 1;
for (int i = 2; i <= n; i++) {
for (int a = 0; a <= i - 1; a++) {
for (int b = 0; a + b <= i - 1; b++) {
int c = i - a - b - 1;
if (str[i] == 'a') {
nxt[0][a + 1][b] += dp[1][a][b] + dp[2][a][b];
nxt[0][a + 1][b] %= mod;
}
if (str[i] == 'b') {
nxt[1][a][b + 1] += dp[0][a][b] + dp[2][a][b];
nxt[1][a][b + 1] %= mod;
}
if (str[i] == 'c') {
nxt[2][a][b] += dp[0][a][b] + dp[1][a][b];
nxt[2][a][b] %= mod;
}
if (str[i] == '?') {
nxt[0][a + 1][b] += dp[1][a][b] + dp[2][a][b];
nxt[1][a][b + 1] += dp[0][a][b] + dp[2][a][b];
nxt[2][a][b] += dp[0][a][b] + dp[1][a][b];
nxt[0][a + 1][b] %= mod;
nxt[1][a][b + 1] %= mod;
nxt[2][a][b] %= mod;
}
}
}
for (int a = 0; a <= i; a++) {
for (int b = 0; a + b <= i; b++) {
for (int k = 0; k <= 2; k++) {
dp[k][a][b] = nxt[k][a][b] % mod;
nxt[k][a][b] = 0;
}
}
}
}
for (int i = 0; i <= n; i++) {
sum[i][0] = dp[0][i][0] + dp[1][i][0] + dp[2][i][0];
for (int j = 1; j <= n; j++) {
sum[i][j] = sum[i][j - 1];
for (int l = 0; l <= 2; l++)
sum[i][j] += dp[l][i][j];
}
}
while (Q--) {
ll x, y, z;
ll ans = 0;
cin >> x >> y >> z;
x += na, y += nb, z += nc;
for (int a = na; a <= x; a++) {
if (n - z - a > y) continue;
ans += sum[a][y];
if (n - z - a - 1 >= 0) ans -= sum[a][n - z - a - 1];
}
cout << ans << "\n";
}
return 0;
}
/*
6 3
a?b??c
2 2 2
1 1 1
1 0 2
6 3
??????
2 2 2
2 3 3
3 3 3
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5932kb
input:
6 3 a?b??c 2 2 2 1 1 1 1 0 2
output:
3 1 1
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 5708kb
input:
6 3 ?????? 2 2 2 2 3 3 3 3 3
output:
30 72 96
result:
ok 3 lines
Test #3:
score: 0
Accepted
time: 1ms
memory: 5604kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 1ms
memory: 5940kb
input:
10 10 acab?cbaca 0 2 0 1 1 2 4 2 3 1 1 1 3 5 1 0 5 2 2 2 0 1 2 5 4 3 0 1 1 3
output:
0 1 1 1 1 0 1 1 1 1
result:
ok 10 lines
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 7776kb
input:
10 10 ?c?c?cbac? 10 5 1 5 8 7 9 2 6 5 7 1 5 2 6 5 6 5 5 10 3 9 1 10 2 5 9 1 2 9
output:
16 16 11 16 11 16 0 5 11 0
result:
wrong answer 7th lines differ - expected: '16', found: '0'