Day6上括号匹配专项

滑稽的题

#include<iostream>

#include<cstring>

#include<queue>

#include<algorithm>

#include<cstdio>

#include<cmath>

#include<ctime>

using namespace std;

int n;

int a,b,x;

int main()

{

//    freopen("book.in","r",stdin);

//    freopen("bok.out","w",stdout);

    scanf("%d",&n);

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

    {

        scanf("%d",&x);

        if(x==)

        {

            a++;

            continue;

        }

        if(x==)

        {

            if(a)

            {

                a--;

                b++;

                continue;

            }else

            {

                printf("No\n");

                return ;

            }

        }

        if(x==)

        {

            if(a&&b)

            {

                a--;

                b--;

                continue;

            }

            if(a>=&&(!b))

            {

                a-=;

                continue;

            }

            printf("No\n");

            return ;

        }

    }

    printf("YES\n");

    return ;

}

奇怪我手动测得都对，而且超时也不太可能吧。？待解决。

模拟白

#include<iostream>

#include<cstring>

#include<queue>

#include<algorithm>

#include<cstdio>

#include<cmath>

#include<ctime>

using namespace std;

const int N=1e6+;

int n,m;

int sum[N],a[N];

bool is[N];

int main()//又来模拟？

{

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

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

    scanf("%d",&n);

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

        scanf("%d",&a[i]);

    scanf("%d",&m);

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

    {

        scanf("%d",&x);

        is[x]=;

    }

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

    {

        if(is[i])    sum[a[i]]--;

        else

            sum[a[i]]++;

        if(sum[a[i]]<)

        {

            printf("NO\n");

            return ;

        }

    }

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

    {

        if(sum[i]<||(sum[i]%))

        {

            printf("NO\n");

            return ;

        }

        sum[i]/=;

    }

    for(int i=n;i>=;i--)

    if(!is[i])//要不是掉下这一步我就可能A了。

    {

        if(sum[a[i]])

        {

            is[i]=;

            sum[a[i]]--;

        }

    }

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

    {

        if(is[i])

            printf("-%d ",a[i]);

        else

            printf("+%d ",a[i]);

    }

    return ;

}

括号翻转，站。

区间dp。

但我觉得，模拟就ok。

#include<iostream>

#include<cstring>

#include<queue>

#include<algorithm>

#include<cstdio>

#include<cmath>

#include<ctime>

using namespace std;

const int N=;

int h[N],nex[N*],to[N*],w[N*],cnt;

int n,m,q;

int x,y,z;

void add()

{

    scanf("%d%d%d",&x,&y,&z);

    to[++cnt]=y,nex[cnt]=h[x],h[x]=cnt,w[cnt]=z;

    to[++cnt]=x,nex[cnt]=h[y],h[y]=cnt,w[cnt]=z;

}

int kid[N][];

bool vis[N];

int A,B,flag;

void dfs(int x)

{

    if(x==B)

    {

        bool is=;

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

        {

            if(kid[i][]&&(!kid[i][]))

                is=;

            if(kid[i][]&&(!kid[i][]))

                is=;

            if(abs(kid[i][]-kid[i][])%)

                is=;

        }

        if(is)    flag=;

        return ;

    }

    for(int i=h[x],v;i;i=nex[i])

    if(!vis[to[i]])

    {

        vis[to[i]]=;

        if(w[i]>)

            kid[w[i]][]++;

        else kid[-w[i]][]++;

        dfs(to[i]);

        vis[to[i]]=;

        if(w[i]>)

            kid[w[i]][]--;

        else kid[-w[i]][]--;

    }

}

int main()

{

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

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

    scanf("%d%d",&n,&m);

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

        add();

    scanf("%d",&q);

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

    {

        scanf("%d%d",&A,&B);

        flag=;

        vis[A]=;

        dfs(A);

        if(flag)    printf("YES\n");

        else printf("NO\n");

    }

    return ;

}

first 25

预处理Floyed dp

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstdlib>

using namespace std;

int n,m;

int g[][][],q[**][],t,x,y,z;

int main()

{

    scanf("%d%d",&n,&m);

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

    {

        scanf("%d%d%d",&x,&y,&z);

        if(!z)

        {

            if(z<)    z=-z;

            else z+=;

            g[x][y][z]=g[y][x][z]=;

        }else

        {

            g[x][y][z]=g[y][x][z]=;

            t++;q[t][]=x,q[t][]=y,q[t][]=;

            t++;q[t][]=y,q[t][]=x,q[t][]=;

        }

    }

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

    {

        t++;

        q[t][]=i;

        q[t][]=i;

        q[t][]=;

    }

    for(int s=;s<=t;s++)

    {

        int x=q[s][];

        int y=q[s][];

        int kid=q[s][];

        if(!kid)

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

            if(g[i][x][kid-]==&&g[i][y]==)

            {

                g[i][y][]=;

                t++;

                q[t][]=i;

                q[t][]=y;

                q[t][]=;

            }

        else

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

        {

            if(g[i][x]&&(!g[i][y]))

            {

                g[i][y]=;

                t++;

                q[t][]=i;

                q[t][]=y;

                q[t][]=;

            }

            if(g[y][i]&&(!g[x][i]))

            {

                g[x][i]=;

                t++;

                q[t][]=x;

                q[t][]=i;

                q[t][]=;

            }

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

            if(g[y][i][j]&&(!g[x][i][j+]))

            {

                g[x][i][j+]=;

                t++;

                q[t][]=x;

                q[t][]=i;

                q[t][]=j+;

            }

        }

    }

    int q;

    scanf("%d",&q);

    while(q--)

    {

        scanf("%d%d",&x,&y);

        if(g[x][y][])

            printf("YES\n");

        else printf("NO\n");

    }

    return ;

}

巴特西

Day6上括号匹配专项

最新文章

热门文章

巴特西

Day6上 括号匹配专项

最新文章

热门文章

Day6上括号匹配专项