uva1423 巧用拓扑排序

对于一个序列 a1 a2 ... an 我们可以计算出一个符号矩阵A, 其中Si,j 为 a1+...+aj 的正负号，（连加和大于0则Sij=+ 小于0 Sij=- 等于0 则Sij=0），根据序列A不难算出上述符号矩阵。你的任务是求解它的“逆问题” ，及给出一个符号矩阵，找出一个对应的序列。输入保证存在一个满足条件的序列，其中每个整数的绝对值均不超过10

解连续和转化为前缀和之差，设Bi=a1+...+ai 规定B0=0 则矩阵中的任意一项都等价于连个Bi 相减之后的正负号，例如，第x行y列的符号为正号 ax+...+ay>0 By-Bx-1>0, 转化为已知B0,B1,...,Bn,的一些大小关系，求他们的值，这个问题通过拓扑排序完成。

#include <iostream>

#include <cstdio>

#include <string.h>

#include<vector>

#include <algorithm>

using namespace std;

const int INF=;

char str[];

vector<int> same[];

vector<int> to[];

int dgreed[];

int G[];

bool use[];

int ans[];

void solve(int loc, int v){

    for(int i=; i<same[loc].size(); ++i)

         ans[ same[loc][i] ]=v;

}

int main()

{

     int cas;

     scanf("%d",&cas);

     for(int cc=; cc<=cas; ++cc){

         int n;

         scanf("%d",&n);

         scanf("%s",str);

         int loc=;

         memset(dgreed,,sizeof(dgreed));

         memset(use,false,sizeof(use));

         for(int i=; i<=n; ++i) to[i].clear(),ans[i]=INF,same[i].clear();

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

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

                 if(str[loc]==''){

                     same[i-].push_back(j);

                     same[j].push_back(i-);

                 }else if(str[loc]=='+'){

                     to[i-].push_back(j);

                     dgreed[j]++;

                 }else {

                     to[j].push_back(i-);

                     dgreed[i-]++;

                 }

                 loc++;

             }

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

                int k=;

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

                if(use[j]==false&&dgreed[j]==){

                     k=j; break;

                }

            G[i]=k; use[k]=true;

            for(int j=; j<to[k].size(); ++j){

                  dgreed[to[k][j]]--;

            }

          }

        loc=;

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

        if(G[i]==) {

                loc=i; break;

        }

        ans[]=;

        int v=-;

        solve(,);

        for(int i=loc-; i>=; --i){

              if(ans[ G[i] ] == INF){

                 ans[ G[i] ] =v--;

              }

              solve(G[i],ans[G[i]]);

        }

        v=;

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

              if(ans[ G[i] ] == INF){

                 ans[ G[i] ] =v++;

              }

              solve(G[i],ans[G[i]]);

        }

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

             printf("%d%c",ans[i]-ans[i-],i==n?'\n':' ');

     }

    return ;

}

秒客网

uva1423 巧用拓扑排序

相关文章