列表

详情

NC21814. 筱玛的字符串

描述

筱玛是一个快乐的男孩子。
筱玛有一个合法的括号匹配串S，但是被!b!b和ipip给偷走了！
!b!b把S中连续一段的字符给反转（即左括号变成右括号，右括号变成左括号），称为S'。
注意!b!b可能并没有反转。
ipip把S'其中的一些字符变成了?，称为S''。
筱玛很生气，但是他只知道S''。
请你求出所有可能的(S,S')对的个数，对取模。

输入描述

一行一个字符串S。

输出描述

一行一个整数，表示模意义下的答案。

示例1

输入: 

??))

输出: 

7

说明:

()(),()))
()(),(())
()(),)())
(()),(())
(()),()))
(()),)())
(()),))))

原站题解

import java.util.Scanner;
public class Main {
public static void main(String[] arg) {
Scanner scanner = new Scanner(System.in);
// todo
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

C++14(g++5.4) 解法, 执行用时: 194ms, 内存消耗: 118248K, 提交时间: 2019-01-11 19:51:22 

#include<bits/stdc++.h>

#define maxn 3010

#define ll long long

using namespace std;



int n;

ll f[maxn][maxn][3];

const ll p=1e9+7;

char s[maxn];



int main()

{

    scanf("%s",s+1),n=strlen(s+1);

    f[0][0][0]=1;

    for(int i=1;i<=n;i++)

    {

        for(int j=0;j<=i;j++)

        {

            if(s[i]!='(')

            {

                f[i][j][0]+=f[i-1][j+1][0];

                if(j)

                    f[i][j][1]+=f[i-1][j-1][0]+f[i-1][j-1][1];

                f[i][j][2]+=f[i-1][j+1][1]+f[i-1][j+1][2];

            }

            if(s[i]!=')')

            {

                if(j)

                    f[i][j][0]+=f[i-1][j-1][0];

                f[i][j][1]+=f[i-1][j+1][0]+f[i-1][j+1][1];

                if(j)

                    f[i][j][2]+=f[i-1][j-1][1]+f[i-1][j-1][2];

            }

            for(int k=0;k<3;k++)

                f[i][j][k]%=p;

        }

    }

    printf("%lld\n",(f[n][0][0]+f[n][0][1]+f[n][0][2])%p);

    return 0;

}

C++11(clang++ 3.9) 解法, 执行用时: 134ms, 内存消耗: 118252K, 提交时间: 2019-01-11 19:40:23 

#include<bits/stdc++.h>

#define maxn 3010

#define ll long long

using namespace std;



int n;

ll f[maxn][maxn][3];

const ll p=1e9+7;

char s[maxn];

int main(){

    scanf("%s",s+1),n=strlen(s+1);

    f[0][0][0]=1;

    for(int i=1;i<=n;i++){

        for(int j=0;j<=i;j++){

            if(s[i]!='('){

                f[i][j][0]+=f[i-1][j+1][0];

                if(j)

                    f[i][j][1]+=f[i-1][j-1][0]+f[i-1][j-1][1];

                f[i][j][2]+=f[i-1][j+1][1]+f[i-1][j+1][2];

            }

            if(s[i]!=')'){

                if(j)

                    f[i][j][0]+=f[i-1][j-1][0];

                f[i][j][1]+=f[i-1][j+1][0]+f[i-1][j+1][1];

                if(j)

                    f[i][j][2]+=f[i-1][j-1][1]+f[i-1][j-1][2];

            }

            for(int k=0;k<3;k++)

                f[i][j][k]%=p;

        }

    }

    printf("%lld\n",(f[n][0][0]+f[n][0][1]+f[n][0][2])%p);

    return 0;

}

上一题

© 2025 nowcoder.com