UVAlive4255

题目很好很有意思。

告诉你n个序列中，任意一个连续子序列的和与0相比较的结果。

构造一个满足条件的序列。

对于从x->y这一段的和，如果大于0，那么sum[x]>sum[y-1]，显然我们可以得到每一个sum的大小关系。由于这个满足条件的sum关系已经考虑了所有的源系列的大小关系，所以只要我们生成了一个满足条件的sum序列能够满足其大小关系，那么a[i]=sum[i]-sum[i-1]就一定是满足条件的。

根据拓扑排序我们可以知道每一个sum之间的大小关系，中间包含于sum[0]=0的大小关系，我们只要依次按照大小一个一个往里面填数字就好了。

召唤代码君：

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <queue>

using namespace std;

int a[][],d[],eq[],Q[],top,totdone,tmp,father;

int f[];

bool vis[];

int n,T;

char s[];

int main()

{

    int cur;

    scanf("%d",&T);

    while (T--)

    {

        memset(a,,sizeof a);

        memset(d,,sizeof d);

        scanf("%d",&n);

        for (int i=; i<=n; i++) eq[i]=-,vis[i]=false;

        scanf("%s",s);

        cur=;

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

            for (int j=i; j<=n; j++,cur++)

            {

                if (s[cur]=='+')

                {

                    a[i-][j]=;

                    d[j]++;

                }

                else if (s[cur]=='-')

                {

                    a[j][i-]=;

                    d[i-]++;

                }

            }

        top=totdone=;

        while (totdone<n+)

        {

            tmp=;

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

                if (!vis[i] && d[i]<tmp) tmp=d[i];

            queue<int> que;

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

                if (!vis[i] && d[i]==tmp) que.push(i);

            father=-;

            while (!que.empty())

                {

                    int i=que.front();

                    que.pop();

                    vis[i]=true;

                    totdone++;

                    if (father==-) { father=i,Q[++top]=i; }

                        else eq[i]=father;

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

                        if (a[i][j]) d[j]--;

                }

        }

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

            if (Q[i]==)

            {

                tmp=i;

                break;

            }

        if (eq[]!=-)

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

                if (Q[i]==eq[]) tmp=i;

        cur=;

        for (int i=tmp+; i<=top; i++) f[Q[i]]=cur++;

        cur=-;

        for (int i=tmp-; i>; i--) f[Q[i]]=cur--;

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

            if (eq[i]!=-) f[i]=f[eq[i]];

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

        {

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

            if (i<n) printf(" ");

        }

        printf("\n");

    }

    return ;

}

巴特西

UVAlive4255_Guess

最新文章

热门文章