UVA 1423: Guess —— 拓扑排序

传送门

题目大意:

给出一个符号矩阵 $S$ ,如果一个数列 $a$ 对于这个符号矩阵满足 $S_{i,j} =$ ‘+’ 时 $\sum_{k=i}^{j}{a_k} > 0$ , $S_{i,j} =$ ‘-‘ 时 $\sum_{k=i}^{j}{a_k} < 0$ , $S_{i,j} = 0$ 时 $\sum_{k=i}^{j} = 0$ ,则数列 $a$ 对于符号矩阵 $S$ 是有效的。求一个有效的 $a$ ,要求 $a$ 中元素的大小满足 $-10\leq a_i \leq 10$ 。

输入格式:

第一行一个整数 $T$ ,代表测试数据组数。

对于每组数据,第一行一个整数 $n\ (1 \leq n \leq 10)$ 代表所求数列的长度。接下来一行一个包含 $\frac{n(n+1)}{2}$ 个字符,表示一个展开的符号矩阵。

输出格式:

对于每组数据,输出一行一个数列,每个数字用空格隔开。

测试样例:

Input
3
4
-+0++++–+
2
+++
5
++0+-+-+–+-+–
Output
-2 5 -3 1
3 4
1 2 -3 4 -5

分析:

这道题非常有意思。

题上给出的条件非常抽象。我们如何利用这个符号矩阵中的信息呢?因为符号矩阵代表的是以一段连续区间的和,所以我们可以考虑把它转化成两个前缀和与 $0$ 的大小关系。例如:若 $S_{i,j} > 0$ 则 $sum_j - sum_{i - 1} > 0$ 。这样的话问题就转化成了求一个合法的前缀和序列。

如何求这个合法的前缀和序列?我们只需要保证小的前缀和一直在大的前缀和前面,求出这样一个前缀和的序列。怎么做呢?拓扑排序。例如:若 $S_{i,j} > 0$ ,说明 $sum_j > sum_{i - 1}$ ,我们就从 $i - 1$ 向 $j$ 连一条有向边。最后对建成的图求拓扑序。因为要求 $-10 \leq a_i \leq 10$ ,所以最小的前缀和从 $0$ 记是没有问题的,每次递增 $1$ 。

求出这个前缀和序列以后,要还原成原数列。非常简单, $a_i = sum_i - sum_{i - 1}$ 。

这道题有一个巨大的坑:输出时每一行的末尾不能留空格

代码:

#include <bits/stdc++.h>
using namespace std;

template<class _T> inline void read(_T &_x) {
  int _t, _flag = 0;
  while ((_t = getchar()) != '-' && (_t < '0' || _t > '9'));
  if (_t == '-')  _flag = 1, _t = getchar();
  _x = _t - '0';
  while ((_t = getchar()) >= '0' && _t <= '9')
    _x = _x * 10 + _t - '0';
  if (_flag)  _x = -_x;
}

typedef long long ll;
typedef pair<int, int> pii;

const int MAX_N = 200 + 10, INF = 0x3f3f3f3f;
struct Edge {
  int v, next;
  Edge() {}
  Edge(int _v, int _next)
    : v(_v), next(_next)
  {}
} edge[MAX_N << 1];
int head[MAX_N], kk = 1, in[MAX_N], n, s[MAX_N];

void init() {
  memset(head, 0, sizeof(head));
  memset(in, 0, sizeof(in));
  memset(s, 0, sizeof(s));
  kk = 1;
}

inline void addedge(int u, int v) {
  edge[kk] = Edge(v, head[u]), head[u] = kk++;
}

void Topo_sort() {
  queue<int> q;
  for (int i = 0; i <= n; ++i) {
    if (!in[i]) q.push(i);
  }
  int num = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    ++num;
    for (int i = head[u]; i; i = edge[i].next) {
      int v = edge[i].v;
      --in[v];
      if (!in[v]) {
        q.push(v);
        /* 若更新入度后出现了两个及以上入度为 0 的点,那么他们的前缀和
        值互不影响。我们可以将他们赋一个相同的值。*/
        s[v] = num;
      }
    }
  }
}

int main() {
  int T;
  read(T);
  while (T--) {
    init();
    read(n);
    char str[MAX_N];
    scanf("%s", str);
    int cnt_str = 0;
    for (int i = 1; i <= n; ++i)
      for (int j = i; j <= n; ++j) {
        if (str[cnt_str] == '+') {
          addedge(i - 1, j);
          ++in[j];
        }
        else if (str[cnt_str] == '-') {
          addedge(j, i - 1);
          ++in[i - 1];
        }
        ++cnt_str;
      }
    Topo_sort();
    for(int i = 1; i < n; ++i) {
      printf("%d ", s[i] - s[i - 1]);
    }
    printf("%d\n", s[n] - s[n - 1]);
  }
  return 0;
}