Given a sequence of integers, a1, a2,..., an , we define its sign matrix S such that, for 1ijn , Sij = `` + " if ai +...+ aj > 0 ; Sij = `` - " if ai +...+ aj < 0 ; and Sij = ``0" otherwise.
For example, if (a1, a2, a3, a4) = (- 1, 5, - 4, 2) , then its sign matrix S is a 4×4 matrix:
1 | 2 | 3 | 4 | |
1 | - | + | 0 | + |
2 | + | + | + | |
3 | - | - | ||
4 | + |
We say that the sequence (-1, 5, -4, 2) generates the sign matrix. A sign matrix is valid if it can be generated by a sequence of integers.
Given a sequence of integers, it is easy to compute its sign matrix. This problem is about the opposite direction: Given a valid sign matrix, find a sequence of integers that generates the sign matrix. Note that two or more different sequences of integers can generate the same sign matrix. For example, the sequence (-2, 5, -3, 1) generates the same sign matrix as the sequence (-1,5, -4,2).
Write a program that, given a valid sign matrix, can find a sequence of integers that generates the sign matrix. You may assume that every integer in a sequence is between -10 and 10, both inclusive.
Input
Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case consists of two lines. The first line contains an integer n (1n10) , where n is the length of a sequence of integers. The second line contains a string of n(n + 1)/2 characters such that the first n characters correspond to the first row of the sign matrix, the next n - 1 characters to the second row, ... , and the last character to the n -th row.
Output
Your program is to write to standard output. For each test case, output exactly one line containing a sequence of n integers which generates the sign matrix. If more than one sequence generates the sign matrix, you may output any one of them. Every integer in the sequence must be between -10 and 10, both inclusive.
Sample Input
3 4 -+0++++--+ 2 +++ 5 ++0+-+-+--+-+--
Sample Output
-2 5 -3 1 3 4 1 2 -3 4 -5
LRJ的代码看不懂。。。然后发现http://blog.csdn.net/wiking__acm/article/details/8660931这位大神的代码和解说都比较易懂,于是照敲了一遍,很纠结地A了。
其实就是拓扑排序,删除入度为零的点,删除其指出的边,开始觉得有点像差分约束题,但差分约束貌似只能判断有无解,而无法构造解。。。不过问题建模是一样的,不等式组,构造连接图:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<set> #include<queue> #include<string> #include<cmath> #include<fstream> #include<iomanip> #include<climits> #include<cfloat> using namespace std; #define MAX_INT 0x7fffffff #define MAX_LL 0x7fffffffffffffff #define ULL unsigned long long #define LL long long #define MAX(x,y) ((x) > (y) ? (x) : (y)) #define MIN(x,y) ((x) < (y) ? (x) : (y)) #define MAXN 13 int n; int map[MAXN][MAXN]; int degree[MAXN]; int s[MAXN]; char text[1000]; void Topsort(){ int cnt=0,cur=-10; while(cnt<n+1){ int flag[MAXN]; memset(flag, 0, sizeof(flag)); //标记出入度为0的点 for(int i=0; i<=n; i++) if(!degree[i]){ degree[i]=-1; flag[i]=1; s[i]=cur; //构造解 cnt++; } cur++; //删除由标记点指出的弧 for(int i=0; i<=n; i++) if(flag[i]){ for(int j=0; j<=n; j++) if(map[i][j]){ degree[j]--; } } } } void ini(){ memset(map, 0, sizeof(map)); memset(degree, 0, sizeof(degree)); } int main(){ //freopen("C:\Users\Administrator\Desktop\in.txt","r",stdin); int cas; scanf(" %d",&cas); while(cas--){ scanf(" %d%s",&n,text); ini(); int c=0; for(int i=1; i<=n; i++) for(int j=i; j<=n; j++){ if(text[c]=='+'){ //加边,s[j]-s[i-1]>0则i-1指向j, map[i-1][j]=1; degree[j]++; } else if(text[c]=='-'){ map[j][i-1]=1; degree[i-1]++; } c++; } Topsort(); //拓扑排序 for(int i=1; i<=n; i++) printf("%d%c",s[i]-s[i-1],(i==n ? ' ':' ')); } return 0; }