#include<bits/stdc++.h> using namespace std; int n; int num[1005]; int f_min[1005];//find_min，f_min[i]表示i右侧能找到的最小数 set<int> g[1005];//用set来建图 int color[1005];//记录染色的情况，用1和2代表颜色 int cnt1,cnt2; bool bfs(int s){//s是起点 queue<int> q; q.push(s); color[s]=1; while(!q.empty()){ int a=q.front(); q.pop(); for(auto i=g[a].begin();i!=g[a].end();i++){ if(!color[(*i)]){//没染过色 color[(*i)]=3-color[a]; q.push((*i)); } else if(color[(*i)]==color[a]){//染色出现矛盾 return false; } } } return true; } void push_and_pop(){ stack<int> st1,st2; int it=1; for(int i=1;i<=n;i++){//i表示当前应当输出的数字 if((!st1.empty())&&st1.top()i){ printf("b "); st1.pop(); } else if((!st2.empty())&&st2.top()i){ while(num[it]!=i+1&&it<=n){//在进行d操作之前尽量多地进行a操作 int x=color[it]; if(x1){ st1.push(num[it]); printf("a "); } else if(x2){ break; st2.push(num[it]); printf("c "); } it++; } if(color[it]1){//特判，把i-1这个数放进stack1 st1.push(num[it]); printf("a "); it++; } printf("d "); st2.pop(); } else{ while(num[it]!=i&&it<=n){ int x=color[it]; if(x1){ st1.push(num[it]); printf("a "); } else if(x==2){ st2.push(num[it]); printf("c "); } it++; } printf("a b "); it++; } } } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&num[i]); } for(int i=1;i<n;i++){ int t=num[i]; for(int j=i+1;j<=n;j++){ t=min(t,num[j]); } f_min[i]=t; } for(int i=1;i<n;i++){ for(int j=i+1;j<n;j++){ if(num[i]<num[j]){ if(f_min[j]<num[i]){ g[i].insert(j); g[j].insert(i);//建无向图 } } } } for(int i=1;i<=n;i++){ if(!color[i]){ bool f=bfs(i); if(!f){ printf("0"); return 0; } } } for(int i=1;i<=n;i++){ if(color[i]==2)cnt2++; else cnt1++; } if(cnt2>cnt1){//让染完色后数量多的一方使用A栈 for(int i=1;i<=n;i++){ if(color[i]==2)color[i]=1; else color[i]=2; } } push_and_pop(); return 0; } 加粗文本

#include<bits/stdc++.h> using namespace std; bool bfs(int s){//s是起点 queue<int> q; q.push(s); color[s]=1; while(!q.empty()){ int a=q.front(); q.pop(); for(auto i=g[a].begin();i!=g[a].end();i++){ if(!color[(*i)]){//没染过色 color[(*i)]=3-color[a]; q.push((*i)); } else if(color[(*i)]==color[a]){//染色出现矛盾 return false; } } } return true; } void push_and_pop(){ stack<int> st1,st2; int it=1; for(int i=1;i<=n;i++){//i表示当前应当输出的数字 if((!st1.empty())&&st1.top()i){ printf(*b *); st1.pop(); } else if((!st2.empty())&&st2.top()i){ while(num[it]!=i+1&&it<=n){//在进行d操作之前尽量多地进行a操作 int x=color[it]; if(x1){ st1.push(num[it]); printf(*a *); } else if(x2){ break; st2.push(num[it]); printf(*c *); } it++; } if(color[it]1){//特判，把i-1这个数放进stack1 st1.push(num[it]); printf(*a *); it++; } printf(*d *); st2.pop(); } else{ while(num[it]!=i&&it<=n){ int x=color[it]; if(x1){ st1.push(num[it]); printf(*a *); } else if(x==2){ st2.push(num[it]); printf(*c *); } it++; } printf(*a b *); it++; } } } int main(){ scanf(*%d*,&n); for(int i=1;i<=n;i++){ scanf(*%d*,&num[i]); } for(int i=1;i<n;i++){ int t=num[i]; for(int j=i+1;j<=n;j++){ t=min(t,num[j]); } f_min[i]=t; } for(int i=1;i<n;i++){ for(int j=i+1;j<n;j++){ if(num[i]<num[j]){ if(f_min[j]<num[i]){ g[i].insert(j); g[j].insert(i);//建无向图 } } } } for(int i=1;i<=n;i++){ if(!color[i]){ bool f=bfs(i); if(!f){ printf("0"); return 0; } } } for(int i=1;i<=n;i++){ if(color[i]==2)cnt2++; else cnt1++; } if(cnt2>cnt1){//让染完色后数量多的一方使用A栈 for(int i=1;i<=n;i++){ if(color[i]==2)color[i]=1; else color[i]=2; } } push_and_pop(); return 0; }

解析： 就算知道是二分图染色还是不会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; int num[1005]; int f_min[1005];//find_min，f_min[i]表示i右侧能找到的最小数 set<int> g[1005];//用set来建图 int color[1005];//记录染色的情况，用1和2代表颜色 int cnt1,cnt2; bool bfs(int s){//s是起点 queue<int> q; q.push(s); color[s]=1; while(!q.empty()){ int a=q.front(); q.pop(); for(auto i=g[a].begin();i!=g[a].end();i++){ if(!color[(*i)]){//没染过色 color[(*i)]=3-color[a]; q.push((*i)); } else if(color[(*i)]==color[a]){//染色出现矛盾 return false; } } } return true; } void push_and_pop(){ stack<int> st1,st2; int it=1; for(int i=1;i<=n;i++){//i表示当前应当输出的数字 if((!st1.empty())&&st1.top()i){ printf("b "); st1.pop(); } else if((!st2.empty())&&st2.top()i){ while(num[it]!=i+1&&it<=n){//在进行d操作之前尽量多地进行a操作 int x=color[it]; if(x1){ st1.push(num[it]); printf("a "); } else if(x2){ break; st2.push(num[it]); printf("c "); } it++; } if(color[it]1){//特判，把i-1这个数放进stack1 st1.push(num[it]); printf("a "); it++; } printf("d "); st2.pop(); } else{ while(num[it]!=i&&it<=n){ int x=color[it]; if(x1){ st1.push(num[it]); printf("a "); } else if(x==2){ st2.push(num[it]); printf("c "); } it++; } printf("a b "); it++; } } } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&num[i]); } for(int i=1;i<n;i++){ int t=num[i]; for(int j=i+1;j<=n;j++){ t=min(t,num[j]); } f_min[i]=t; } for(int i=1;i<n;i++){ for(int j=i+1;j<n;j++){ if(num[i]<num[j]){ if(f_min[j]<num[i]){ g[i].insert(j); g[j].insert(i);//建无向图 } } } } for(int i=1;i<=n;i++){ if(!color[i]){ bool f=bfs(i); if(!f){ printf("0"); return 0; } } } for(int i=1;i<=n;i++){ if(color[i]==2)cnt2++; else cnt1++; } if(cnt2>cnt1){//让染完色后数量多的一方使用A栈 for(int i=1;i<=n;i++){ if(color[i]==2)color[i]=1; else color[i]=2; } } push_and_pop(); return 0; }

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

#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]; // p[i]统计i的边 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; for (int i = 1; i <= n; ++i) a[i] = read(); for (int i = n; i >= 1; --i) f[i] = min(f[i + 1], a[i]); // 寻找i为起点的最小值，注意从n开始 }

#include <bits/stdc++.h> using namespace std; const int N = 1e4+10; int n, K = 1, a[N], ka, adr[N]; bool vis[N]; stack<int> S1, S2; char ans[N << 1]; bool f(int x, int y) { for (int i = x; i <= y; i++) { if (!vis[i]) return false; } return true; } bool check(int x) { if (S2.empty()) return true; memset(vis, 0, sizeof(vis)); for (int i = adr[x]; i <= max(adr[S1.top() - 1], adr[K]); i++) { vis[a[i]] = true; } if (f(S2.top() + 1, n)) return false; return true; } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; adr[a[i]] = i; } for (int i = 1; i <= n; i++) { if (S1.empty() || (!S2.empty() && S2.top() < a[i] && S1.top() > a[i])) { S1.push(a[i]); ans[ka++] = 'a'; } else if (!S1.empty() && S1.top() < a[i]) { if (S2.empty() || S2.top() > a[i]) { S2.push(a[i]); ans[ka++] = 'c'; } else { cout << "0"; return 0; } } else { if (a[i] == K) { S1.push(a[i]); ans[ka++] = 'a'; } else if (a[i] == S1.top() - 1) { S1.push(a[i]); ans[ka++] = 'a'; } else if (!S2.empty() && a[i] == S2.top() - 1) { S2.push(a[i]); ans[ka++] = 'c'; } else { if (check(a[i])) { S1.push(a[i]); ans[ka++] = 'a'; } else { S2.push(a[i]); ans[ka++] = 'c'; } } } while ((!S1.empty() && S1.top() == K) || (!S2.empty() && S2.top() == K)) { if (!S1.empty() && S1.top() == K) { ans[ka++] = 'b'; S1.pop(); K++; } else if (!S2.empty() && S2.top() == K) { ans[ka++] = 'd'; S2.pop(); K++; } } } for (int i = 0; i < (n << 1); i++) { for (int j = 0; j < (n << 1) - 1; j++) { if ((ans[j] == 'd' && ans[j + 1] == 'a') || (ans[j] == 'c' && ans[j + 1] == 'b')) { swap(ans[j], ans[j + 1]); } } } for (int i = 0; i < (n << 1); i++) { cout << ans[i] << " "; } return 0; }

#include<bits/stdc++.h> using namespace std; int n; int num[1005]; int f_min[1005]; set<int> g[1005]; int color[1005]; int cnt1,cnt2; bool bfs(int s){ queue<int> q; q.push(s); color[s]=1; while(!q.empty()){ int a=q.front(); q.pop(); for(auto i=g[a].begin();i!=g[a].end();i++){ if(!color[(*i)]){ color[(*i)]=3-color[a]; q.push((*i)); } else if(color[(*i)]color[a]){ return false; } } } return true; } void push_and_pop(){ stack<int> st1,st2; int it=1; for(int i=1;i<=n;i++){ if((!st1.empty())&&st1.top()i){ printf("b "); st1.pop(); } else if((!st2.empty())&&st2.top()i){ while(num[it]!=i+1&&it<=n){ int x=color[it]; if(x1){ st1.push(num[it]); printf("a "); } else if(x2){ break; st2.push(num[it]); printf("c "); } it++; } if(color[it]1){ st1.push(num[it]); printf("a "); it++; } printf("d "); st2.pop(); } else{ while(num[it]!=i&&it<=n){ int x=color[it]; if(x1){ st1.push(num[it]); printf("a "); } else if(x2){ st2.push(num[it]); printf("c "); } it++; } printf("a b "); it++; } } } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&num[i]); } for(int i=1;i<n;i++){ int t=num[i]; for(int j=i+1;j<=n;j++){ t=min(t,num[j]); } f_min[i]=t; } for(int i=1;i<n;i++){ for(int j=i+1;j<n;j++){ if(num[i]<num[j]){ if(f_min[j]<num[i]){ g[i].insert(j); g[j].insert(i); } } } } for(int i=1;i<=n;i++){ if(!color[i]){ bool f=bfs(i); if(!f){ printf("0"); return 0; } } } for(int i=1;i<=n;i++){ if(color[i]==2)cnt2++; else cnt1++; } if(cnt2>cnt1){ for(int i=1;i<=n;i++){ if(color[i]==2)color[i]=1; else color[i]=2; } } push_and_pop(); return 0; }

#include <bits/stdc++.h> using namespace std; const int Max=1010; int n,m=1,size,tot1,tot2,p1[Max],p2[Max]; int first[Max],f[Max],num[Max],vis[Max]; struct shu{int to,next,len;}edge[Max*Max]; inline int get_int() { int x=0,f=1; char c; for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar()); if(c=='-') f=-1,c=getchar(); for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0'; return x*f; } inline void build(int x,int y) { edge[++size].next=first[x],first[x]=size,edge[size].to=y; edge[++size].next=first[y],first[y]=size,edge[size].to=x; } inline void pre() { f[n]=num[n]; for(int i=n-1;i>=1;i--) f[i]=min(f[i+1],num[i]); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(f[j]<num[i]&&num[i]<num[j]) build(i,j); } inline bool dfs(int p,int color) { vis[p]=color; for(int u=first[p];u;u=edge[u].next) { int to=edge[u].to; if(!vis[to]) dfs(to,3-color); else if(color==vis[to]) return 0; } return 1; } int main() { n=get_int(); for(int i=1;i<=n;i++) num[i]=get_int(); pre(); for(int i=1;i<=n;i++) if(!vis[i]&&!dfs(i,1)) {puts("0");return 0;} for(int i=1;i<=n;i++) { if(vis[i]1)p1[++tot1]=num[i],printf("a "); else p2[++tot2]=num[i],printf("c "); while(mp1[tot1]||mp2[tot2]) { if(mp1[tot1]) tot1--,printf("b "); else tot2--,printf("d "); m++; } } return 0; } 欢迎加入团队