算好题目，反正我没想到可以用图论做（虽然现在做的是图论专题= =）
首先是要把求每个位置上的值转化为求 “前缀和之差”，这是一个很有用的技巧
其次，由输入的（n+(n-1)+...+2+1）个符号，可以确定出 n个前缀和的大小关系，并从大到小做有向边建图
之后，用拓扑排序依次从大到小找到前缀和，与此同时对num[]做处理，实际上是离散出这n个值。
这n值符合之前的大小关系，所以他们两两相减，就得到了题目要求的值
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std; const int MAXN=; struct Edge{
int v,next;
Edge(){}
Edge(int _v,int _next):v(_v),next(_next){}
}edge[MAXN*MAXN]; int indegree[MAXN],n;
int num[MAXN];
int tol,head[MAXN]; queue<int>q; void top()
{
for(int i=;i<=n;i++){
if(!indegree[i])
q.push(i);
}
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i!=-;i=edge[i].next)
{ int v=edge[i].v;
num[v]--;
if((--indegree[v])==)
q.push(v);
}
}
} void init()
{
tol=;
memset(head,-,sizeof(head));
memset(indegree,,sizeof(indegree));
memset(num,,sizeof(num));
} void add(int u,int v)
{
edge[tol]=Edge(v,head[u]);
head[u]=tol++;
} char str[MAXN*MAXN]; int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%s",&n,str);
int tot=;
init(); for(int i=;i<=n;i++)
{
for(int j=i;j<=n;j++,tot++)
{
if(str[tot]=='+'){
add(j,i-);
indegree[i-]++;
}else if(str[tot]=='-'){
add(i-,j);
indegree[j]++;
}
}
}
top();
for(int i=;i<=n;i++)
{
if(i==)printf("%d",num[i]-num[i-]);
else printf(" %d",num[i]-num[i-]);
}
printf("\n");
}
return ;
}
后来发现其实根本不用拓扑排序。。拓扑的本质是为了离散，其实建图的时候就已经决定了大小关系，可以直接对num[]处理，连建图都省了
#include<stdio.h>
#include<string.h> const int MAXN=; int num[MAXN];
char str[MAXN*MAXN]; int main()
{
int T,n,tot;
scanf("%d",&T);
while(T--)
{
scanf("%d%s",&n,str);
tot=;
memset(num,,sizeof(num));
for(int i=;i<=n;i++)
{
for(int j=i;j<=n;j++,tot++)
{
if(str[tot]=='+')
num[i-]--;
else if(str[tot]=='-')
num[j]--;
}
}
for(int i=;i<=n;i++)
if(i==)printf("%d",num[i]-num[i-]);
else printf(" %d",num[i]-num[i-]);
printf("\n");
}
return ;
}