oyjpArt ACM/ICPC算法程序設(shè)計(jì)空間

上個(gè)禮拜6參加了湖大的邀請(qǐng)賽,一直沒有時(shí)間寫總結(jié),終于空閑,來描畫下.
分組:
ALPC T1: alpc117, alpc02, alpc12(me) (比賽中使用robust隊(duì)名)
ALPC T2: alpc10, alpc25, alpc62 (比賽中使用alpc62隊(duì)名)
ALPC T3: alpc05, alpc55, alpc16(比賽中使用icpc隊(duì)名)
ALPC T4: alpc33, alpc07, alpc60 (比賽中使用alpcteam4隊(duì)名)
 
成績(jī):(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	修學(xué)儲(chǔ)能	3	436
15	bluesea	Ecust_bluesea	3	562
16	reyes	Ecust_ReYes	2	115
17	KYAO	目標(biāo)是擠進(jìn)前十	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 :類似于質(zhì)數(shù)篩法的思想(也可以理解成背包)把Frobenius數(shù)找出來.題目問有沒有可能有超過1,000,000的Frobenius數(shù), 其實(shí)仔細(xì)想想都可以知道 只要1,000,000之后加上10,000沒有出現(xiàn)Frobenius數(shù),后面就不可能出現(xiàn).alpc117A掉的.

C題Mineshaft :題意很難理解,處于決策考慮,我們組最后放棄了這題.

D題Colour sequence 簡(jiǎn)單的DP,我A了.

E題Projects 還是一個(gè)DP, dp[i][j]代表前面i個(gè)工程由j個(gè)人來完成,在這個(gè)基礎(chǔ)上作DP應(yīng)該不難.注意計(jì)算概率的方式,還有這個(gè)題目可以直接用整數(shù)計(jì)算,就沒有精度誤差了.我敲的.

F題Booksort : 搜索+剪枝.看到題目基本上就可以明確是搜索題,而且也很好用迭代深搜來寫.于是問題歸結(jié)于如何剪枝.我想到了一種關(guān)于跳躍點(diǎn)的剪枝: 若連續(xù)的兩個(gè)數(shù)不滿足嚴(yán)格升序關(guān)系,則成為一個(gè)跳躍點(diǎn)(第1個(gè)數(shù)不是1或者最后一個(gè)數(shù)不是N也是跳躍點(diǎn)). 這樣一次SHIFT操作最多只能減少3個(gè)跳躍點(diǎn),也就是說2次最多減少6個(gè),依此類推.直觀的想,這個(gè)剪枝的效果應(yīng)該是會(huì)比較明顯的.ALPC02敲了這題,15MS寬裕的過了.

G題Oulipo : 典型的KMP,alpc117大敲一頓過了.

H題Lucky Light : 這道題我沒有過問,這是我們上場(chǎng)敲的第一題,ALPC02 A了它,不過罰時(shí)較多.好在AC之后我們隊(duì)越來越順

I題Sightseeing : 首先是求最短路,然后分別對(duì)最短路和最短路+1做記憶化搜索.