题目大意
运用两个栈的 push 和 pop 操作使得一个序列单调递增且操作字典序最小.$n\leq 1000$.
题解
本题我们要尝试运用 "瞪眼法", 也就是推样例. 我们显然要数字尽可能地推入第一个栈. 那么问题就是: 怎样的两个数字不可以在同一个栈中呢? 这样的效果是: 当一个数字 a 想要出栈时, 其上端有个被他大的数字 b 挡着, 且是不得不挡着. 怎么会 "不得不" 呢? 那是因为有一个数字 c<a 在 b 的上面 (原序列中, c 在 b 的右面), 因为要想使输出序列递增, 必须把 b 入了栈以后才能出栈. 所以, a 和 c 不能共存. 将所有满足 a,c 这样的条件的点连边, 进行二分图染色 (进入栈的编号)(染不了色输出 - 1), 然后模拟即可.
- #include
- #include
- #include
- #include
- #include
- using namespace std;
- const int MAX_NODE = 1010, MAX_EDGE = MAX_NODE * MAX_NODE;
- vector Ops;
- struct Node;
- struct Edge;
- struct Node
- {
- Edge *Head;
- int Color;
- }_nodes[MAX_NODE];
- int TotNode;
- Node *A[MAX_NODE];
- stack<Node*> St[3];
- struct Edge
- {
- Node *To;
- Edge *Next;
- }_edges[MAX_EDGE];
- int _eCount;
- void Dfs(Node *cur, int color)
- {
- if (cur->Color && cur->Color != color)
- {
- printf("0\n");
- exit(0);
- }
- if (cur->Color)
- return;
- cur->Color = color;
- for (Edge *e = cur->Head; e; e = e->Next)
- Dfs(e->To, color == 1 ? 2 : 1);
- }
- void AddEdge(Node *from, Node *to)
- {
- Edge *e = _edges + ++_eCount;
- e->To = to;
- e->Next = from->Head;
- from->Head = e;
- }
- void Build(Node *u, Node *v)
- {
- AddEdge(u, v);
- AddEdge(v, u);
- }
- void BuildGraph()
- {
- static Node *AftMinV[MAX_NODE];
- AftMinV[TotNode] = A[TotNode];
- for (int i = TotNode - 1; i>= 1; i--)
- AftMinV[i] = min(A[i], AftMinV[i + 1]);
- for (int i = 1; i <= TotNode; i++)
- for (int j = i + 1; j <= TotNode; j++)
- if (A[i] <A[j] && AftMinV[j] <A[i])
- Build(A[i], A[j]);
- }
- int main()
- {
- scanf("%d", &TotNode);
- for (int i = 1; i <= TotNode; i++)
- {
- int vId;
- scanf("%d", &vId);
- A[i] = _nodes + vId;
- }
- BuildGraph();
- for (int i = 1; i <= TotNode; i++)
- if (!A[i]->Color)
- Dfs(A[i], 1);
- Node *cur = _nodes + 1;
- for (int i = 1; i <= TotNode; i++)
- {
- Ops.push_back(A[i]->Color == 1 ? 'a' : 'c');
- St[A[i]->Color].push(A[i]);
- while (!St[cur->Color].empty() && St[cur->Color].top() == cur)
- {
- St[cur->Color].pop();
- Ops.push_back(cur->Color == 1 ? 'b' : 'd');
- cur++;
- }
- }
- for (unsigned int i = 0; i < Ops.size(); i++)
- printf("%c", Ops[i]);
- printf("\n");
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2806608.html