Beyond the Void

三、初窺門徑

雖然從初中就開始學習OI，但我一直以來不知道自己要參加的比賽到底是什麼，直到初三暑假我有幸來到了鄭州參加河南省計算機學會辦的培訓班。雖然只有短短十天，卻讓我的認識有了翻天覆地的改變。第一天的課上，老師就從頭到尾介紹了一下信息學競賽，我的大腦中一下子充斥了NOIP、NOI、WC、IOI等概念，才發現我僅僅參加過的NOIP普及組，連初窺門徑都算不上。幾天以來還認識了不少同學，水平都遠超過我。從前在七中的時候，我有一種登峰造極的幻覺，因爲沒有人能與我的水平匹敵，可是來到這個培訓班卻發現，原來僅僅在河南省就有這麼多比我強的人。十天之內老師講的東西超出了我大腦能夠承受的全部，我深深地感受到了自己的渺小，原來前方的道路還那麼漫長。

高中的第一節信息學競賽課是在開學的一週之後的星期一晚上，我和其他四人來到逸夫科技樓的機房，見到了我的教練常慶衛老師。爲了測試我們的水平，第一節課上老師就出了幾個題。我做得不怎麼樣，當時眞是深受打擊。後來我才知道其他幾個人做得也不好，不過也許我天生就是這樣靦腆，沒有敢去問。接下來我每星期一、三、五晚上都要來機房參加競賽培訓，大約三個星期左右過後，常老師講的內容就超出了我初中學習的全部。我驚訝地發現我初中學過的內容是這麼少，同時也驚喜地發現我學習的速度要遠遠高於初中的時候。

慢慢我和常老師也熟悉起來，經常講完課後以問問題的名義跟到他的辦公室，和他談起來。談話中，我詳細瞭解到了NOIP、NOI、冬令營、省選、APIO、CTSC等比賽，以及保送的情況。他多次談到兩個得意門生：羅宇龍和趙迎賓，他們一個被保送到上海交大，一個被保送到復旦。原來一些模糊的概念在我的腦中漸漸清晰起來，我開始設計我的高中，希望能像羅宇龍和趙迎賓那樣，但是我又覺得我的水平和他們相差太遠，恐怕願望難以實現。但無論如何，拿到NOIP一等獎獲得保送資格是第一步，儘管常老師告訴我他過去的學生在很少有在高一拿到NOIP一等獎的。

也許是我天生喜歡自命不凡，抑或是隨着野心的膨脹，我覺得應該超前做一點，不能再跟着老師的腳步走，否則就會像「大多數人」一樣了，因此開始自己找題做。在常老師的推介下，我開始嘗試做USACO。USACO是一個美國的面向IOI的訓練系統，上面分有6個Chapter，每個Chapter內有一些題，難度依次遞增，通過一個Chapter內所有的題以後才能開始做下一個Chapter。感謝Rob Kolstad無私地把這個題庫無償奉獻給了全世界。期間我自學了C語言，並且開始在做題時使用C語言，雖然老師和所有同學一直在用Pascal。在做USACO的過程中，我過去零散的知識開始變得有系統，無意間水平已經提升到了另一個高度。

和所有的初學者一樣，第一個把我難倒的知識是「動態規劃」。從前就聽過這個名詞，而且瞭解到「動態規劃」是「運籌學」的一個重要分支，因此更感覺神秘而高不可攀了。常老師第一次講完動態規劃以後，我還是一頭霧水的，費了好大力氣才把例題弄明白，但是看到練習題還是不會。艱難地弄明白幾個題以後，卻發現幾乎是一個體一個方法，無法抽象出一個模式。後來雖然有了一些經驗，但眞正理解動態規劃卻是一年以後的事了。

轉眼間到了2007年11月，我終於來到NOIP提高組比賽。2007年的題算是比較容易的，有個動態規劃的題我也搞出來了。最終我以超過分數線一點拿到了NOIP一等獎。

四、高中課程

與我之前聽到的各種傳聞一樣，高中生活是很累的。日程表被安排得慢慢的：每週上課六天，每天早晨七點二十分開始早讀，中午十二點放學，下午兩點半開始上課，六點放學，七點開始上晚自習，一直上到十點二十。儘管如此，作爲「數學競賽班」，只放假一天的周末還要拿出半天來到學校進行數學競賽培訓。爲了加快講課進度，每週二、週四的晚自習還要用於數學課，這正好與信息學競賽培訓穿插開來，讓我沒有一天晚自習能拿出來寫作業。我只好趁中午別人午休時我還可以到教室趕作業。但是沒過多久，我把我中午寫作業的一點時間也投入到了做USACO上。我只好把政治、歷史、地理課拿來寫數學、物理、化學、語文、英語的作業，這才勉強能做完。轉眼一個月就過去了，月考如期而至，我考了全班第24名，年級一百多名。雖然也不算差，但與我初中的成績差遠了，一時我簡直無法接受。

NOIP前一個月，馬浩突然想我和高翔提議要拿政治、歷史、地理課到機房去做USACO。我很矛盾，想想這下連文科課上都不能寫作業了，該怎麼辦呢？但如果能拿到NOIP一等獎，獲得保送資格，這不是更誘人嗎？但期中考試也快到了，如果再不下功夫的話，將會考得更差。猶豫了許久，終於還是決定政史地課去機房做USACO，儘管有些不捨，因爲我還是比較喜歡這些課程的。這下可好，我終於寫不完作業了，每天到教室裏面，看着同學做完了老師布置的作業，又拿來課外輔導習題，我只好向課代表澹然地說一句「沒寫完」。班主任也曾經找過我，說它可以理解我，但是希望我拿了NOIP一等獎以後專心到文化課的學習中，並希望我能參加數學競賽。我也在思考着，但拿NOIP一等獎談何容易呢？

NOIP的時間正好與期中考試衝突，這讓我感到異常的高興，於是我就藉此申請不參加期中考試了，甚至期中考試之前一週都在機房內做USACO。令我感到有些意外，我竟然拿到了NOIP一等獎，勝利的喜悅差點讓我衝昏了頭腦，但這次與初中時不同，因爲我知道前方的道路還很漫長。拿到NOIP一等獎只是獲得了「保送資格」，不等於「保送」，眞正的保送，還要到高三的時候參加一次「保送生考試」，根據你的成績才能確定去哪所高校。因此說來，文化課的成績還很重要。回到班上以後，我立刻開始惡補文化課，還好除了數學以外耽誤的不多，數學課竟然在這幾天講完了整整「三角函數」一章。接下來好像有幾個星期我都沒有去機房，直到常老師又開始講課。

把问题抽象成图论问题，数学模型是求从S到T的两条不相交的路径，使得路径上点的权值之和最大。

费用流建模，首先拆点，把顶点i拆成i.a和i.b，i.a 与i.b之间连接一条费用为“好心值”，容量为1的有向边，特殊地，左上角和右下角两个节点拆分后点内边容量设为2，因为我们要找两条不相交路径。i右边和下边的节点j，连接一条(i.b,j.a)费用为0，容量为1的有向边。

求最大费用最大流即可，费用流值就是要求的结果。比动态规划运行得快，空间占用少。
Read the rest of this entry »

在冬令营的开幕式上，秘书长杜子德透露了关于各科联赛一等奖保送取消的消息，18日晚上的领队和老师的会议上也讨论了相关的竞赛改革信息。具体的信息要等到三月份教育部的通知了，但是大家已经讨论的沸沸扬扬。我支持取消NOIP保送。

取消NOIP保送，同时会加大NOI的参加人数。真正喜欢OI的人，目标是NOI(或更高)而不是NOIP！而现在NOI每个省份参与人数只有区区数人，这是很不好的。取消NOIP保送后，能使更多的真正热爱OI的人进入NOI。取消NOIP的保送，意味着NOIP获奖面加大，NOIP一等奖可以获得高考20分的加分。学习OI和其他竞赛，有不少人是为了保送，而不是真正的喜欢。取消了保送，这些人将会重新权衡利弊，也许会退出竞赛的学习。

只有取消了NOIP保送，才能使我们更有危机感，不敢丝毫放松文化课的学习。因为除了竞赛保送，只有高考才能通向大学。尽管高考制度多么恶劣，对人才是多么摧残，在中国，起码它还是一个相对公平的选拔制度。相比其他的各类国家的考试，哪个有高考这么严谨？在中国全面实现大学自主招生简直是奢谈，没有独立公正的司法制度作为保证，自主招生何谈公平？为了保送而学习竞赛是可以理解的，毕竟它比高考要是更好的出路。但是竞赛不应该成为一个专门用来躲避高考的工具。竞赛到底也出现了腐败的现象，还不是因为有权势者了解到了这个进入大学更容易的途径吗？但是在司法腐败的基础上，想让竞赛真正的公平起来，是不可能的。

保送或者加分，都应该作为竞赛的附属品，而不是让其光芒掩盖竞赛本身。当然任何改革都会引起部分人的不满，竞赛的改革也是一样的。我相信取消联赛保送对竞赛的发展是有利的，起码会让有权势者退出在各科联赛中的利益角逐。当然，取消保送的确会给我带来切实的利益，我承认这也是我支持的一个原因。

这道题的错误做法很多,但是实际在考场上，大多数人拿到了30分。错误做法却能得满分的也很多,正确的算法是基于二分图的算法。注意，不是二分图匹配！

分析条件，我们把问题抽象为数学模型。设输入序列为S，考虑S[i],S[j]两个元素不能进入同一个栈的条件.注意,这里所说的"S[i],S[j]两个元素不能进入同一个栈",不是说仅仅不能同时在一个栈中,而是自始至终不能进入一个栈,即如果有解,那么S[i],S[j]一定进入过的栈不同.

结论P: S[i],S[j]两个元素不能进入同一个栈 <=> 存在k,满足i<j<k,使得S[k]<S[i]<S[j].
证明略过,请参考sqybi.尝试后可以发现结论P是正确的.

把每个元素按照输入序列中的顺序编号,看作一个图中的每个顶点.这时,我们对所有的(i,j)满足i<j,判断是否满足结论P,即S[i],S[j]两个元素能否进入同一个栈.如果满足P,则在i,j之间连接一条边.

我们对图染色,由于只有两个栈,我们得到的图必须是二分图才能满足条件.由于要求字典序最小,即尽量要进入栈1,我们按编号递增的顺序从每个未染色的顶点开始染色,相邻的顶点染上不同的色,如果发生冲突,则是无解的.否则我们可以得到每个顶点颜色,即应该进入的栈.

接下来就是输出序列了,知道了每个元素的决策,直接模拟了.

在判断数对(i,j)是否满足P时,枚举检查是否存在k的时间复杂度是O(n),则总的时间复杂度是O(n^3),对于n=1000是太大了.这原因在于过多得枚举了k,我们可以用动态规划把枚举k变为O(1)的算法.

设F[i]为Min{S[i],S[i+1],S[i+2]..S[n-1],S[n]},状态转移方程为F[i]=Min{ S[i] , F[i+1] }.边界为F[N+1]=极大的值.

判断数对(i,j)是否满足P,只需判断(S[i]<S[j] 并且 F[j+1]<S[i])即可.时间复杂度为O(n^2).

参考资料:sqybi的题解

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

/* 
 * Problem: NOIP2008 twostack
 * Author: Guo Jiabao
 * Time: 2008.12.9 21:22:52
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
 
using namespace std;
 
const int MAXN=1002;
const int INF=0x7FFFFFFF;
 
class tStack
{
	private:
		int top;
		int S[MAXN];
	public:
		tStack() : top(0) {}
		void ins(int k)
		{
			S[++top]=k;
		}
		int tp()
		{
			return S[top];
		}
		void pop()
		{
			top--;
		}
};
 
int S[MAXN],F[MAXN],bel[MAXN];
bool adjm[MAXN][MAXN];
int N,top1,top2;
tStack T[3];
 
void init()
{
	int i;
	freopen("twostack.in","r",stdin);
	freopen("twostack.out","w",stdout);
	scanf("%d",&N);
	for (i=1;i<=N;i++)
	{
		scanf("%d",&S[i]);
	}
}
 
void noanswer()
{
	printf("0");
	exit(0);
}
 
void color(int i,int c)
{
	bel[i]=c;
	int j;
	for (j=1;j<=N;j++)
	{
		if (adjm[i][j])
		{
			if (bel[j]==c) //conflict : not a bipartite graph
			{
				noanswer();
			}
			if (!bel[j])
			{
				color(j,3-c); // color the opposite color 1<->2
			}
		}
	}
}
 
void dye()
{
	int i,j;
	F[N+1]=INF;
	for (i=N;i>=1;i--)
	{
		F[i]=S[i];
		if (F[i+1]<F[i])
			F[i]=F[i+1];
	}
	for (i=1;i<=N-1;i++)
	{
		for (j=i+1;j<=N;j++)
		{
			if (S[i]<S[j] && F[j+1]<S[i])
			{
				adjm[i][j]=adjm[j][i]=true;
			}
		}
	}
	for (i=1;i<=N;i++)
	{
		if (!bel[i])
		{
			color(i,1);
		}
	}
}
 
void solve()
{
	int i,should=1,s;
	for (i=1;i<=N;i++)
	{
		s=bel[i];
		if (s==1)
		{
			T[1].ins(S[i]);
			printf("a ");
		}
		else
		{
			T[2].ins(S[i]);
			printf("c ");
		}
		while (T[1].tp()==should || T[2].tp()==should)
		{
			if (T[1].tp()==should)
			{
				T[1].pop();
				printf("b");
				if (should!=N)
					printf(" ");
				should++;
			}
			else
			{
				T[2].pop();
				printf("d");
				if (should!=N)
					printf(" ");
				should++;
			}
		}
	}
}
 
int main()
{
	init();
	dye();
	solve();
	return 0;
}

NOIP已经告一段落，结果已经没有悬念。下一步，省选。还记得今年省选失败后，心想还有一年，而现在，留给我的仅仅是剩下的5个月。我的水平到底提高了多少？

我已经没有时间再来浪费，所以我不能犹豫，尽快制定一个切实可行的计划，向着我的目标，NOI2009前进。在未来的几个月内，我要多做难题，强化各种高级数据结构的掌握。

现在，我要着手开始做POI了。