oyjpArt ACM/ICPC算法程序设计空间

上个礼拜6参加了湖大的邀请赛,一直没有时间写总结,终于空闲,来描画下.
分组:
ALPC T1: alpc117, alpc02, alpc12(me) (比赛中使用robust队名)
ALPC T2: alpc10, alpc25, alpc62 (比赛中使用alpc62队名)
ALPC T3: alpc05, alpc55, alpc16(比赛中使用icpc队名)
ALPC T4: alpc33, alpc07, alpc60 (比赛中使用alpcteam4队名)
 
成绩:(2题以上)

Realtime Ranklist of 2007 Warm Up 10
Start Time : 2007-9-15 10:30:00 End Time: 2007-9-15 15:30:00
Contest/Course Status : Ended
Rank	User ID	User Name	Solves	Penalty
1	robust	alpcT1	7	1175
2	icpc	nudtIII	6	797
3	footmen	Team Footmen	6	1244
4	backbone	Ecust_Backbone刷死我了~	5	509
5	Three_up	Ljy	5	1044
6	alpc62	alpc T2	4	736
7	cyc	if you can,you can	4	793
8	TCT	k5的兄弟努力啊！！	4	824
9	zealor		4	836
10	ft2	ft	4	838
11	ACM06060	辜斯缪	4	861
12	alpcteam4	alpcT4	4	929
13	Hunter	Hunter	3	411
14	csmathboy	修学储能	3	436
15	bluesea	Ecust_bluesea	3	562
16	reyes	Ecust_ReYes	2	115
17	KYAO	目标是挤进前十	2	127
18	allencxz	My dream!!!	2	206
19	clover	clover	2	262
20	jjllqq	ECUST_CodeSeekers	2	374
21	crz1987	crz	2	397
22	MultiThread	Jun Wang	2	407
23	madongfly	I Love Fly	2	468

题目答题情况如下：

2007 Warm Up 10
Start Time : 2007-9-15 10:30:00 , End Time : 2007-9-15 15:30:00
Total Time Length : 5 : 00 : 00, Status : Ended
Solved	Problem	AC/Submit	Title	Release Time
	A	1/4	Cheesy Chess	2007-9-14 13:11:17
	B	29/30	Frobenius	2007-9-14 13:11:25
	C	0/0	Mineshaft	2007-9-14 13:18:26
	D	59/61	Colour sequence	2007-9-14 13:24:18
	E	19/20	Projects	2007-9-14 13:28:01
	F	1/4	Booksort	2007-9-14 13:28:06
	G	24/59	Oulipo	2007-9-14 13:28:11
	H	32/45	Lucky Light	2007-9-14 13:28:17
	I	7/14	Sightseeing	2007-9-14 13:28:35
Ranklisk    Status    Clarifications

题目:

A题Cheesy Chess : 模拟题.按说深搜广搜都能过,我在最后30分钟敲的,没AC,主要原因是题意在敲之前没有理解透彻.

B题Frobenius :类似于质数筛法的思想(也可以理解成背包)把Frobenius数找出来.题目问有没有可能有超过1,000,000的Frobenius数, 其实仔细想想都可以知道 只要1,000,000之后加上10,000没有出现Frobenius数,后面就不可能出现.alpc117A掉的.

C题Mineshaft :题意很难理解,处于决策考虑,我们组最后放弃了这题.

D题Colour sequence 简单的DP,我A了.

E题Projects 还是一个DP, dp[i][j]代表前面i个工程由j个人来完成,在这个基础上作DP应该不难.注意计算概率的方式,还有这个题目可以直接用整数计算,就没有精度误差了.我敲的.

F题Booksort : 搜索+剪枝.看到题目基本上就可以明确是搜索题,而且也很好用迭代深搜来写.于是问题归结于如何剪枝.我想到了一种关于跳跃点的剪枝: 若连续的两个数不满足严格升序关系,则成为一个跳跃点(第1个数不是1或者最后一个数不是N也是跳跃点). 这样一次SHIFT操作最多只能减少3个跳跃点,也就是说2次最多减少6个,依此类推.直观的想,这个剪枝的效果应该是会比较明显的.ALPC02敲了这题,15MS宽裕的过了.

G题Oulipo : 典型的KMP,alpc117大敲一顿过了.

H题Lucky Light : 这道题我没有过问,这是我们上场敲的第一题,ALPC02 A了它,不过罚时较多.好在AC之后我们队越来越顺

I题Sightseeing : 首先是求最短路,然后分别对最短路和最短路+1做记忆化搜索.