SQYBI.com

这可能是第一份正确的完整题解.

这个帖子: http://www.oibh.org/bbs/thread-26983-1-2.html 是此算法的来源,但是帖子中说的不是很清楚,而且没有证明.题解中将把这些问题解决.
十分感谢inzaghi250(sqybi注:还好我不是inzaghi的fans…)提供的算法.

这道题大概可以归结为如下题意:
有两个队列和两个栈,分别命名为队列1(q1),队列2(q2),栈1(s1)和栈2(s2).最初的时候,q2,s1和s2都为空,而q1中有n个数(n<=1000),为1~n的某个排列.
现在支持如下四种操作:
a操作,将 q1的首元素提取出并加入s1的栈顶.
b操作,将s1的栈顶元素弹出并加入q1q2的队列尾.
c操作,将 q1的首元素提取出并加入s2的栈顶.
d操作,将s2的栈顶元素弹出并加入q1q2的队列尾.
请判断,是否可以经过一系列操作之后,使得q2中依次存储着1,2,3,…,n.如果可以,求出字典序最小的一个操作序列.

这道题的错误做法很多,错误做法却能得满分的也很多,这里就不多说了.直接切入正题,就是即将介绍的这个基于二分图的算法.
注意到并没有说基于二分图匹配,因为这个算法和二分图匹配无关.这个算法只是用到了给一个图着色成二分图.

第一步需要解决的问题是,判断是否有解.

考虑对于任意两个数q1[i]和q1[j]来说,它们不能压入同一个栈中的充要条件是什么(注意没有必要使它们同时存在于同一个栈中,只是压入了同一个栈).实际上,这个条件p是:存在一个k,使得i<j<k且q1[k]<q1[i]<q1[j].

首先证明充分性,即如果满足条件p,那么这两个数一定不能压入同一个栈.这个结论很显然,使用反证法可证.
假设这两个数压入了同一个栈,那么在压入q1[k]的时候栈内情况如下:
…q1[i]…q1[j]…
因为q1[k]比q1[i]和q1[j]都小,所以很显然,当q1[k]没有被弹出的时候,另外两个数也都不能被弹出(否则q2中的数字顺序就不是1,2,3,…,n了).
而之后,无论其它的数字在什么时候被弹出,q1[j]总是会在q1[i]之前弹出.而q1[j]>q1[i],这显然是不正确的.

接下来证明必要性.也就是,如果两个数不可以压入同一个栈,那么它们一定满足条件p.这里我们来证明它的逆否命题,也就是"如果不满足条件p,那么这两个数一定可以压入同一个栈."
不满足条件p有两种情况:一种是对于任意i<j<k且q1[i]<q1[j],q1[k]>q1[i];另一种是对于任意i<j,q1[i]>q1[j].
第一种情况下,很显然,在q1[k]被压入栈的时候,q1[i]已经被弹出栈.那么,q1[k]不会对q1[j]产生任何影响(这里可能有点乱,因为看起来,当q1[j]<q1[k]的时候,是会有影响的,但实际上,这还需要另一个数r,满足j<k<r且q1[r]<q1[j]<q1[k],也就是证明充分性的时候所说的情况…而事实上我们现在并不考虑这个r,所以说q1[k]对q1[j]没有影响).
第二种情况下,我们可以发现这其实就是一个降序序列,所以所有数字都可以压入同一个栈.
这样,原命题的逆否命题得证,所以原命题得证.

此时,条件p为q1[i]和q1[j]不能压入同一个栈的充要条件也得证.

这样,我们对所有的数对(i,j)满足1<=i<j<=n,检查是否存在i<j<k满足p1[k]<p1[i]<p1[j].如果存在,那么在点i和点j之间连一条无向边,表示p1[i]和p1[j]不能压入同一个栈.此时想到了什么?那就是二分图~
二分图的两部分看作两个栈,因为二分图的同一部分内不会出现任何连边,也就相当于不能压入同一个栈的所有结点都分到了两个栈中.
此时我们只考虑检查是否有解,所以只要O(n)检查出这个图是不是二分图,就可以得知是否有解.

此时,检查有解的问题已经解决.接下来的问题是,如何找到字典序最小的解.
实际上,可以发现,如果把二分图染成1和2两种颜色,那么结点染色为1对应当前结点被压入s1,为2对应被压入s2.为了字典序尽量小,我们希望让编号小的结点优先压入s1.
又发现二分图的不同连通分量之间的染色是互不影响的,所以可以每次选取一个未染色的编号最小的结点,将它染色为1并从它开始DFS染色,直到所有结点都被染色为止.这样,我们就得到了每个结点应该压入哪个栈中.接下来要做的,只不过是模拟之后输出序列啦~

还有一点小问题,就是如果对于数对(i,j),都去枚举检查是否存在k使得p1[k]<p1[i]<p1[j]的话,那么复杂度就升到了O(n^3).解决方法就是,首先预处理出数组b,b[i]表示从p1[i]到p1[n]中的最小值.接下来,只需要枚举所有数对(i,j),检查b[j+1]是否小于p1[i]且p1[i]是否小于p1[j]就可以了.

附代码(除去注释不到100行),带注释.代码中的a数组对应文中的队列p1.
已经过掉所有标准数据,以及5 7 2 4 1 6 3这组让很多贪心程序挂掉的数据~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

#include <iostream>
 
using namespace std;
 
const int nn = 1002, mm = nn * 2, inf = 1000000000;
int n, tot, now;
int a[nn], b[nn], head[nn], color[nn];
int adj[mm], next[mm];
int stack[3][nn];
bool result;
 
void addEdge(int x, int y) //加边
{
    ++ tot;
    adj[tot] = y;
    next[tot] = head[x];
    head[x] = tot;
}
 
bool dfs(int i) //DFS染色,检查图是否是二分图的经典算法
{
    int temp = head[i];
    while (temp) //邻接表,检查每一条边
    {
        if (! color[adj[temp]]) //如果与当前结点的结点还未染色
        {
            color[adj[temp]] = 3 - color[i]; //进行染色
            dfs(adj[temp]); //DFS
        }
        if (color[adj[temp]] == color[i]) return false;
            //如果两个相邻结点染色相同,说明此图不是二分图,返回无解
        temp = next[temp];
    }
    return true;
}
 
int main()
{
    freopen("twostack.in", "r", stdin);
    freopen("twostack.out", "w", stdout);
 
    //输入
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
 
    //预处理b数组
    b[n + 1] = inf;
    for (int i = n; i >= 1; -- i) b[i] = min(b[i + 1], a[i]); //"min" in STL
 
    //枚举数对(i,j)并加边
    tot = 0;
    for (int i = 1; i <= n; ++ i)
        for (int j = i + 1; j <= n; ++ j)
            if (b[j + 1] < a[i] && a[i] < a[j])
            {
                addEdge(i, j);
                addEdge(j, i);
            }
 
    //DFS染色
    memset(color, 0, sizeof(color));
    result = true;
    for (int i = 1; i <= n; ++ i) //每次找当前未染色的编号最小的结点,并染颜色1
        if (! color[i]) //当前位置尚未被染色
        {
            color[i] = 1;
            if (! dfs(i)) //染色时出现矛盾,此时图不是一个二分图,即无法分配到两个栈中
            {
                result = false; //记录无解
                break;
            }
        }
 
    if (! result) //无解
        printf("0");
    else //有解
    {
        //模拟求解
        now = 1;
        for (int i = 1; i <= n; ++ i)
        {
            //将当前数字压入对应的栈
            if (color[i] == 1)
                printf("a ");
            else
                printf("c ");
            stack[color[i]][0] ++;
            stack[color[i]][stack[color[i]][0]] = a[i]; //this will work even if stack[1][0] = 0
 
            //循环检查,如果可以的话就从栈顶弹出元素
            while (stack[1][stack[1][0]] == now || stack[2][stack[2][0]] == now)
            {
                if (stack[1][stack[1][0]] == now)
                {
                    printf("b ");
                    stack[1][0] --;
                }
                else if (stack[2][stack[2][0]] == now)
                {
                    printf("d ");
                    stack[2][0] --;
                }
                now ++;
            }
        }
    }
}

一眨眼都到NOIP 2008了,自己都成前辈了啊.

这次没参赛,明天会到场bless各位的,特别是zmc同学和wr同学~szy和zch就算了吧,你们俩都有1=了...
还有raulliubo,吴豪等人,因为路途遥远无法到场(^_^),在此先bless了~dog你还年轻,先等等咯.

明天要搞题,争取至少搞定三道题吧...
有种很强烈的感觉,这次就一道DP.

另外借鱼牛的一句话,"祝各NOIP选手考出真实的好成绩".
相信不会再看到作弊事件的.净化OI,人人有责...

明天还要早起赶过去,不多说咯.
估计明年的这个时候我就不会写NOIP2009祝福文了吧...

Fighting~

好久没写SRM的文章了(上一次还是这里的SRM 422吧...),这次写主要是因为终于重新变黄了.
数一数,都蓝了快10场了呢.

上一场没参加,但这场开始的时候rp也没有爆发.
不知道怎么,12点开始的比赛,闹钟竟然也设在了12点.匆匆忙忙爬起来,都没来及洗脸就坐下开始看题.结果一刻钟都没看懂题,orz.
然后擦了一把脸接着看,终于看懂了.按照惯例,第一题应该是裸search的,但是自己分析复杂度竟然太高.只好求助于FancyMouse牛(后面那道500pts也求助于FancyMouse牛了),后来得知原先4^n的复杂度实际应该是3^n,然后后来又优化了几次,终于在比赛还有半个多小时的时候搞定250pts,这时这道题还剩下120多pts了.

第二题先和FM牛叙述了题意,然后自己感觉还是裸search.于是问FM牛,和我的想法一样.还有半小时,本来不想写了,但是在FM牛的鼓励下还是写了.最后在比赛还有2min结束的时候搞定500pts,200多分.

1000pts看了就知道不是能做的题,最后的确是这样.只有Petr和另一位大牛两人搞定1000pts,剩下的都挂掉了.
最后rating涨的也不是很多,要是250pts快点搞定就说不定会涨很多了.

另外祝贺一下RoBa神牛又一次变红.

附一段聊天记录(有删减):

Killa.sqybi 0:40:07
还有半小时...我估计自己写不完500..
Fancy Mouse 0:40:20
MA。。。impossible is nothing
Fancy Mouse 0:40:49
自从上次regional最后15分钟切掉2题以后偶十分信奉这句话
Fancy Mouse 0:41:15
虽然其中一道是别的队2hr以内就切掉的水题
Fancy Mouse 0:41:23
偶们不知怎么就是不会做
Killa.sqybi 0:41:49
呃...
Fancy Mouse 0:41:55
偶在前面那道搜索切掉以后还剩下10分钟的时候豁出去写了个暴力居然过掉了

再次感谢FM牛...

本来想起个"光棍节快乐"之类的题目的,想来想去还是11.11比较震撼.

首先默哀一分钟--今天是一战停战日.
默哀毕,切入正题(这篇文章会有正题吗-_-||).

这种日子里,coding貌似成了一种煞风景的事情了.既然如此,那就先煞煞吧,最后再煞未免太不道德了.
连续两场比赛没能完成,真的很囧.

首先是上次SRM,让我给忘记了.但要是如此还好了,更囧的是我偶然发现因为夏令时的原因,比赛的registion还没结束.最囧的事,匆匆忙忙去reg,但是TC客户端死活登陆不了,直到比赛结束我也没能登陆上去.
...
然后第二天,TC客户端恢复正常了.

第二件事,USACO月赛,NOV08.本来以为自己已经错过了,今晚又是偶然发现比赛还没结束.于是急急忙忙开题,花了20分钟写了第一题,submit,然后写第三题的线段树.等比赛进行了1个多小时的时候,准备submit,系统告诉我月赛已经结束...然后我就发现上面还在走的倒计时好讽刺啊...为啥比赛偏偏这时候结束...orz...

还有自己的功力下降不少...一个线段树竟然写了一小时...

好吧,就煞到这里.
然后先转matrix67牛的一个笑话调节一下气氛(atmosphere?).
(要看原文,点击这里,注意原文有隐藏文字^_^)

初中的时候，有一天，老师问：你们最喜欢的数字是什么呀？
一个同学说，我最喜欢的数字是1，因为1是第一的意思，我妈妈告诉我我要永远争第一。
第二个同学说，我最喜欢的数字是11，因为我喜欢足球，足球需要全队11个人齐心协力。我希望我能够从足球中学会团队合作。
第三个同学说，我最喜欢的数字是111，因为我喜欢指环王，我要像比尔博·巴金斯那样生活，在人生的111年里勇于探索，敢于挑战。
然后呢，偏偏就轮到我了……
我说，对不起，我有事先走了。

然后呢,今天听说某人和某人分手了.
不想多安慰他们什么,只是默默祝福所有人都能幸福吧.
不过提醒其他的因为某些原因不能过节的朋友们:这个节不放假,不要为了过节分手啊...

不知道为啥突然想起听梁静茹的歌,事实证明今天听梁静茹的歌是多么大的错误...特别是听到分手快乐...还有别人的天长地久啊,燕尾蝶啊...唉...

刚刚被打断太长时间了...这篇文章注定没有结尾吧.
那就这样吧,挺好的.

update:忘记了trackback,现在补上...

很抱歉这么晚才放出来,翻译早就做好了,但是根本就都忘掉了.
很无奈地放一个more标签,想看的自己点开,因为比较长,放在主页上比较难看...
今天SRM竟然被我忘了,现在登陆又不知道为啥登不进去,本来以为SRM还能更新一篇文章的,看起来没戏了...

Read more...