首页 > 代码库 > Guess

Guess

2024-07-08 18:41:40   222人阅读

uvaLive4255:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=25&page=show_problem&problem=2256

题意：对于一个序列，我们可以计算出一个符号矩阵，其中Sij为ai+...+aj的正负号，现在给你一个矩阵的上三角，求一个满足的序列

题解：对于这一题，按照白书上讲的，可以转化成前缀和来做。B【i】表示B[1]+B[2]+....+B[i]的和，sij=B[j]-B[i-1];如果Sij>0，就B[J]-B[I-1]>0，那么i-1和j建立一条边，相反的就j到i-1建边，如果等于0，不用考虑的，因为是n*（n-）/2个数，每个点和其他点都有关系，所以肯定会搜到。建好图之后，直接topsort 就可以得到一组B的值，然后相邻的相减，就可以得到一组a的值。这里，为方便，加入一个0点，并且B[0]=0；

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 int b[20],n; 8 int deg[20]; 9 bool map[20][20];10 void init(){11      memset(deg,0,sizeof(deg));12      memset(b,0,sizeof(b));13      memset(map,0,sizeof(map));14 }15 void topsort(){16    b[0]=0;17    queue<int>Q;18    for(int i=0;i<=n;i++){19        if(deg[i]==0){20          deg[i]--;21          Q.push(i);22          b[i]=0;23        }24    }25    while(!Q.empty()){26        int u=Q.front();27        Q.pop();28        for(int i=0;i<=n;i++){29           if(map[u][i]){30                deg[i]--;31                if(deg[i]==0){32                  b[i]=b[u]+1;33                  deg[i]--;34                  Q.push(i);35                }36           }37        }38    }39 }40 char temp;41 int main(){42    int test;43    scanf("%d",&test);44    while(test--){45      scanf("%d",&n);46      init();47      for(int i=0;i<n;i++){48         for(int j=i+1;j<=n;j++){49             cin>>temp;50             if(temp==‘+‘){51                 deg[j]++;52                 map[i][j]=1;53             }54             else if(temp==‘-‘){55                deg[i]++;56                map[j][i]=1;57             }58         }59      }60       topsort();61       for(int i=1;i<=n;i++){62         if(i<n)printf("%d ",b[i]-b[i-1]);63         else64             printf("%d\n",b[i]-b[i-1]);65       }66    }67 }
View Code

 


联系
我们