Luogu: p1155 [noip2008 improvement group] double stack sorting (bipartite graph, simulation)

Twin City Inn

• First step ： Determine whether double stack sorting can be done

To understand perceptually , We want the final output sequence to be Ascending , Obviously, the number in the stack should be guaranteed to be Descending Of ;

Excerpt from zjp_shadow The antithesis of

{1,2,3} This set of data can be put into the same stack , Just put it in and take it out immediately

If the bipartite graph is dyed successfully , Each number will get a color , Numbers of the same color must be in a stack

• The second step ： Output the sorting of the minimum dictionary order

A more troublesome simulation , There are many situations that need special judgment

Because the order of different operations will affect the dictionary order , We should give priority to the entry and exit of the first stack , Consider the second stack , namely ： Stack 2 Consider the stack before any operation of 1 Can you operate

At the same time, it's very important , The resulting sequence is required to be in ascending order ：{1、2、3、4…}, We have to record which number should pop up every time , Don't play in the wrong order .

Code：

#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define sca scanf
#define pri printf
#define ul (u << 1)
#define ur (u << 1 | 1)
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define rfor(a,b,c) for(int a=b;a>=c;a--)
//[ Blog address ]：https://blog.csdn.net/weixin_51797626?t=1
using namespace std;
inline int read() {
     int x = 0, f = 1, ch = getchar(); while (ch < '0' || ch>'9') {
     if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') {
     x = x * 10 + ch - '0'; ch = getchar(); } return x * f; }
inline void write(int x) {
     if (x < 0) putchar('-'), x = -x; if (x >= 10) write(x / 10); putchar(x % 10 + '0'); }

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;

const int N = 1010, M = 400010, MM = N;
int INF = 0x3f3f3f3f, mod = 998244353;
ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, k, T, S, D;
int g[N][N], qmin[N];
int a[N], color[N], top = 1;
stack<int> aa, cc;
bool st[N];

bool col(int x, int c) {
    
	color[x] = c;
	for (int j = 1; j <= n; j++)
		if (g[x][j]) {
    
			if (!color[j]) {
    
				if (!col(j, 3 - c))return false;
			}
			else if (c == color[j])return false;
		}
	return true;
}

inline void popp(stack<int>& aa, int x) {
    
	aa.pop();
	if (x == 1)cout << " b";
	else cout << " d";
	top++;
}

inline bool check(stack<int>& aa) {
    
	return aa.size() && aa.top() == top;// Judge whether the top of the stack is the current number of the bomb 
}

void solve() {
    
	cin >> n;
	forr(i, 1, n)cin >> a[i];

	qmin[n + 1] = n + 1;
	rfor(i, n, 1)qmin[i] = min(a[i], qmin[i + 1]);// Preprocess a suffix min

	forr(i, 1, n - 2)
		forr(j, i + 1, n - 1)
		if (a[i] < a[j] && qmin[j + 1] < a[i])// If and only if 
			g[i][j] = g[j][i] = 1;// We can judge i、j Cannot be the same color 

	forr(i, 1, n)
		if (!color[i]) {
    
			if (!col(i, 1)) {
     // Dichotomous coloring 
				cout << 0;
				return;
			}
		}

	top = 1;
	bool f = false;
	forr(i, 1, n) {
    
		if (color[i] == 1) {
    
			while (aa.size() && aa.top() < a[i]) {
     
				// If there is more than the number to be inserted in the current stack （a[i]） Small number 
				// Obviously, it will bounce  a[i]  until 
				// But not all these numbers are on the stack 1 in , So judge the bomb stack 1 Or stack 2, Bomb stack 1 Just pop the stack 1

				if (check(aa))popp(aa, 1);
				else popp(cc, 2);
			}
			aa.push(a[i]);
			if (!f)f = true, cout << "a";
			else cout << " a";
		}
		else {
    
			// a key ：
			// Bomb stack 2 Before , We give priority to stack 1 I can play it all , This will ensure the minimum dictionary order 
			while (check(aa))popp(aa, 1);
			while (cc.size() && cc.top() < a[i]) {
    
				if (check(cc))popp(cc, 2);
				else popp(aa, 1);
			}
			while (check(aa))popp(aa, 1);// And then again 
			// Anyway, stack 2 Do stack before any operation of 1 The operation of ！

			cc.push(a[i]);
			if (!f)f = true, cout << "c";
			else cout << " c";
		}
	}

	// Finally, play all 
	while (aa.size()) {
    
		if (check(aa))popp(aa, 1);
		else popp(cc, 2);
	}
	while (cc.size())popp(cc, 2);
}

int main() {
    
	cinios;

	solve();

	return 0;
}
/* */