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的兄弟努力?。。?/a>	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做記憶化搜索.