UVa 1423 – Guess [数列前缀和+拓扑排序]

Problem

传送门

Mean

给你一个数n和一个字符矩阵,矩阵中S(i, j)表示ai + a(i+1) +…aj的正负号,要你还原a序列,其中a序列中每个数的绝对值不大于10.数列最多10个数

Analysis

根据每个数列段的符号可以转化为两个前缀和的大小关系,这就就得到了拓扑关系,拓扑排序即可。

Code

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

const int maxn = 15;
int n, cur, in[maxn], t[maxn];
string str;
vector<int> G[maxn];

void toposort() {
    cur = 7777777;
    vector<int> qu;
    for(int i = 0; i <= n; ++i)
        if(!in[i]) qu.push_back(i);
    while(!qu.empty()) {
        for(auto i : qu)
            t[i] = cur;
        vector<int> ne;
        for(auto i : qu)
            for(auto j : G[i])
                if(--in[j] == 0)
                    ne.push_back(j);
        qu = ne;
        cur -= 1;
    }
}

int main() {
    int T; cin >> T;
    while(T--) {
        cin >> n >> str;
        memset(in, 0, sizeof(in));
        for(int i = 0; i <= n; ++i) G[i].clear();
        for(int i = 1, k = 0; i <= n; ++i) {
            for(int j = i; j <= n; ++j) {
                if(str[k] == '-') G[i-1].push_back(j), ++in[j];
                else if(str[k] == '+') G[j].push_back(i-1), ++in[i-1];
                k += 1;
            }
        }
        toposort();
        for(int i = 1; i <= n; ++i) {
            printf("%d%c", t[i] - t[i-1], i==n ? '\n' : ' ');
        }
    }
    return 0;
}

欢迎留言