QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#218356#2927. Bracket Pairingucup-team1004AC ✓0ms3824kbC++14991b2023-10-18 08:16:092023-10-18 08:16:09

Judging History

This is the latest submission verdict.

  • [2023-10-18 08:16:09]
  • Judged
  • Verdict: AC
  • Time: 0ms
  • Memory: 3824kb
  • [2023-10-18 08:16:09]
  • Submitted

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'