牛客网NOIP赛前集训营-普及组（第一场）

A.绩点

思路:水题.题目要求保留1位小数,四舍五入. round(ans*10)/10即可

B.巨大的棋盘

题意:取膜

C.括号

题意: 有一个由'('和')'构成的长度不超过1e4的序列,求有多少种选择的方法,使得括号是匹配的

思路:

定义dp[i][j]:  到第i个位置,1~i中有j个'('未匹配过

if(s[i]=='(')    dp[i][j]=dp[i-1][j]+dp[i-1][j-1];

if(s[i]==')')    dp[i][j]=dp[i-1][j]+dp[i-1][j+1];

开滚动数组,时间换空间.方案数取膜,考虑组合或者DP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+4;
const ll MOD=1e9+7;
const int Seed=1e7+7;
template <class T>
bool sf(T &ret){ //Faster Input
    char c; int sgn; T bit=0.1;
    if(c=getchar(),c==EOF) return 0;
    while(c!='-'&&c!='.'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    if(c==' '||c=='\n'){ ret*=sgn; return 1; }
    while(c=getchar(),c>='0'&&c<='9') ret+=(c-'0')*bit,bit/=10;
    ret*=sgn;
    return 1;
}
char s[N];
ll dp[2][10005];
void adjust(ll &t){
    t%=MOD;
    t+=MOD;
    t%=MOD;
}
int main(){
    int n;
    sf(n);
    scanf("%s",s+1);
    dp[0][0]=1;
    int now=0;
    for(int i=1;i<=n;i++){
        now^=1;
        if(s[i]=='('){
            dp[now][0]=dp[now^1][0];
            adjust(dp[now][0]);
            for(int j=1;j<=i;j++)   dp[now][j]=dp[now^1][j]+dp[now^1][j-1],adjust(dp[now][j]);
        }
        else{
            adjust(dp[now][0]);
            for(int j=i;j>=0;j--)   dp[now][j]=dp[now^1][j]+dp[now^1][j+1],adjust(dp[now][j]);
        }
    }
    printf("%lld\n",dp[now][0]-1);

    return 0;
}