10-17（day2）

这次写day2的总结

T1：表达式

题面：给你一串表达式

在本题中，我们对合法表达式定义如下：
1. 任何连续（至少1个）数字是合法表达式；
2. 若x是合法表达式，则(x)也是合法表达式；
3. 若x和y 是合法表达式，则x+y、x-y、x*y、x/y都是合法表达式；
4. 若x是合法表达式，则在x 前后添加任意数量的空白符也是合法表达式。
现在给你若干个表达式，请你判断这些表达式是否是合法的。

emmmm，写一个类似于区间dp的东西就行啦（的确定复合NOIPday2T2的难度的，但是好麻烦的感觉）

emmmmm自己没有来得及改自己的wa程序，借用学长的ac程序

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define up(i,j,n)    for (int i = j; i <= n; i++)

#define down(i,j,n)    for (int i = j; i >= n; i--)

#define cmax(a,b)    a = max (a, b)

#define cmin(a,b)    a = min (a, b)

#define FILE        "expr"

const int MAXN = ;

const int oo = 0x3f3f3f3f;

int T, N;

char s[MAXN];

int vaild[MAXN][MAXN];

bool isop(char o){

    if (o == '+') return ;

    if (o == '-') return ;

    if (o == '*') return ;

    if (o == '/') return ;

    return ;

}

bool allempty(int le, int ri){

    up (i, le, ri) if (s[i] != ' ') return ;

    return ;

}

bool chk(int le, int ri){

    if (vaild[le][ri] != -)     return vaild[le][ri];

    if (le > ri)             return vaild[le][ri] = ;

    if (allempty(le, ri))         return vaild[le][ri] = ;

    vaild[le][ri] = ;

    bool allnumber = ;

    up (i, le, ri) if (s[i] < '' || s[i] > '') {

        allnumber = ;

        break;

    }

    if (allnumber) return vaild[le][ri] = ;

    if (le == ri) return vaild[le][ri] = ;

    if (s[le] == '(' && s[ri] == ')') return vaild[le][ri] = chk(le + , ri - );

    bool ok[MAXN];

    up (i, le, ri) ok[i] = ;

    up (i, le, ri) if (isop(s[i])) {

        if (chk(le, i - )) ok[i - ] |= ;

        up (j, le + , i - ) if (isop(s[j]) && ok[j - ])

            ok[i - ] |= chk(j + , i - );

    }

    up (i, le + , ri) if (isop(s[i]) && ok[i - ])

        vaild[le][ri] |= chk(i + , ri);

    int lower = le - , upper = ri + ;

    while (s[lower + ] == ' ') lower++;

    while (s[upper - ] == ' ') upper--;

    vaild[le][ri] |= chk(lower + , upper - );

    return vaild[le][ri];

}

int main(){

    freopen(FILE".in", "r", stdin);

    freopen(FILE".out", "w", stdout);

    scanf("%d", &T);

    char ch = getchar();

    while (T--) {

        gets(s);

        N = strlen(s);

        up (i, , N - ) up (j, i, N - ) vaild[i][j] = -;

        puts(chk(, N - ) ? "Yes" : "No");

    }

    return ;

}

T2：食物链

emmmmm省选题还行

题面：给你一些捕食关系，求有多少条食物链

emmmm一A？类似于拓扑序的东西，我把每一个当前入度为零的点所连的边的权设成1，每次去边就往下传递值，最后一个点就是答案。

#include<bits/stdc++.h>

#define mode 1000000007

using namespace std;

map<string,int> a;

int m;

struct node

{

    int y;

    int next;

}b[];

int lv[];

int n;

int sum;

int f[];

int op[];

int vl[];

int q[];

int num;

void init()

{

    cin>>m;

    memset(lv,,sizeof(lv));

    memset(op,,sizeof(op));

    for(int i=;i<=m;i++)

    {

        string x;

        string y;

        cin>>x>>y;

        if(a[x]==)

            a[x]=++n;

        if(a[y]==)

            a[y]=++n;

        b[++sum].y=a[y];

        b[sum].next=f[a[x]];

        f[a[x]]=sum;

        lv[a[y]]++;

        vl[a[x]]++;

    }

    num=n;

}

void topsort(int x)

{

    q[]=x;

    op[x]=;

    int tou=,wei=;

    while(tou<wei)

    {

        tou++;

        int t=q[tou];

        for(int i=f[t],y;i;i=b[i].next)

        {

            lv[y=b[i].y]--;

            op[y]=(op[y]+op[t])%mode;

            if(lv[y]==)q[++wei]=y;

        }

    }

    cout<<op[wei]<<endl;

}

int main()

{

    freopen("chain.in","r",stdin);

    freopen("chain.out","w",stdout);

    init();

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

        if(lv[i]==)b[++sum].y=i,b[sum].next=f[n+],f[n+]=sum,lv[i]++;

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

        if(vl[i]==)b[++sum].y=n+,b[sum].next=f[i],f[i]=sum,lv[n+]++;

    topsort(n+);

    int yu=;

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

        if(vl[i]==0)yu=(op[i]+yu)%mode;

    cout<<yu<<endl;*/

}

T3：emmmm学长说是出烂的题了

题面：从（0,0）走到（n，m）有多少种走法，其中有k个点是坏点，不能通过。

山神讲过的题，把每个坏点排序，x为第一关键字，y第二关键字，从小到大，

设dp[i]表示到第i个坏点且不经过其他坏点的总方案数，新增加一个点(n,m)，则dp[k]为所求答案。

则有状态转移方程dp[i] = C[x[i]+y[i],x[i]) - sum(dp[j] * C(x[i] - x[j] + y[i] - y[j],x[i] - x[j])

那么问题就是快速求组合数了，容我智障，数论0基础，不会求

学长教了一种o(n)预处理，o(1)查询的求组合数的方法。

int C(int a, int b){

        if (a <  || b <  || a < b) return ;

        return mul(fac[a], mul(inv[b], inv[a - b]));

}

void Prepare(){

    scanf("%d%d%d", &N, &M, &K);

    up (i, , K) scanf("%d%d", &a[i].fi, &a[i].se);

    a[++K] = make_pair(N, M);

    sort(a + , a + K + );

    fac[] = ; inv[] = ; inv[] = ;

    up (i, , LIM) fac[i] = mul (i, fac[i - ]);

    up (i, , LIM) inv[i] = mul (mod - mod / i, inv[mod % i]);

    up (i, , LIM) cmul(inv[i], inv[i - ]);

}

巴特西

10-17（day2）

最新文章

热门文章