博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【codevs1170】 双栈排序
阅读量:5117 次
发布时间:2019-06-13

本文共 1181 字,大约阅读时间需要 3 分钟。

 (题目链接)

题意

  给出一个初始序列,判断能否通过两个栈的入栈和出栈操作构造出一个有序序列。若可以,输出字典序最小的方案。

Solution

  还是想狙LCF才看的这道题,真的是很神啊。考场绝对做不出的题之一。

  网上题解一大piang,那个结论其实很好YY出来,只是想不到转换到二分图染色上面去。。

代码

// codevs1170#include
#include
#include
#include
#include
#include
#define LL long long#define MOD 100000000#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=1010;struct edge {int to,next;}e[maxn<<1];int c[maxn],head[maxn],a[maxn],f[maxn],s1[maxn],s2[maxn];int t1,t2,n,cnt;void link(int u,int v) { e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt; e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;}bool color(int x,int cl) { c[x]=cl; for (int i=head[x];i;i=e[i].next) { if (!c[e[i].to]) {if (!color(e[i].to,3-cl)) return 0;} else if (c[e[i].to]==cl) return 0; } return 1;}int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); f[n+1]=inf; for (int i=n;i;i--) f[i]=min(f[i+1],a[i]); for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) if (a[i]

  

转载于:https://www.cnblogs.com/MashiroSky/p/5930693.html

你可能感兴趣的文章
JS动画代码
查看>>
泥泞的道路
查看>>
简单爬虫
查看>>
Swift - UIDatePicker
查看>>
近期计划
查看>>
Storm入门(一)原理介绍
查看>>
bzoj 3351 [ioi2009]Regions
查看>>
ascii函数
查看>>
代理模式
查看>>
PS设计漂亮网站主页图片的实例教程
查看>>
个人工作总结01
查看>>
[USACO09NOV]硬币的游戏A Coin Game
查看>>
第二周课程进度
查看>>
PowerPivot excel 2010 for sql
查看>>
Eclipse常用设置
查看>>
上传文件 tmp_name 为空
查看>>
css 样式 文字过长 换行处理方法
查看>>
PHP IDE phpstorm 常用快捷键
查看>>
iOS:触摸控件UITouch、事件类UIEvent
查看>>
ThinkPad T430 安装Win7 64Bit
查看>>