Posted on 2007-09-19 22:44
oyjpart 閱讀(1696)
評(píng)論(6) 編輯 收藏 引用 所屬分類:
ACM/ICPC或其他比賽
上個(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題以上)
題目答題情況如下：
題目:
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做記憶化搜索.