QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#218356 | #2927. Bracket Pairing | ucup-team1004 | AC ✓ | 0ms | 3824kb | C++14 | 991b | 2023-10-18 08:16:09 | 2023-10-18 08:16:09 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
if(x.empty())return out<<"[]";
out<<'['<<x[0];
for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
cerr<<x<<' ',debug(y...);
}
const int N=22;
int n;
ll f[N][N];
char a[N],str[10]="[]<>{}()";
int main(){
scanf("%s",a+1),n=strlen(a+1);
for(int i=1;i<=n+1;i++)f[i][i-1]=1;
for(int l=n;l>=1;l--){
for(int r=l;r<=n;r++){
if((r-l+1)%2)continue;
for(int i=0;i<8;i+=2){
if(a[l]!=str[i]&&a[l]!='?')continue;
for(int j=l+1;j<=r;j++){
if(a[j]!=str[i+1]&&a[j]!='?')continue;
f[l][r]+=f[l+1][j-1]*f[j+1][r];
}
}
}
}
cout<<f[1][n]<<endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3604kb
input:
??
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
????
output:
32
result:
ok single line: '32'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
????????
output:
3584
result:
ok single line: '3584'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
]????]
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
?????[
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
([???]
output:
1
result:
ok single line: '1'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
??({?]
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
??({?]??
output:
4
result:
ok single line: '4'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
?[()?)()]]
output:
1
result:
ok single line: '1'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
?()?????
output:
320
result:
ok single line: '320'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
?????()?
output:
320
result:
ok single line: '320'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
???([]){}???
output:
320
result:
ok single line: '320'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
????????????????????
output:
17611882496
result:
ok single line: '17611882496'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
<{[{()}]}<>{}>{?()[]
output:
1
result:
ok single line: '1'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
[<{}<><?[]>?[]{}<{}>
output:
1
result:
ok single line: '1'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
()<{}{}><???[]>>[()]
output:
9
result:
ok single line: '9'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
([{?}}<??){<>}[?}<>]
output:
1
result:
ok single line: '1'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
{}(?(?()[]??]<>){[]?
output:
21
result:
ok single line: '21'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
<??>]??{{}[]}>>()?{}
output:
1
result:
ok single line: '1'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
{???{(({?><>?>})){}}
output:
8
result:
ok single line: '8'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
?<()[]?<{?>??>>())[]
output:
11
result:
ok single line: '11'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
?[()?)()][]{[?}>?]{?
output:
1
result:
ok single line: '1'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
{?(?>)<>>{}<?{}}?]{?
output:
1
result:
ok single line: '1'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
[?}[[???[??????]??>?
output:
34880
result:
ok single line: '34880'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
??<???????<>??[??]{?
output:
629760
result:
ok single line: '629760'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
?????????[?)?}?>[???
output:
889856
result:
ok single line: '889856'
Test #27:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
????????????}(??????
output:
275382272
result:
ok single line: '275382272'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
?[??]?{??)??????????
output:
8609792
result:
ok single line: '8609792'
Test #29:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
???????(??)??{?????>
output:
16621568
result:
ok single line: '16621568'
Test #30:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
????[]?[<???????????
output:
21446656
result:
ok single line: '21446656'
Test #31:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
???????}>??????)?)??
output:
4677632
result:
ok single line: '4677632'
Test #32:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
[??????(??????????{}
output:
41435136
result:
ok single line: '41435136'
Test #33:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
(?>?[???????????}???
output:
8740864
result:
ok single line: '8740864'
Test #34:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
()()(?
output:
1
result:
ok single line: '1'
Test #35:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
(??)
output:
5
result:
ok single line: '5'
Test #36:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
(<{}>??]
output:
1
result:
ok single line: '1'
Test #37:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
(?]]
output:
0
result:
ok single line: '0'