传送门
思路：连续和转化为前缀和之差。可以将问题转化为已知序列 a1,a2,...,an 的大小关系，求出任意一组满足条件的序列。 拓扑排序即可。
我是以sum大指向sum小的方向建边。假设入度为零的点即最大值点的值为0，那么后面的点比它小就小1。 注意sum[0]=0，0也要跑。
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> piir; const int maxn = 10+5; const int maxm = 5e5+5; const int INF = 0x3f3f3f3f; string s; vector<int> G[maxn]; int T,n; int sum[maxn],in[maxn]; queue<int> q; void top(){ for(int i=0;i<=n;i++){ if(in[i]==0) q.push(i); } while(!q.empty()){ int u=q.front();q.pop(); for(auto v : G[u]){ sum[v] = sum[u]-1; in[v]--; if(in[v]==0) q.push(v); } } } void init(){ while(!q.empty()) q.pop(); for(int i=0;i<=n;i++) G[i].clear(); memset(sum,0,sizeof(sum)); memset(in,0,sizeof(in)); } int main(){ //freopen("in.txt","r",stdin); cin>>T; while(T--){ init(); cin>>n; cin>>s; int tot=0; for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ if(s[tot]=='+') G[j].push_back(i-1),in[i-1]++; else if(s[tot]=='-') G[i-1].push_back(j),in[j]++; tot++; } } top(); for(int i=1;i<=n;i++){ cout<<sum[i]-sum[i-1]<<" "; } cout<<'\n'; } return 0; }
