QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#737755#9536. Athlete Welcome Ceremonyucup-team1412WA 1556ms696900kbC++143.2kb2024-11-12 16:47:222024-11-12 16:47:22

Judging History

This is the latest submission verdict.

  • [2024-11-12 16:47:22]
  • Judged
  • Verdict: WA
  • Time: 1556ms
  • Memory: 696900kb
Show
  • [2024-11-12 16:47:22]
  • Submitted

answer

//https://contest.ucup.ac/contest/1821/problem/9536?v=1
//f[i][x][y][p] : 考虑前i个字符，使用j个a，k个b，并且最后一个字符是p
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn = 305;
ll n , q;
string c, s;
ll f[maxn][maxn][maxn][3];
ll g[maxn][maxn][maxn];
ll cnt[3];
const ll mod = 1e9 + 7;
signed main(){
    cin >> n >> q;
    cin >> c;
    s = "0";
    s += c;

    for(ll i = 1 ; i <= n;i++){
        if(s[i]!='?')cnt[ (ll)(s[i] - 'a') ]++; 
    }


    if(s[1] == '?'){
        f[1][2][1][0] = 1;
        f[1][1][2][1] = 1;
        f[1][1][1][2] = 1;

    }
    else{
        if(s[1] == 'a')f[1][2][1][0] = 1;
        if(s[1] == 'b')f[1][1][2][1] = 1;
        if(s[1] == 'c')f[1][1][1][2] = 1;
    }

    for(ll i = 2; i <= n ;i ++){
        for(ll x = 1 ; x <= i + 1 ; x++){
            for(ll y = 1 ; x + y <= i + 2; y++ ){
                // cout <<  "fdassdas" << endl;
                ll z = i + 3 - x - y;

                if(s[i] != '?'){
                    if(s[i] == 'a' && x >= 1){
                        //f[1][2][1][0]
                        f[i][x][y][0] = ( f[i - 1][x - 1][y][1] + f[i - 1][x - 1][y][2]+ mod) % mod ;
                    }
                    else if ( s[i] == 'b' && y >= 1 ){
                        f[i][x][y][1] = (f[i - 1][x][y - 1][0] + f[i - 1][x][y - 1][2]+ mod)% mod ;
                    }
                    else if ( s[i] == 'c' && z >= 1 ){
                        f[i][x][y][2] = (f[i - 1][x][y][0] + f[i - 1][x][y][1] + mod) % mod;
                    }
                }
                else{
                    if(s[i - 1] != 'a' && x >= 1  ){//can select a
                        f[i][x][y][0] = (  f[i - 1][x - 1][y][1] + f[i - 1][x - 1][y][2]+ mod) % mod;
                    }
                    if(s[i - 1] != 'b' && y >= 1){//can select b
                        f[i][x][y][1] = (f[i - 1][x][y - 1][0]  + f[i - 1][x][y - 1][2]+ mod) % mod;
                    }
                    if(s[i - 1] != 'c' && z >= 1){//can select c
                        f[i][x][y][2] = (f[i - 1][x][y][0] + f[i - 1][x][y][1] + mod) % mod;
                    }
                }


            }
        }
    }


    // cout << f[13][5][6][2] << endl;
    for(ll x = 1 ; x <= 2 * n + 10; x++){
        for(ll y = 1 ;y <= 2 * n + 10; y++){
            for(ll z = 1 ; z <= 2 * n + 10 ; z++){

                ll res = 0;
                for(ll  i = 0 ; i <= 2 ; i++){
                    res = ( res + f[n][x][y][i] + mod)% mod;
                }
                // cout << res << endl;

                g[x][y][z] = (g[x-1][y][z] + g[x][y-1][z] + g[x][y][z-1] - g[x-1][y-1][z]-g[x-1][y][z-1]-g[x][y-1][z-1] + g[x-1][y-1][z-1] + mod)%mod;
                if(x + y + z == n + 3){
                    g[x][y][z] = (g[x][y][z] + res + mod) % mod;
                }
                // cout << g[x][y][z] << endl;
            }



        }
    }

    while(q--){
        ll x,y,z;
        cin >> x >> y >> z;
        ll ans = g[x + 1 + cnt[0] ][y + 1 + cnt[1] ][z + 1 + cnt[2] ] % mod;
        cout << (ans >= 0 ? ans : mod + ans )<< endl;
    }


    return 0;
}
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 17124kb

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

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: 0ms
memory: 6060kb

input:

1 1
?
0 1 1

output:

2

result:

ok single line: '2'

Test #4:

score: 0
Accepted
time: 0ms
memory: 26260kb

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: 0
Accepted
time: 0ms
memory: 28184kb

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
16
5
11
0

result:

ok 10 lines

Test #6:

score: 0
Accepted
time: 12ms
memory: 68648kb

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:

8
8
8
0
8
8
6
8
8
8
8
0
0
0
1
8
4
8
8
8
2
4
1
8
1
6
0
2
8
6
8
8
1
4
2
8
8
0
0
8
2
0
8
8
8
4
8
8
8
8
2
0
0
4
8
8
1
8
7
6
7
0
8
8
8
0
4
7
8
4
0
8
0
4
8
8
8
7
8
4
7
2
8
8
8
0
2
2
8
8
8
4
4
0
8
0
8
8
1
1

result:

ok 100 lines

Test #7:

score: 0
Accepted
time: 24ms
memory: 66756kb

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:

34272000
31599360
497244
34272000
17637520
12290752
34272000
93044
415832
34272000
34272000
0
34272000
16360704
27933952
0
34272000
33886976
7896832
12290752
718
24
0
34272000
34272000
0
34272000
34272000
34272000
32254720
0
5666944
34256640
34272000
34272000
12290752
30493248
34256640
20630016
0
10...

result:

ok 100 lines

Test #8:

score: 0
Accepted
time: 64ms
memory: 162256kb

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:

16
15
14
16
16
16
16
16
8
2
16
8
16
16
16
16
16
2
16
16
16
0
1
16
16
5
1
5
16
16
16
16
16
15
16
13
16
15
2
16
16
1
8
16
16
16
15
0
16
15
16
16
16
16
8
8
16
16
16
16
16
16
8
16
16
1
8
8
16
16
1
16
1
0
16
2
2
16
7
16
16
8
16
16
16
16
1
16
14
16
16
16
16
5
16
16
14
16
11
16
15
11
2
1
8
16
16
7
16
5
16
...

result:

ok 1000 lines

Test #9:

score: 0
Accepted
time: 63ms
memory: 174132kb

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:

490475656
143989836
119661929
707864467
10104
219100551
479284703
764218529
903846231
659694548
204287063
105920502
191779504
182802705
215438611
938692318
797581204
903917420
893995828
287222624
578695829
95654849
457810426
709349795
85961844
923330494
783007506
111119718
295402274
241594071
551680...

result:

ok 1000 lines

Test #10:

score: 0
Accepted
time: 89ms
memory: 180712kb

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:

380160
380160
226896
64156
0
380160
92
380160
380160
92
0
380160
379648
0
380160
22500
380160
380160
380160
380160
380160
226896
380160
380160
226896
0
380160
380160
380160
380160
152672
380160
5624
226896
380160
380160
379648
0
380160
380160
366848
380160
226896
380160
92
374912
5624
380160
380160
...

result:

ok 1000 lines

Test #11:

score: -100
Wrong Answer
time: 1556ms
memory: 696900kb

input:

300 100000
abcacacbabacbcababcacacb?babacbcbacbcababcbcbabcacbcbacacabacacacbacbcbcacbabacbcbcbabcacbababcabcabcabababacbcacbacabcbacbacacacbababababacbcababcbcacacbcbabacabcabababcabacbcbcbabcabacbabacacbcbcacacacbcabcbabcbcabababababcacabcabababcbcbcbcbcabacbabacbabcacbcababacacbcbababababcacacaba...

output:

2811
15065
7669
2822
7735
24866
320
4961
326
11084
1257
5
30689
11058
11006
11123
338
1245
14960
30731
1235
2755
4907
24914
11032
4907
2773
4907
19639
11032
2752
19554
11019
9
24904
30605
4889
1270
1272
11077
14975
11097
4934
338
2801
11019
1250
30710
24895
30563
7691
19690
320
19656
19656
24733
195...

result:

wrong answer 1st lines differ - expected: '1', found: '2811'
English 繁體中文 简体中文

服务器时间: 2025-02-07 02:27:02 | 开源项目