uvalive 4255 Guess（拓扑排序）

算好题目，反正我没想到可以用图论做（虽然现在做的是图论专题= =）

首先是要把求每个位置上的值转化为求 “前缀和之差”，这是一个很有用的技巧

其次，由输入的（n+(n-1)+...+2+1）个符号，可以确定出 n个前缀和的大小关系，并从大到小做有向边建图

之后，用拓扑排序依次从大到小找到前缀和，与此同时对num[]做处理，实际上是离散出这n个值。

这n值符合之前的大小关系，所以他们两两相减，就得到了题目要求的值

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<queue>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 const int MAXN=15;
 8 
 9 struct Edge{
10     int v,next;
11     Edge(){}
12     Edge(int _v,int _next):v(_v),next(_next){}
13 }edge[MAXN*MAXN];
14 
15 int indegree[MAXN],n;
16 int num[MAXN];
17 int tol,head[MAXN];
18 
19 queue<int>q;
20 
21 void top()
22 {
23     for(int i=0;i<=n;i++){
24         if(!indegree[i])
25             q.push(i);
26     }
27     while(!q.empty())
28     {
29         int u=q.front();
30         q.pop();
31         for(int i=head[u];i!=-1;i=edge[i].next)
32         {
33 
34             int v=edge[i].v;
35             num[v]--;
36             if((--indegree[v])==0)
37                 q.push(v);
38         }
39     }
40 }
41 
42 void init()
43 {
44     tol=0;
45     memset(head,-1,sizeof(head));
46     memset(indegree,0,sizeof(indegree));
47     memset(num,0,sizeof(num));
48 }
49 
50 void add(int u,int v)
51 {
52     edge[tol]=Edge(v,head[u]);
53     head[u]=tol++;
54 }
55 
56 char str[MAXN*MAXN];
57 
58 int main()
59 {
60     int T;
61     scanf("%d",&T);
62     while(T--)
63     {
64         scanf("%d%s",&n,str);
65         int tot=0;
66         init();
67 
68         for(int i=1;i<=n;i++)
69         {
70             for(int j=i;j<=n;j++,tot++)
71             {
72                 if(str[tot]=='+'){
73                     add(j,i-1);
74                     indegree[i-1]++;
75                 }else if(str[tot]=='-'){
76                     add(i-1,j);
77                     indegree[j]++;
78                 }
79             }
80         }
81         top();
82         for(int i=1;i<=n;i++)
83         {
84             if(i==1)printf("%d",num[i]-num[i-1]);
85             else printf(" %d",num[i]-num[i-1]);
86         }
87         printf("
");
88     }
89     return 0;
90 }

View Code

后来发现其实根本不用拓扑排序。。拓扑的本质是为了离散，其实建图的时候就已经决定了大小关系，可以直接对num[]处理，连建图都省了

 1 #include<stdio.h>
 2 #include<string.h>
 3 
 4 const int MAXN=11;
 5 
 6 int num[MAXN];
 7 char str[MAXN*MAXN];
 8 
 9 int main()
10 {
11     int T,n,tot;
12     scanf("%d",&T);
13     while(T--)
14     {
15         scanf("%d%s",&n,str);
16         tot=0;
17         memset(num,0,sizeof(num));
18         for(int i=1;i<=n;i++)
19         {
20             for(int j=i;j<=n;j++,tot++)
21             {
22                 if(str[tot]=='+')
23                     num[i-1]--;
24                 else if(str[tot]=='-')
25                     num[j]--;
26             }
27         }
28         for(int i=1;i<=n;i++)
29             if(i==1)printf("%d",num[i]-num[i-1]);
30             else printf(" %d",num[i]-num[i-1]);
31         printf("
");
32     }
33     return 0;
34 }

View Code