UVALive 4255 Guess

这题竟然是图论···orz

题意：给出一个整数序列a1，a2，……，可以得到如下矩阵

1 2 3 4

1 - + 0 +

2 + + +

3 - -

4 +

“-”表示从ai到aj的和是负数，“+”表示和是正数，“0”表示和是0。现给出矩阵，求序列，每个整数的绝对值不超过10。

解法：转化为前缀和问题，矩阵可以表示前缀和的关系，用b表示前缀和，例如“-”表示b[j]-b[i-1]<0，即b[j]<b[i-1]。通过矩阵得到所有前缀和之间的关系，通过拓扑排序解出所有前缀和（任意一组解）。记录每个前缀和比它大的前缀和的个数，和比它小的前缀和都有哪些，找到比自己大的前缀和的个数为0的赋值为10（前缀和最大值），将比它小的前缀和的比它们大的前缀和数减一，如此循环，下次赋值为9。

代码：

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<string>

#include<string.h>

#include<math.h>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#define ll long long

using namespace std;

char sign[15][15];

int bigger[15];//比自己大的前缀和个数

vector<int> v[15];//比自己小的前缀和们

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        memset(sign,'\0',sizeof(sign));

        memset(bigger,0,sizeof(bigger));

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

            v[i].clear();

        int n;

        int b[15]= {0};

        scanf("%d",&n);

        char str[200];

        scanf("%s",str);

        int k=0;

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

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

            {

                sign[i][j]=str[k++];

                if(sign[i][j]=='-')

                {

                    bigger[j]++;

                    v[i-1].push_back(j);

                }

                else if(sign[i][j]=='+')

                {

                    bigger[i-1]++;

                    v[j].push_back(i-1);

                }

            }

        int sum=10;

        while(1)

        {

            queue<int> q;

            int flag=1;

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

            {

                if(bigger[i]==0)

                {

                    bigger[i]--;

                    flag=0;

                    b[i]=sum;

                    q.push(i);

                }

            }

            if(flag)

                break;

            else

            {

                while(!q.empty())

                {

                    int i=q.front();

                    q.pop();

                    for(int j=0; j<v[i].size(); j++)

                        bigger[v[i][j]]--;

                }

                sum--;

            }

        }

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

        {

            if(i!=1)

                cout<<" ";

            cout<<b[i]-b[i-1];

        }

        cout<<endl;

    }

    return 0;

}

代码好丑···

12341-+0+2+++3--4+

巴特西

UVALive 4255 Guess

最新文章

热门文章