UVA1423 猜序列 解题报告

【问题描述】  

　　对于一个序列a[1],a[2],…,a[n]，我们可以计算出一个符号矩阵S，其中s[i][j]=a[i]+…+a[j]的正负号：连加和大于0则s[i][j]='+'，小于0则s[i][j]='-'，等于0则s[i][j]='0'。例如序列：-1,5,-4,2的矩阵如下： 

　　　　 

　　根据序列A不难算出上述符号矩阵。你的任务上求解它的逆问题，即给出一个符号矩阵，找出一个对应的序列。输入保证存在一个满足上述条件的序列，其中每个整数的绝对值均不超过10。

 【输入格式】  

　　第1行为整数T，表示数据组数。

　　每组数据包含两行，第1行为整数n，表示序列长度。第2行有n*(n+1)/2个字符，有符号矩阵的每一行按照从上到下的顺序连接而成。

 【输出格式】  

　　对于每组数据，在一行上输出n个绝对值不超过10的整数，即序列A。要求序列中最大值与最小值尽量接近。

 【输入样例】   

3

4

-+0++++--+

2 

+++ 

5 

++0+-+-+--+-+--

 【输出样例】  

-1 3 -2 1

1 1 

1 1 -2 3 -4 

【数据范围】  

1<=T<=100  , 1<=n<=10

解题思路：本题的核心思路是转化。s[i][j]为连续子序列和，可以转化为sum[j]-sum[i-1]（前缀和）。由题目所给信息可以判断出sum[j]与sum[i-1]的大小关系，于是可以把sum的下标看作图的顶点，将sum[i-1]<sum[j]转化为由i-1到j的一条有向边。因为图中不可能存在环，所以该图为DAG图，又因为A[i]=A[i]-A[i-1]，所以可以运用拓扑排序把sum计算出来，进而求得A序列。需要注意的是要使序列中最大值与最小值尽量接近，且序列为整数，则sum之间的最小差值为1，可以假设最小的sum（下标为图中入度为0的点）为10，对A序列的值无影响，进行拓扑排序BFS，求得所有sum。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=15;
int T,N;
char s[100];
int sum[maxn],rd[maxn];
vector<int>g[maxn];
void BFS()
{
	queue<int>q;
	for(int i=0;i<=N;i++)
	if(rd[i]==0)  
	{
		q.push(i);
		sum[i]=10;  //假设最小的sum值为10
	}
	while(!q.empty())
	{
		int i=q.front();  q.pop();
		for(int k=0;k<g[i].size();k++)
		{
			int j=g[i][k];
			if(rd[j]>0)  rd[j]--;
			if(rd[j]==0)  
			{
				q.push(j);
				sum[j]=sum[i]+1;  //sum之间的最小差值为1
			}
		}
	}
}
int main()
{
	//freopen("48.in","r",stdin);
	//freopen("48.out","w",stdout);
	scanf("%d",&T);
	for(int i=1;i<=T;i++)
	{
		scanf("%d",&N);
		scanf("%s",s);
		memset(rd,0,sizeof(rd));
		memset(sum,0,sizeof(sum));
		for(int i=0;i<=N;i++)
		g[i].clear();  //注意每次要清空
		int k=0;
		for(int i=1;i<=N;i++)
		for(int j=i;j<=N;j++)
		{
			if(s[k]=='-')  //s[i][j]<0  sum[j]<sum[i-1]
			{	
				g[j].push_back(i-1);  
				rd[i-1]++;
			}
			if(s[k]=='+')  //s[i][j]>0  sum[i-1]<sum[j]
			{
				g[i-1].push_back(j);  
				rd[j]++;
			}
			k++;
		}
		BFS();
		for(int i=1;i<=N;i++)
		printf("%d ",sum[i]-sum[i-1]);
		printf("\n");
	}
	return 0;
}