QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#747544	#9536. Athlete Welcome Ceremony	ucup-team1412	WA	290ms	589628kb	C++23	4.6kb	2024-11-14 17:28:14	2024-11-14 17:28:14

Judging History

This is the latest submission verdict.

[2024-11-14 17:28:14]
Judged

Verdict: WA
Time: 290ms
Memory: 589628kb

Show

[2024-11-14 17:28:14]
Submitted

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const ll p = 1e9 + 7;
const ll MAXN = 301;
ll dp[MAXN][MAXN][MAXN][4];
ll g[MAXN][MAXN][MAXN];

ll n, q;
string c;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    cin >> c;
    string s = "0" + c;

    ll cnt = 0;
    ll cnta = 0, cntb = 0, cntc = 0;


    for (ll i = 1; i <= n; i++) {
        if (s[i] == '?') cnt++;
        if (s[i] == 'a') cnta++;
        if (s[i] == 'b') cntb++;
        if (s[i] == 'c') cntc++;
        if (i == 1) {
            if (s[i] == 'a') {
                dp[1][0][0][1] = 1;
            }
            else if (s[i] == 'b') {
                dp[0][1][0][2] = 1;
            }
            else if (s[i] == 'c') {
                dp[0][0][1][3] = 1;
            }
            else {
                dp[1][0][0][1] = 1;
                dp[0][1][0][2] = 1;
                dp[0][0][1][3] = 1;
            }
        }
        else {
            for (ll a = 0; a <= i; a++) {
                for (ll b = 0; a + b <= i; b++) {
                    if (s[i] == 'a') {
                        if (a != 0) {
                            dp[a][b][i - a - b][1] = dp[a - 1][b][i - a - b][2] + dp[a - 1][b][i - a - b][3];
                            dp[a][b][i - a - b][1] %= p;
                        }

                    }
                    else if (s[i] == 'b') {
                        if (b != 0) {
                            dp[a][b][i - a - b][2] = dp[a][b - 1][i - a - b][1] + dp[a][b - 1][i - a - b][3];
                            dp[a][b][i - a - b][2] %= p;
                        }

                    }
                    else if (s[i] == 'c') {
                        if (i - a - b != 0) {
                            dp[a][b][i - a - b][3] = dp[a][b][i - a - b - 1][1] + dp[a][b][i - a - b - 1][2];
                            dp[a][b][i - a - b][3] %= p;
                        }
                    }
                    else {
                        if (a != 0) {
                            dp[a][b][i - a - b][1] = dp[a - 1][b][i - a - b][2] + dp[a - 1][b][i - a - b][3];
                            dp[a][b][i - a - b][1] %= p;
                        }
                        if (b != 0) {
                            dp[a][b][i - a - b][2] = dp[a][b - 1][i - a - b][1] + dp[a][b - 1][i - a - b][3];
                            dp[a][b][i - a - b][2] %= p;
                        }
                        if (i - a - b != 0) {
                            dp[a][b][i - a - b][3] = dp[a][b][i - a - b - 1][1] + dp[a][b][i - a - b - 1][2];
                            dp[a][b][i - a - b][3] %= p;
                        }
                    }
                }
            }
        }

    }
    // cout << dp[1][1][1][1] + dp[1][1][1][2] + dp[1][1][1][3];
    // for (ll x = 1; x <= n + 1; x++) {
    //     for (ll y = 1; y <= n + 1; y++) {
    //         for (ll z = 1; z <= n + 1; z++) {
    //             if (x + y + z > n + 3) break;
    //             g[x][y][z] = g[x - 1][y][z] + g[x][y - 1][z] + g[x][y][z - 1] - g[x][y - 1][z - 1] - g[x - 1][y][z - 1] - g[x - 1][y - 1][z] + g[x - 1][y - 1][z - 1];
    //             g[x][y][z] %= p;
    //             if (x + y + z == n + 3) {
    //                 g[x][y][z] += (dp[x][y][z][1] + dp[x][y][z][2] + dp[x][y][z][3]) % p;
    //                 g[x][y][z] %= p;
    //             }
    //         }
    //     }
    // }
    // for (ll i = 0; i <= n; i++) {
    //     for (ll j = 0; j <= n; j++) {
    //         for (ll k = 1; k <= 3; k++) {
    //             g[i+1][j+1][n-i-j+1]+=dp[]
    //         }
    //     }
    // }

    for (ll i = 1; i <= n + 1; i++) {
        for (ll j = 1; j <= n + 1; j++) {
            for (ll k = 1; k <= n + 1; k++) {
                g[i][j][k] = g[i - 1][j][k] + g[i][j - 1][k] + g[i][j][k - 1] - g[i - 1][j - 1][k] - g[i - 1][j][k - 1] - g[i][j - 1][k - 1] + g[i - 1][j - 1][k - 1];
                g[i][j][k] %= p;
                if (i + j + k == n + 3) {
                    ll now = 0;
                    for (ll t = 1; t <= 3; t++) {
                        now += dp[i - 1][j - 1][k - 1][t];
                    }
                    g[i][j][k] += now;
                    g[i][j][k] %= p;
                }
                g[i][j][k] = (g[i][j][k] + p) % p;
            }
        }
    }

    while (q--) {
        ll a, b, c;
        cin >> a >> b >> c;
        a = min(cnt, a);
        b = min(cnt, b);
        c = min(cnt, c);
        cout << g[a + cnta + 1][b + cntb + 1][c + cntc + 1] << endl;
    }

    return 0;
}

源文件, 语言: C++23

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 14148kb

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: 18064kb

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: 7636kb

input:

1 1
?
0 1 1

output:

result:

ok single line: '2'

Test #4:

score: 0

Accepted

time: 0ms

memory: 22332kb

input:

output:

result:

ok 10 lines

Test #5:

score: 0

Accepted

time: 0ms

memory: 24288kb

input:

output:

result:

ok 10 lines

Test #6:

score: 0

Accepted

time: 0ms

memory: 99020kb

input:

50 100
?abacbacab?cbcbcb?acabcbabcbcacbababc?caba?acacbca
8 3 8
2 4 8
8 7 3
0 9 2
10 8 7
7 6 5
4 10 2
6 9 3
3 6 6
9 10 8
2 5 8
8 1 0
3 5 0
1 0 6
5 0 8
6 5 5
1 7 9
7 7 10
4 7 5
6 6 4
10 1 2
4 1 7
10 0 8
7 6 3
1 9 1
4 7 2
8 4 0
8 6 1
5 10 4
5 8 2
5 8 4
4 5 9
5 2 1
1 10 9
4 10 1
8 4 3
8 9 9
8 0 1
0 8 0...

output:

result:

ok 100 lines

Test #7:

score: 0

Accepted

time: 0ms

memory: 120568kb

input:

50 100
b????????bca?????c?b??ca?acac?b?b???ca?ab???a?a???
35 43 36
12 49 47
7 11 34
38 44 22
42 17 10
49 8 38
18 26 44
6 18 14
28 29 6
48 32 47
29 15 48
1 5 33
24 17 18
10 27 32
19 10 34
2 23 9
14 24 39
46 12 34
9 49 26
21 8 46
43 43 3
31 16 2
8 27 7
24 41 35
17 25 31
0 13 47
24 31 23
33 40 30
36 39...

output:

result:

ok 100 lines

Test #8:

score: 0

Accepted

time: 16ms

memory: 148616kb

input:

100 1000
c?cbababcabacbacbacacbacabcbabababacababcbcab?cbabacbacbcbcacbab?bcabcbcababcacbabacbcb?babcbab?baca
13 11 4
4 17 20
14 5 2
16 14 15
8 12 17
19 5 11
5 17 12
20 7 6
19 10 1
6 5 0
13 1 9
7 17 1
20 4 16
11 12 18
19 2 16
18 1 11
19 16 3
7 1 0
6 9 16
6 9 16
6 20 7
0 16 20
1 2 8
16 5 20
18 14 18
...

output:

result:

ok 1000 lines

Test #9:

score: 0

Accepted

time: 3ms

memory: 186900kb

input:

100 1000
?????c??????????????????????????b???a????a?????????????????????????c????????????????????????????????
43 38 20
27 40 32
39 27 33
28 50 43
50 3 46
38 46 14
42 48 10
45 25 28
49 10 49
38 17 42
41 49 22
41 18 44
46 47 25
17 44 35
34 43 22
47 42 32
32 44 40
36 41 24
45 38 45
49 44 18
42 34 32
43...

output:

result:

ok 1000 lines

Test #10:

score: 0

Accepted

time: 11ms

memory: 189068kb

input:

100 1000
c???cacacbcab?cb?acb???ac?bab?bcbcbc?c?bcbcaba??b?ba?c?aca?a?bac?cbcbcba??ca?b????ac?baba?ab?cba?c?c
99 70 32
52 98 84
12 78 77
84 8 87
16 36 0
48 70 100
25 4 15
95 54 35
33 35 90
20 4 69
6 11 76
27 96 48
16 24 18
99 48 1
43 54 35
9 81 75
27 58 52
50 94 14
29 67 27
59 68 53
42 31 46
12 90 2...

output:

result:

ok 1000 lines

Test #11:

score: -100

Wrong Answer

time: 290ms

memory: 589628kb

input:

300 100000
abcacacbabacbcababcacacb?babacbcbacbcababcbcbabcacbcbacacabacacacbacbcbcacbabacbcbcbabcacbababcabcabcabababacbcacbacabcbacbacacacbababababacbcababcbcacacbcbabacabcabababcabacbcbcbabcabacbabacacbcbcacacacbcabcbabcbcabababababcacabcabababcbcbcbcbcabacbabacbabcacbcababacacbcbababababcacacaba...

output:

result:

wrong answer 1st lines differ - expected: '1', found: '305'