题目详情提交记录（0）

题解

userId_undefined

法兰西玫瑰

2023-03-04 17:42:33

发布于：上海

440阅读
0回复
0点赞

#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;
}
加粗文本

userId_undefined
去预览
0/2000

全部评论 4

  • userId_undefined

    你猜

    空间掌握者循环·循环打卡人分支·分支解题者

    #include<bits/stdc++.h>
    using namespace std;
    const int Max=1010;
    int n,m=1,size,tot1,tot2,p1[Max],p2[Max],first[Max],f[Max],num[Max],vis[Max];
    struct shu{int to,next,len;}edge[MaxMax];
    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(colorvis[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(m    p1[tot1]||m    p2[tot2]) {
    if(m==p1[tot1]) tot1--,printf("b ");
    else tot2--,printf("d ");
    m++;
    }
    }
    }

    2025-09-24 来自 浙江

    0
  • userId_undefined

    ༺ཌༀ༒RDS༒ༀད༻（必回关）

    出道萌新时间刺客空间掌握者时空双修者荣耀黄金快乐小狗

    /code/judger/run/20250722/5054479695523872865/main.cpp: In function 'void push_and_pop()':
    /code/judger/run/20250722/5054479695523872865/main.cpp:35:29: error: expected ')' before 'i'
    35 | if((!st1.empty())&&st1.top()i){
    | ~ ^
    | )
    /code/judger/run/20250722/5054479695523872865/main.cpp:39:34: error: expected ')' before 'i'
    39 | else if((!st2.empty())&&st2.top()i){
    | ~ ^
    | )
    /code/judger/run/20250722/5054479695523872865/main.cpp:42:4: error: 'x1' was not declared in this scope; did you mean 'x'?
    42 | if(x1){
    | ^~
    | x
    compilation terminated due to -fmax-errors=3.

    2025-07-22 来自 重庆

    0
  • userId_undefined

    两袖清风

    /code/judger/run/20250525/5043992401935368290/main.cpp: In function 'void push_and_pop()':
    /code/judger/run/20250525/5043992401935368290/main.cpp:35:29: error: expected ')' before 'i'
    35 | if((!st1.empty())&&st1.top()i){
    | ~ ^
    | )
    /code/judger/run/20250525/5043992401935368290/main.cpp:39:34: error: expected ')' before 'i'
    39 | else if((!st2.empty())&&st2.top()i){
    | ~ ^
    | )
    /code/judger/run/20250525/5043992401935368290/main.cpp:42:4: error: 'x1' was not declared in this scope; did you mean 'x'?
    42 | if(x1){
    | ^~
    | x
    compilation terminated due to -fmax-errors=3.

    2025-05-25 来自 北京

    0
  • userId_undefined

    复仇者_远航

    倔强青铜

    编译错误: /code/judger/test/1766263593769795584/main11.cpp: In function 'void push_and_pop()':
    /code/judger/test/1766263593769795584/main11.cpp:35:29: error: expected ')' before 'i'
    if((!st1.empty())&&st

    2024-03-09 来自 浙江

    0
    • userId_undefined

      Man肘牢大666

      回复复仇者_远航

      /code/judger/run/20251011/5069229225796436065/main.cpp: In function 'void push_and_pop()':
      /code/judger/run/20251011/5069229225796436065/main.cpp:35:29: error: expected ')' before 'i'
      35 | if((!st1.empty())&&st1.top()i){
      | ~ ^
      | )
      /code/judger/run/20251011/5069229225796436065/main.cpp:39:34: error: expected ')' before 'i'
      39 | else if((!st2.empty())&&st2.top()i){
      | ~ ^
      | )
      /code/judger/run/20251011/5069229225796436065/main.cpp:42:4: error: 'x1' was not declared in this scope; did you mean 'x'?
      42 | if(x1){
      | ^~
      | x
      compilation terminated due to -fmax-errors=3.

      2025-10-11 来自 浙江

      0
暂无数据

提交答案之后，这里将显示提交结果～

首页