首页 > 代码库 > UVAlive4255_Guess

UVAlive4255_Guess

2024-07-12 01:30:18   217人阅读

题目很好很有意思。

告诉你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[11][11],d[11],eq[11],Q[121],top,totdone,tmp,father;int f[121];bool vis[11];int n,T;char s[121];int main(){    int cur;    scanf("%d",&T);    while (T--)    {        memset(a,0,sizeof a);        memset(d,0,sizeof d);        scanf("%d",&n);        for (int i=0; i<=n; i++) eq[i]=-1,vis[i]=false;        scanf("%s",s);        cur=0;        for (int i=1; i<=n; i++)            for (int j=i; j<=n; j++,cur++)            {                if (s[cur]==‘+‘)                {                    a[i-1][j]=1;                    d[j]++;                }                else if (s[cur]==‘-‘)                {                    a[j][i-1]=1;                    d[i-1]++;                }            }        top=totdone=0;        while (totdone<n+1)        {            tmp=9999;            for (int i=0; i<=n; i++)                if (!vis[i] && d[i]<tmp) tmp=d[i];            queue<int> que;            for (int i=0; i<=n; i++)                if (!vis[i] && d[i]==tmp) que.push(i);            father=-1;            while (!que.empty())                {                    int i=que.front();                    que.pop();                    vis[i]=true;                    totdone++;                    if (father==-1) { father=i,Q[++top]=i; }                        else eq[i]=father;                    for (int j=0; j<=n; j++)                        if (a[i][j]) d[j]--;                }        }        for (int i=1; i<=top; i++)            if (Q[i]==0)            {                tmp=i;                break;            }        if (eq[0]!=-1)            for (int i=0; i<=n; i++)                if (Q[i]==eq[0]) tmp=i;        cur=1;        for (int i=tmp+1; i<=top; i++) f[Q[i]]=cur++;        cur=-1;        for (int i=tmp-1; i>0; i--) f[Q[i]]=cur--;        for (int i=0; i<=n; i++)            if (eq[i]!=-1) f[i]=f[eq[i]];        for (int i=1; i<=n; i++)        {            printf("%d",f[i]-f[i-1]);            if (i<n) printf(" ");        }        printf("\n");    }    return 0;}

 


联系
我们