QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#294595	#4824. Bracket-and-bar Sequences	ucup-team1525^#	0	0ms	3916kb	C++20	2.4kb	2023-12-30 14:53:12	2023-12-30 14:53:13

Judging History

你现在查看的是最新测评结果

[2023-12-30 14:53:13]
评测

测评结果：0
用时：0ms
内存：3916kb

查看

[2023-12-30 14:53:12]
提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=25;
ll f[N+5];
void prep(){
    f[0]=1;
    for(int i=1;i<=N;i++)
        for(int j=0;j<i;j++)
            for(int k=0;j+k<i;k++)
                f[i]+=f[j]*f[k]*f[i-j-k-1];
    // printf("%lld\n",f[N]);
}
ll dfs(int n,char s[N*3+5]){
    if(n==0) return 1;
    int j=0,k=0,mt=0,cnt=0;
    for(int i=0;i<n*3;i++)
        if(s[i]=='(') mt++;
        else if(s[i]==')'){
            mt--;
            if(!mt){
                k=cnt; break;
            }
            cnt++;
        }
        else{
            if(mt==1) j=cnt;
        }
    //printf("%d %d %d\n",n,j,k);
    ll res=0;
    for(int j1=0;j1<j;j1++)
        for(int k1=0;j1+k1<n;k1++)
            res+=f[j1]*f[k1]*f[n-1-j1-k1];
    for(int k1=0;j+k1<k;k1++)
        res+=f[j]*f[k1]*f[n-1-j-k1];
    char t[N*3+5];
    int lt=0;
    for(int i=1;i<=j*3;i++)
        t[lt++]=s[i];
    for(int i=j*3+2;i<3*k+2;i++)
        t[lt++]=s[i];
    for(int i=3*k+3;i<3*n;i++)
        t[lt++]=s[i];
    return res+dfs(n-1,t);
}
void encode(){
    int n;
    char s[N*3+5];    
    scanf("%d",&n);
    scanf("%s",s);
    printf("%lld\n",dfs(n,s));
}
char ans[N*3+5];
void dfs(int n,ll res){
    if(n==0) return;
    for(int j=0;j<n;j++)
        for(int k=0;j+k<n;k++){
            ll tmp=f[j]*f[k]*f[n-j-k-1];
            if(tmp<res) res-=tmp;
            else{
                // printf("%d %d %d\n",n,j,k);
                dfs(n-1,res);
                char now[N+5];
                int lt=0;
                now[0]='(';
                for(int i=1;i<=j*3;i++)
                    now[i]=ans[lt++];
                now[j*3+1]='|';
                for(int i=j*3+2;i<3*(j+k)+2;i++)
                    now[i]=ans[lt++];
                now[3*(j+k)+2]=')';
                for(int i=3*(j+k)+3;i<3*n;i++)
                    now[i]=ans[lt++];
                for(int i=0;i<3*n;i++)
                    ans[i]=now[i];
                return;
            }
        }
}
void decode(){
    int n; ll res;
    scanf("%d",&n);
    scanf("%lld",&res);
    dfs(n,res);
    printf("%s\n",ans);
}
int main(){
    prep();
    char s[10];
    scanf("%s",s);
    if(s[0]=='e'){
        int t; scanf("%d",&t);
        while(t--) encode();
    }
    else{
        int t; scanf("%d",&t);
        while(t--) decode();
    }
    return 0;
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3916kb

input:

encode
3
1
(|)
4
((((|)|)|)|)
5
(|(|))((|(|))|)

output:

1
55
66

input:

decode
3
1
1
4
55
5
66

output:

(|)
((((|)|)|)|)
(|(|))((|(|))|)

result:

ok 3 lines

Test #2:

score: 100

Accepted

time: 0ms

memory: 3812kb

input:

encode
1
1
(|)

output:

input:

decode
1
1
1

output:

(|)

result:

ok single line: '(|)'

Test #3:

score: 0

Wrong Answer

time: 0ms

memory: 3860kb

input:

encode
3
2
((|)|)
1
(|)
2
(|(|))

output:

3
1
2

input:

decode
3
2
3
1
1
2
2

output:

((|)|)
(|))|)
(|(|))

result:

wrong answer 2nd lines differ - expected: '(|)', found: '(|))|)'