QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#726454	#9536. Athlete Welcome Ceremony	gt1h	TL	1946ms	207184kb	C++17	7.6kb	2024-11-09 00:54:53	2024-11-09 00:54:53

Judging History

This is the latest submission verdict.

[2024-11-09 00:54:53]
Judged

Verdict: TL
Time: 1946ms
Memory: 207184kb

Show

[2024-11-09 00:54:53]
Submitted

answer

#include<bits/stdc++.h>
#define ioss ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define int long long
using namespace std;
const int mod=1e9+7;
int n,q,x,y,z,c0,c1,c2;
int ans[155][155][155];
int dp[155][155][155][3],dpp[155][155][155][3];
string s;
inline void gin(int &x){
    x=0; int nt;
    while(!isdigit(nt=getchar())); x=nt^'0';
    while(isdigit(nt=getchar())) x=(x<<1)+(x<<3)+(nt^'0');
}
inline void prt(const int &x) {
    if(x>9) prt(x/10);
    putchar((x%10)^'0');
}
inline void f() {
    for (int i=0;i<=150;++i) {
        for (int j=0;j<=150;++j) {
            for (int k=0;k<=150;++k) {
                dp[i][j][k][0]=dp[i][j][k][1]=dp[i][j][k][2]=0;
                if (s[0]=='a') {
                    if (i>0)
                        dp[i][j][k][0]=1;
                }
                if (s[0]=='b') {
                    if (j>0)
                        dp[i][j][k][1]=1;
                }
                if (s[0]=='c') {
                    if (k>0)
                        dp[i][j][k][2]=1;
                }
                if (s[0]=='?') {
                    if (i>0)
                        dp[i][j][k][0]=1;
                    if (j>0)
                        dp[i][j][k][1]=1;
                    if (k>0)
                        dp[i][j][k][2]=1;
                }
            }
        }
    }
    dp[0][0][0][0]=dp[0][0][0][1]=dp[0][0][0][2]=0;
    int l=s.size();
    if (l==1) {
        if (s[0]=='?') {
            for (int i=0;i<=150;++i) {
                for (int j=0;j<=150;++j) {
                    for (int k=0;k<=150;++k) {
                        if (i>0)
                            ans[i][j][k]+=1;
                        if (j>0)
                            ans[i][j][k]+=1;
                        if (k>0)
                            ans[i][j][k]+=1;
                    }
                }
            }
        }
        else {
            for (int i=0;i<=150;++i) {
                for (int j=0;j<=150;++j) {
                    for (int k=0;k<=150;++k) {
                            ans[i][j][k]=1;
                    }
                }
            }
        }
        return ;
    }
    for (int x=1;x<l;++x) {
        for (int i=0;i<=150;++i) {
            for (int j=0;j<=150;++j) {
                for (int k=0;k<=150;++k) {
                    for (int c=0;c<=2;++c) {
                        dpp[i][j][k][c]=dp[i][j][k][c];
                    }
                }
            }
        }
        for (int i=0;i<=150;++i) {
            for (int j=0;j<=150;++j) {
                for (int k=0;k<=150;++k) {
                    dpp[i][j][k][0]=dpp[i][j][k][1]=dpp[i][j][k][2]=0;
                    if (s[x]=='a') {
                        if (i==0)
                            continue;
                        if (s[x-1]=='b') {
                            dpp[i][j][k][0]=dp[i-1][j][k][1];
                        }
                        if (s[x-1]=='c') {
                            dpp[i][j][k][0]=dp[i-1][j][k][2];
                        }
                        if (s[x-1]=='?') {
                            dpp[i][j][k][0]=(dp[i-1][j][k][1]+dp[i-1][j][k][2])%mod;
                        }
                    }
                    if (s[x]=='b') {
                        if (j==0)
                            continue;
                        if (s[x-1]=='a') {
                            dpp[i][j][k][1]=dp[i][j-1][k][0];
                        }
                        if (s[x-1]=='c') {
                            dpp[i][j][k][1]=dp[i][j-1][k][2];
                        }
                        if (s[x-1]=='?') {
                            dpp[i][j][k][1]=(dp[i][j-1][k][0]+dp[i][j-1][k][2])%mod;
                        }
                    }
                    if (s[x]=='c') {
                        if (k==0)
                            continue;
                        if (s[x-1]=='a') {
                            dpp[i][j][k][2]=dp[i][j][k-1][0];
                        }
                        if (s[x-1]=='b') {
                            dpp[i][j][k][2]=dp[i][j][k-1][1];
                        }
                        if (s[x-1]=='?') {
                            dpp[i][j][k][2]=(dp[i][j][k-1][0]+dp[i][j][k-1][1])%mod;
                        }
                    }
                    if (s[x]=='?') {
                        if (s[x-1]=='a') {
                            if (j>0)
                                dpp[i][j][k][1]=dp[i][j-1][k][0];
                            if (k>0)
                                dpp[i][j][k][2]=dp[i][j][k-1][0];
                        }
                        if (s[x-1]=='b') {
                            if (i>0)
                                dpp[i][j][k][0]=dp[i-1][j][k][1];
                            if (k>0)
                                dpp[i][j][k][2]=dp[i][j][k-1][1];
                        }
                        if (s[x-1]=='c') {
                            if (i>0)
                                dpp[i][j][k][0]=dp[i-1][j][k][2];
                            if (j>0)
                                dpp[i][j][k][1]=dp[i][j-1][k][2];
                        }
                        if (s[x-1]=='?') {
                            if (i>0)
                                dpp[i][j][k][0]=(dp[i-1][j][k][1]+dp[i-1][j][k][2])%mod;
                            if (j>0)
                                dpp[i][j][k][1]=(dp[i][j-1][k][0]+dp[i][j-1][k][2])%mod;
                            if (k>0)
                                dpp[i][j][k][2]=(dp[i][j][k-1][0]+dp[i][j][k-1][1])%mod;
                        }
                    }
                }
            }
        }
        for (int i=0;i<=150;++i) {
            for (int j=0;j<=150;++j) {
                for (int k=0;k<=150;++k) {
                    for (int c=0;c<=2;++c) {
                        dp[i][j][k][c]=dpp[i][j][k][c];
                    }
                }
            }
        }
    }
    for (int i=0;i<=150;++i) {
        for (int j=0;j<=150;++j) {
            for (int k=0;k<=150;++k) {
                if (s[l-1]=='a') {
                    ans[i][j][k]=dp[i][j][k][0];
                }
                if (s[l-1]=='b') {
                    ans[i][j][k]=dp[i][j][k][1];
                }
                if (s[l-1]=='c') {
                    ans[i][j][k]=dp[i][j][k][2];
                }
                if (s[l-1]=='?') {
                    if (s[l-2]=='a') {
                        ans[i][j][k]=(dp[i][j][k][1]+dp[i][j][k][2])%mod;
                    }
                    if (s[l-2]=='b') {
                        ans[i][j][k]=(dp[i][j][k][0]+dp[i][j][k][2])%mod;
                    }
                    if (s[l-2]=='c') {
                        ans[i][j][k]=(dp[i][j][k][0]+dp[i][j][k][1])%mod;
                    }
                    if (s[l-2]=='?') {
                        ans[i][j][k]=(dp[i][j][k][0]+dp[i][j][k][1]+dp[i][j][k][2])%mod;
                    }
                }
            }
        }
    }
}
signed main() {
    // ioss
    gin(n);
    gin(q);
    cin>>s;
    for (int i=0;i<s.size();++i) {
        if (s[i]=='a')
            ++c0;
        if (s[i]=='b')
            ++c1;
        if (s[i]=='c')
            ++c2;
    }
    f();
    while (q--) {
        gin(x);
        gin(y);
        gin(z);
        x+=c0;
        y+=c1;
        z+=c2;
        if (x>150)
            x=150;
        if (y>150)
            y=150;
        if (z>150)
            z=150;
        prt(ans[x][y][z]);
        putchar('\n');
    }
    return 0;
}

源文件, 语言: C++17

详细

Test #1:

score: 100

Accepted

time: 203ms

memory: 206476kb

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: 223ms

memory: 206968kb

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: 8ms

memory: 121180kb

input:

1 1
?
0 1 1

output:

result:

ok single line: '2'

Test #4:

score: 0

Accepted

time: 344ms

memory: 206540kb

input:

output:

result:

ok 10 lines

Test #5:

score: 0

Accepted

time: 363ms

memory: 206964kb

input:

output:

result:

ok 10 lines

Test #6:

score: 0

Accepted

time: 1843ms

memory: 207184kb

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: 1946ms

memory: 206544kb

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: -100

Time Limit Exceeded

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
...