「NOIP 2008」双栈排序

#二分图染色

Published on 2016-11-04

描述

Tom 最近在研究一个有趣的排序问题。通过 2 个栈 $S_1$ 和 $S_2$ ，Tom 希望借助以下 4 种操作实现将输入序列升序排序。

A：如果输入序列不为空，将第一个元素压入栈 $S_1$ 。
B：如果栈 $S_1$ 不为空，将 $S_1$ 栈顶元素弹出至输出序列。
C：如果输入序列不为空，将第一个元素压入栈 $S_2$ 。
D：如果栈 $S_2$ 不为空，将 $S_2$ 栈顶元素弹出至输出序列。

如果一个的排列 $P$ 可以通过一系列操作使得输出序列为，Tom 就称 $P$ 是一个“可双栈排序排列”。例如 $(1,3,2,4)$ 就是一个“可双栈排序序列”，而 $(2,3,4,1)$ 不是。
将 $(1,3,2,4)$ 排序的操作序列：a,c,c,b,a,d,d,b。
当然，这样的操作序列有可能有几个，对于上例 $(1,3,2,4)$ ，a,c,c,b,a,d,d,b 是另外一个可行的操作序列。
Tom 希望知道其中字典序最小的操作序列是什么。

分析

这个题首先得入手，我们先看最小的数 $1$ ，一旦我们遇到了数 $1$ ，那么我们必定进行操作 a, b 将其压入并弹出，如果之前 $2$ 在栈内，那么 $2$ 必须得在栈顶，否则它就被卡在栈里了，无法进行排序。

这似乎给了我们一些启发，对于位置 $i < j$ ，如果 $a_i>a_j$ ，那么无所谓， $j$ 可以先弹出。可如果 $a_i < a_j$ ，而且在 $a_j$ 加入时 $a_i$ 仍然在栈中（这意味着存在一个 $k > j$ ，满足 $a_k < a_i$ ），那么它们不能在同一个栈里面，否则就会像之前的 $2$ 一样，被卡死了。
不能共存，这让我们想到了二分图染色，我们尝试建图，构建出约束关系：

对于每一个位置 $i$ ，建立一个点 $v_i$ 。
对于 $i < j$ ，满足 $a_i < a_j$ 且有 $k > j$ 满足 $a_k < a_i$ ，则连接 $v_i\leftrightarrow v_j$ 的无向边。

对这个图进行二分图黑白染色，如果不能染色，那么说明无解。否则这种染色方案对应一个可行解：顺着考虑序列 $P$ ，如果点 $v_i$ 是白色，那么它入栈 $S_1$ ，否则入栈 $S_2$ ，入栈之后能出栈的全部出栈。

不能染色就不存在解是很好理解的，为什么每一个染色方案都能对应一个可行解呢？
我们用归纳法证明，每一个数 $P_i$ 都能弹出：首先数 $1$ 一定能被弹出，我们假设数 $i - 1(i\ge 2)$ 都能被弹出，那么考虑数 $i$ 是否能被弹出，假设 $P_j = i$ ，如果不存在 $k > j$ 使得 $P_k < P_j$ ，说明考虑到位置 $j$ 的时候比它小的数都被弹出了，那么它只需要进行 a, b 操作就能弹出。
如果存在 $k > j$ 使得 $P_k < P_j$ ，那么找到最大的 $k$ 满足 $P_k < P_j$ ，我们要证明，一旦 $P_k$ 弹出，则都能顺着被弹出。接着使用归纳法，首先 $P_k$ 可以被弹出（已经知道一直到 $i - 1$ 都能弹出）；假设 $P_{k} + 1$ 如果不可以被弹出，设 $P_x = P_k + 1$ ，那么 $P_x$ 所在的栈的前面，一定有一个 $P_{l} > P_x$ 挡住了它，由于 $l$ 在栈中比 $x$ 靠近顶部，所以 $x<l$ ，而又有 $k\ge x$ 且 $P_k < P_x$ ，所以再二分图染色的过程中，它们一定不同色，也就是不在一个栈里，而现在却在一个栈中，这就矛盾了，所以 $P_k + 1$ 也能弹出。不停的归纳，所以最终， $P_j$ 也能被弹出。
最后的最后，每一个数 $P_i$ 都能被弹出。

所以，每一个染色方案都能对应一个可行解。自然也容易证明，每一个可行解都能对应一个染色方案，所以染色方案和可行解是等价的。至于求字典序最小的可行解，只需要在染色的时候，按照的顺序来尝试染色，而且每次染色先染白色。

最后一个问题，是不是每次一定都要立即出栈呢？有没有可能先出栈 $S_2$ ，再入栈 $S_1$ ，调整为先入栈 $S_1$ 再出栈 $S_2$ 使得字典序更小的情况呢？这是有可能的，事实上这是一个容易被忽略的点，参见「NOIP 2008 双栈排序」的一点点 Hack。

代码

//  Created by Sengxian on 2016/11/04.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1000 + 3;
int n, a[MAX_N], mn[MAX_N], color[MAX_N];
bool G[MAX_N][MAX_N];

bool Dfs(int u, int c) {
    color[u] = c;
    for (int v = 0; v < n; ++v) if (G[u][v]) {
        if (color[v] == c) return false;
        if (color[v] == 0 && !Dfs(v, -c)) return false;
    }
    return true;
}

stack<int> A, B;
vector<char> ans;
int now = 0;

void go(int i) {
    vector<int> vec;
    while (true) {
        bool update = false;
        if (!A.empty() && A.top() == now) A.pop(), now++, vec.push_back('b'), update = true;
        if (!B.empty() && B.top() == now) B.pop(), now++, vec.push_back('d'), update = true;
        if (!update) break;
    }
    if (i + 1 < n && color[i + 1] == -1) {
        for (int i = vec.size() - 1; i >= 0; --i)
            if (vec[i] == 'b') {
                int len = (int)vec.size() - i - 1;
                for (int k = now - 1; k > now - 1 - len; --k)
                    B.push(k);
                now -= len;
                vec.resize((int)vec.size() - len);
                break;
            }
    }
    ans.insert(ans.end(), vec.begin(), vec.end());
}

void solve() {
    for (int i = 0; i < n; ++i)
        if (color[i] == -1) {
            A.push(a[i]), ans.push_back('a');
            go(i);
        } else if (color[i] == 1) {
            B.push(a[i]), ans.push_back('c');
            go(i);
        }
    for (int i = 0; i < (int)ans.size(); ++i)
        printf("%c%c", ans[i], i + 1 == (int)ans.size() ? '\n' : ' ');
}

int main() {
#ifdef DEBUG
    freopen("test.in", "r", stdin);
#endif
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", a + i), a[i]--;
    mn[n] = n;
    for (int i = n - 1; i >= 0; --i) mn[i] = min(mn[i + 1], a[i]);
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j) if (a[i] < a[j] && mn[j + 1] < a[i])
            G[i][j] = G[j][i] = true;
    for (int i = 0; i < n; ++i) if (!color[i])
        if (!Dfs(i, -1)) return puts("0"), 0;
    solve();
    return 0;
}

BZOJ 2118 - 墨墨的等式 BZOJ 1999 - [Noip2007]Core树网的核

Sengxian's Blog

「NOIP 2008」双栈排序

描述

分析

代码