我的黄金时代

poj 2817 WordStack

先枚举预处理每两个单词之间的最大值。
然后易看出是要寻找一条遍历所有顶点一遍的最长路径，也即找到一条最长的Hamilton Path。(TSP问题)

状态为d[state][last]，代表遍历了state这些点，并且最后一个点为last时，最长的Hamilton Path。
状态方程为：d[state][last] = d[state-(1<<i)][i] + w[i][last] ( (i!=last) && ((1<<i)&state) )

poj 2677 Tour

TSP问题简化版，又称为bitonic tour。（参见算法导论习题15-1）

不妨将问题看作两个人同时从左向右走，并且两个人走过所有的点，且两人走过的点均不同，求两人走过的路径之和最短解。
状态为d[i][j]，代表了第一个人走到点i，第二个人走到点j，并且i>j，且i之前（包括i）的所有点均被走过，最短路径和。
状态方程为：
(1) i==j+1，d[i][j] = d[j][k] + w[k][i] ( 0<=k<j )
(2) i>j+1，d[i][j] = d[i-1][j] + w[i-1][i]

(1) n个有序集合求并
问题定义：设有n个有序数组，arr[i] ( 0<=i<n )，将这n个有序数组归并，得到一个有序数组。

解法[1]：
当n=2时，显然，我们只要线性扫描两个数组即可，复杂度O(size(arr[0]) + size(arr[1]))；
当n>2时，我们可以使用上述方法对有序数组两个两个的进行归并，最终得到一个有序数组。在总的归并过程中，每个元素被操作O(logn)次，因此，总的时间复杂度为O(mlogn)，m = sum(size(arr[i]))， 0<=i<n。

解法[2]：
不妨假设有序数组是按照非降序排序的。归并时，使用最小堆。首先将n个数组中的首元素压入最小堆。每次弹出最小堆中的堆顶元素，相当于得到了n个数组中当前处理位置中最小的元素，然后将弹出元素所在数组中的下一个元素压入最小堆。每个元素在最小堆上均被插入和弹出一次，O(logn)，所以总的时间复杂度为O(mlogn)，m = sum(size(arr[i]))， 0<=i<n。

(2) n个有序集合求交
问题定义：设有n个有序数组，arr[i] ( 0<=i<n )，将这n个有序数组求交，得到一个有序数组。

解法：
对所有数组线性扫描一遍即可。不妨设有序数组是按照非降序排序的。
设min为所有数组当前被扫描位置的最小值，max为最大。若min==max，则将此值加入新数组。若min!=max，则对每个数组从当前位置起扫描，直至找到第一个大于等于min的数，如此循环。
时间复杂度为，O(m)，m = sum(size(arr[i]))， 0<=i<n。

伪码如下：

	for each arr
		pos[i] = -1

	min = max = 0
	end = false
	while end == false
		if min == max
			for each arr
				++pos[i]
				if pos[i] >= size(arr[i])
					end = true
					break
		else if min != max
			min = max
			for each arr
			while arr[i][pos[i]] < min
				++pos[i]
				if pos[i] >= size(arr[i])
					end = true
					break
			if arr[i][pos[i]] > max
				max = arr[i][pos[i]]
		while end == false
			if min == max
			newarr.add(min)
    

2001
Shanghai Site hosted by Shanghai University
Team: xdu1
Player: 黄德祥(计99),周树德(计99),郑颖(软99)
Result: Honorable Mention

2002
Beijing Site hosted by TsingHua University
Team: xdu1
Player: 袁进辉(计99),郑颖(软99),冯博文(计00)
Result: Honorable Mention

Team: xdu2
Player: 高丽强(计00),彭超(计00),贺宇凯(计01)
Result: Honorable Mention

Team: xdu3
Player: 李胜梅(计99),周树德(计99),张彦春(计99)
Result: Honorable Mention

Xian Site hosted by Xi’an JiaoTong University
Team: xdu1
Player: 袁进辉(计99),郑颖(软99),冯博文(计00)
Result: Honorable Mention

Team: xdu2
Player: 高丽强(计00),彭超(计00),贺宇凯(计01)
Result: Honorable Mention

Team: xdu3
Player: 严佩(计00),郝淼(计01),张彦春(计99)
Result: Honorable Mention

2003
Beijing Site hosted by TsingHua University
Team: xdu01
Player: 彭超(计00),严佩(计00),贺于凯(计01)
Result: The Silver Medal (ICPC 5th)

Guangzhou Site hosted by ZhongShan University
Team: xdu01
Player: 彭超(计00),高丽强(计00),魏晓林(计02)
Result: Honorable Mention

2004
Beijing Site hosted by Peking University
Team: xduBoys01
Player: 彭超(计00),贺于凯(计01),汪浩(计03)
Result: Honorable Mention

Team: xduGirls01
Player: 陈力琼(软01),王艳(计02),穆浩英(软03)
Result: Honorable Mention

Shanghai Site hosted by Shanghai Jiao Tong University
Team: ACMore
Player: 魏晓林(计02),谢远江(计02),卢闰明(计03),
Result: Honorable Mention

2005
Chengdu Site hosted by SiChuan University
Team: ACMore
Player: 谢远江(计02),卢闰明(计03),程明明(计03)
Result: Honorable Mention

Beijing Site hosted by Peking University
Team: ACMore
Player: 谢远江(计02),卢闰明(计03),程明明(计03)
Result: The Silver Medal (ICPC 19th)

Hangzhou Site hosted by ZheJiang University
Team: Challenge
Player: 卢闰明(计03),刘璟(计03),穆浩英(软03)
Result: Honorable Mention

2006
Beijing Site hosted by TsingHua University
Team: ACMore
Player: 卢闰明(计03),王洋(软04),段根全(计04)
Result: The Bronze Medal

Team: XDteam2
Player: 李志(计04),宋爱龙(计04),李永庆(计04)
Result: Honorable Mention

Team: HappyBaby
Player: 袁珺(计04),王晓丽(软04),褚艳丽(软04)
Result: Honorable Mention

Shanghai Site hosted by Shanghai University
Team: ACMore
Player: 卢闰明(计03),王洋(软04),段根全(计04)
Result: The Silver Medal (ICPC 10th)

Team: Challenge
Player: 刘璟(计03),李志(计04),陈熙(计05)
Result: The Bronze Medal

Xian Site hosted by XiDian University
We are the Oganizer

The 2006 World Finals
Team: ACMore
Player: 卢闰明(计03),王洋(软04),段根全(计04)
Result: ICPC 44th

2007
Nanjing Site hosted by Nanjing University of Aeronautics and Astronautics
Team: Origin
Player: 陈熙(计05),蔡田齐一(通05),李友(电05)
Result: The Bronze Medal

Team: just kids
Player: 郭阳(计05),谭博侃(计05),仲超(计05)
Result: Honorable Mention

Beijing Site hosted by Beihang University
Team: Lucky dogs
Player: 陈熙(计05),王玉操(计06),廖宇晨(软06)
Result: Honorable Mention

Chengdu Site hosted by Xihua University
Team: just kids
Player: 郭阳(计05),谭博侃(计05),仲超(计05)
Result: Honorable Mention

Team: D-N Capcablity
Player: 刘学美(计05),宋大卫(电06),吴钟琦(计06)
Result: Honorable Mention

Rank Name Solved Time
1 Warsaw University 8 1405
2 Tsinghua University 7 1200
3 St. Petersburg University of IT, Mechanics and Optics 6 866
4 Massachusetts Institute of Technology 6 866
5 Novosibirsk State University 6 868
6 Saratov State University 6 957
7 Twente University 6 1011
8 Shanghai Jiao Tong University 6 1026
9 University of Waterloo 6 1103
10 Moscow State University 6 1192
11 University of Auckland 6 1210
12 California Institute of Technology 6 1241
13 Petrozavodsk State University 6
14 Kyoto University 5
14 National Taiwan University 5
14 Peking University 5
14 Seoul National University 5
14 Sharif University of Technology 5
14 St. Petersburg State University 5
14 Universidad de Buenos Aires 5
14 University of Alberta 5
14 University of British Columbia 5
14 University of Science and Technology of China 5
14 University of Texas at Dallas 5
14 University of Toronto 5
26 Amirkabir University of Technology 4
26 Belarusian State University 4
26 Fudan University 4
26 Johannes Kepler Universit?t Linz 4
26 KTH - Royal Institute of Technology 4
26 National Technical University of Ukraine 4
26 Pontifícia Universidade Católica do Rio de Janeiro 4
26 Stanford University 4
26 Stavropol State University 4
26 The University of Tokyo 4
26 Universidade de S?o Paulo 4
26 University of Cape Town 4
26 University of Illinois at Urbana-Champaign 4
26 University of Nebraska - Lincoln 4
26 University of Wroclaw 4
26 Ural State University 4
26 Vologda State Pedagogical University 4
26 Zhongshan (Sun Yat-sen) University 4
44 Bina Nusantara University 3
44 Carnegie Mellon University 3
44 College of Technology, Vietnam National University, Hanoi 3
44 Cornell University 3
44 Duke University 3
44 East China University of Science & Technology 3
44 Hefei University of Technology 3
44 Indian Institute of Technology, Madras 3
44 Korea Advanced Institute of Science and Technology 3
44 National University of Defense Technology 3
44 Orel State Technical University 3
44 Saitama University 3
44 Universidad Centroccidental Lisandro Alvarado 3
44 Universitat Politècnica de Catalunya 3
44 University of Adelaide 3
44 University of Bucharest 3
44 University of Central Florida 3
44 University of New South Wales 3
44 Xiamen University 3
44 Xidian University 3
44 Zhejiang University 3

由衷的恭喜ACMore@XDU (Lrm, duan, elf) ^_^
lrm这三年也算彻底圆满了。
下个赛季的elf, duan, lizhi也能撑起来XDU的ICPC了。
06/07赛季也就这样结束了。
明年如果还有兴趣看得话，也只是一个彻彻底底的看客了。

rank 46th.
纯安慰性的the bronze medal.

前两题还算稳当。
第三题又是我的严重问题，对不起lizhi同学了。
chenxi让我期盼的I没有出现奇迹。
当时确实太想赢了。
心态。心态。

lrm打得很出色，rank 15th，这里也祝贺他了。可惜最后一次没有机会跟他合作。
但也让我又认识到了一些问题，也有了一些新的变化。

颁奖XX讲话时，随便问了下lizhi明年还打么，他笑了笑说算了，还有别的事情做。

2004.07~2006.11
hangzhou 2005 rank49th honorable mention
shanghai  2006 rank46th the bronze medal

就这么退役了。
匆匆过客，其实，连影子都留不下。