首页 > 代码库 > BZOJ 2080: [Poi2010]Railway 双栈排序

BZOJ 2080: [Poi2010]Railway 双栈排序

2024-08-20 22:24:47   225人阅读

2080: [Poi2010]Railway

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 140  Solved: 35
[Submit][Status][Discuss]

Description

一个铁路包含两个侧线1和2，右边由A进入，左边由B出去（看下面的图片）
 技术分享 
有n个车厢在通道A上，编号为1到n，它们被安排按照要求的顺序（a1,a2,a3,a4....an）进入侧线，进去还要出来，它们要按照编号顺序（1，2，3，4，5。。。。n）从通道B出去。他们从A到1或2，然后经过一系列转移从B出去，不用考虑容量问题。

Input

输入：第一行一个整数n（1<=n<=100000）表示要转移的车厢总数，第二行为进入侧线的要求顺序a1.a2.a3.a4....an，由空格隔开。

Output

输出：如果可以按照编号顺序到通道B，则输出两行，第一行为TAK，第二行为n个由空格隔开的整数，表示每个车厢进入的侧线编号（1,2）。否则输出NIE。

Sample Input

[样例输入1]
4
1 3 4 2
[样例输入2]
4
2 3 4 1

Sample Output

[样例输出1]
TAK
1 1 2 1 （1号线进到侧线1，然后出来，3号进入侧线1,4号进入侧线2,2号进入侧线1，然后出来，接着3号出来，4号出来）
[样例输出2]
NIE （不可能。。No）

HINT

 

Source

By poi

[Submit][Status][Discuss]

 

分析

本题和 NOIP 2008 提高组 的 双栈排序 是类似的。

 

首先，考虑一个序列满足双栈排序，需要什么样的性质。

发现，如果点i如栈，那么在i之前的值大于a[i]的点都不可能出栈，那么它们出来的时候一定和入栈的顺序刚好相反。

如果，其入栈不是递减的，出栈就不会是递增的。后来发现，这也是序列满足双栈排序的充要条件。

 

因此，对于所有的i<j<k且有a[k]<a[i]<a[k]，在i和j之间连边。每条边上的两个点不能在同一个栈中。做染色即可。

 

双栈排序数据太水，不用刻意调整顺序即可AC，而且边很少。

 

代码

 

技术分享 
  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 const int N = 2005;
  6 
  7 int n, num[N];
  8 
  9 int low[N], col[N];
 10 
 11 int hd[N], to[N], nt[N], tot;
 12 
 13 void addEdge(int x, int y)
 14 {
 15     nt[++tot] = hd[x]; to[tot] = y; hd[x] = tot;
 16     nt[++tot] = hd[y]; to[tot] = x; hd[y] = tot;
 17 }
 18 
 19 bool dfs(int u, int c)
 20 {
 21     if (col[u] != -1)
 22         return col[u] != c;
 23 
 24     col[u] = c;
 25     
 26     for (int i = hd[u]; i; i = nt[i])
 27         if (dfs(to[i], c ^ 1))return true;
 28         
 29     return false;
 30 }
 31 
 32 int stk1[N], tot1;
 33 int stk2[N], tot2;
 34 int ans[N], cnt, t(1);
 35 
 36 void pop(void)
 37 {
 38     if (tot1 && stk1[tot1] == t)
 39         { ans[++cnt] = 1, --tot1, ++t; pop(); }
 40     if (tot2 && stk2[tot2] == t)
 41         { ans[++cnt] = 3, --tot2, ++t; pop(); }
 42 }
 43 
 44 void putAns(void)
 45 {
 46     for (int i = 1; i <= n; ++i)
 47     {
 48         pop();
 49         
 50         switch (col[i])
 51         {
 52             case 0: 
 53             {
 54                 stk1[++tot1] = num[i];
 55                 ans[++cnt] = 0;
 56                 break;
 57             }
 58             case 1:
 59             {
 60                 stk2[++tot2] = num[i];
 61                 ans[++cnt] = 2;
 62                 break;
 63             }
 64         }
 65     }
 66     
 67     pop();
 68     
 69     for (int i = 1; i <= cnt; ++i)
 70         printf("%c ", ‘a‘ + ans[i]);
 71 }
 72 
 73 signed main(void)
 74 {
 75     scanf("%d", &n);
 76     
 77     for (int i = 1; i <= n; ++i)
 78         scanf("%d", num + i);
 79         
 80     low[n] = num[n];
 81         
 82     for (int i = n; i >= 2; --i)
 83         low[i - 1] = min(num[i], low[i]);
 84         
 85     for (int i = 1; i < n; ++i)
 86         for (int j = 1 + i; j <= n; ++j)
 87             if (num[i] < num[j] && num[i] > low[j])
 88                 addEdge(i, j);
 89                 
 90     bool flag = true;
 91     
 92     memset(col, -1, sizeof(col));
 93     
 94     for (int i = 1; i <= n; ++i)
 95         if (col[i] == -1)if (dfs(i, 0))
 96             { flag = false; break; }
 97             
 98     if (flag)
 99         putAns();
100     else
101         puts("0");
102 }
双栈排序.cpp

 

 

@Author: YouSiki

BZOJ 2080: [Poi2010]Railway 双栈排序


联系
我们