当每个元素进哪个栈确定时，不确定的只有某个元素进一个栈，和另一个栈弹出元素的顺序。 这种情况，因为要求字典序最小，而 a 栈的所有操作的字典序都小于 b 栈，我们每次有元素进 b 栈前先尽可能把 a 栈能弹出的先弹出。 这样，我们知道，只要确定每个数进入哪个栈，问题就解决了！ 怎么确定呢？？ 也就是确定哪些元素无论是否同时在栈内，都不能进入同一个栈。即，找到所有 i 元素选择进入 a 栈，那么 j 元素只能进入 b 栈的情况。 如果有一个顺序靠前的元素，和一个顺序靠后的元素，前者大于后者，前者和后者可以进入同一个栈，即前面的元素进入没有弹出时，后面的元素进入。 如果有一个顺序靠前的元素 i，和一个顺序靠后的元素 j，前者大小小于后者

解析： 就算知道是二分图染色还是不会TT。 首先考虑怎么判断是否有解。 a [ i ] 和 a [ j ] 不能压入同一个栈（在同一个栈中出现过）⇔ 存在一个k,使得 i < j < k 且 a [ k ] < a [ i ] < a [ j ] 严格证明就比较复杂了，我就说如何感性理解吧（反正在考场上也没几个人会去严格证明）。 因为一个数只能进出一次，k 要排在前面所以弹出 k 时 i 和 j 都在栈里，如果两者在同一个栈弹出后顺序就错误了，然后找不到除这种情况外的反例，于是就这样了。。。 所以如果输入数据不能使得所有限制成立则无解，然后就可以转化成二分图染色来判定，不能在同一个栈中就连边。 关于输出答案，因为要让字典序最小肯定是尽量加在S1里面，实在不行加进S2。 代码: 欢迎加入团队

#include<bits/stdc++.h> using namespace std; int n, N, x, k, tot, sum = 1, p1 = 1001, p2 = 1001; int a[1001], f[1005], c[1001], t[2005], head[1005]; char s[5] = {'0', 'a', 'b', 'c', 'd'}; vector<int> p[1001]; queue<int> q; stack<int> s1, s2; struct edge { int next, to; } e[2000005]; inline void add(int x, int y) { ++tot; e[tot].next = head[x]; e[tot].to = y; head[x] = tot; } inline int read() { int x = 0; bool f = 1; char ch = getchar(); while (ch > '9' || ch < '0') { if (ch == '-') f = 0; ch = getchar(); } while (ch <= '9' && ch >= '0') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } return f ? x : -x; } int main() { n = read(), f[n + 1] = n + 1, N = 2 * n; }