UVA1423 Guess（拓扑排序）

Guess

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 (1 ≤ n ≤ 10), 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

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

链接

https://cn.vjudge.net/problem/UVALive-4255

题意

一个未知的整数序列，给出其任意一个区间和的正负，现要求还原这个序列，找到符合条件的一种即可。输入保证存在一个满足条件的序列，其中每个整数的绝对值不超过10。

对于一个序列$a_1, a_2, ..., a_n$，我们可以计算一个符号矩阵S，其中$S_{ij}$为$a_i+...+a_j$的正负号（连加和大于0则$S_{ij}$ = '+'，小于0则$S_{ij}$='-'，等于0则$S_{ij}$='0'），参见样例。

现在的任务是求解它的“逆问题”，即给出一个符号矩阵，找出一个对应的序列。

题解

使用“连续和转化为前缀和之差”的技巧，设$B_i = a_1 + a_2 + ... + a_i$，规定$B_0 = 0$，则矩阵中的任意一项都等价于等于$B_i$相减之后的正负号。例如，第x行y列的符号为正，表示$a_x+...+a_y>0$，即$B_y-B_{x_1}>0$，即$B_y>B_{x_1}$。这样，本题就转化为已知$B_0 = 0, B_1, ..., B_n$的一些大小关系，求它们的值（只要一组解即可）。可以通过拓扑排序完成。——小白书P310

本题参考了TouchDreamer的写法。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 110;
vector <int> E[maxn];
queue <int> Q;
char s[maxn];
int sum[maxn]; // 表示前缀和
int indegree[maxn];
int n;

void init()
{
    for (int i = 0; i <= n; ++i)
    {
        E[i].clear();
        indegree[i] = 0;
        sum[i] = -1; // sum初始值可以自定义，不会对结果造成什么影响，因为求得的是前缀和的差值
    }
}

void TopSort()
{
    for (int i = 0; i <= n; ++i)
    {
        if (indegree[i] == 0)
            Q.push(i);
    }
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        for (int i = 0; i < E[u].size(); ++i)
        {
            int v = E[u][i];
            sum[v] = sum[u] - 1; // v->u，说明sum[v]比sum[u]小，减1即可，保证数在-10到10之间
            if ((--indegree[v]) == 0)
                Q.push(v);
        }
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        init();
        scanf("%d", &n);
        scanf("%s", s);
        int k = 0;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = i; j <= n; ++j)
            {
                if (s[k] == '+') // 将Sij转化为sum[j] - sum[i-1]，根据大小关系建边
                {
                    E[j].push_back(i-1);
                    indegree[i-1]++;
                }
                else if (s[k] == '-')
                {
                    E[i-1].push_back(j);
                    indegree[j]++;
                }
                k++;
            }
        }
        TopSort();
        printf("%d", sum[1] - sum[0]);
        for (int i = 2; i <= n; ++i) // 前缀和相减得到每一个元素
            printf(" %d", sum[i] - sum[i-1]);
        printf("\n");
    }
    return 0;
}

The end.
2018-07-20 星期五