TA的每日心情 | 慵懶 2015-4-10 14:18 |
---|
簽到天數: 78 天 [LV.6]常住居民II
管理員
- 積分
- 3959
|
趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
x
HSPC比完了,應該來懺悔一下只有拿第二!? 明明有看過題目(又抄題...),但卻放掉兩題,兩題都是flow,一題是我高一全國賽的最後一題,是KM algoithm的原始模型題... 不過當時只有國手一人寫出來... ,另一題股票走勢也是全國賽題目,不過我把模型建錯,變成用加的加到答案,然後就一片混亂,結果原來是用總額扣回去,真是悲劇,另一個未解出的也很可惜,一直想要怎樣搬座標,沒想到用向量直接乘一乘就好了,水題未解出超慘,原本想說時間還滿微妙,下面給下個人隨興題解吧:
A.睡吧喬治
BASIC
http://ideone.com/VH3esg
兩時間相減,我直接小時/分鐘直接減,隨便處裡一下進位就拿到傳說中的SID:1 Yes. 本人第二次,上一次是去年NPSC出賽被我亂翻到gcd瞬殺得到的,超開心。
B.神奇寶貝大師之路 - 迷幻森林
BFS
http://ideone.com/Kq9Fkm
這一題是李弘毅想出來的,我在爆pG時哪幫我弄出來讓我可以接著coding,基本上可以想像所有的訓練師都執著地要在終點對戰,那可以證明只有該訓練師與終點之最短路小於等於主角時才能對戰。多起點最短路如果笨笨的從每個起點開始搜應該是會TLE的,不如從終點一網打盡的乾脆。
C.四面體
DP
Code遺失~ 不過超水
有人在四面體的邊上走路,問跨過N條邊回到原點的方法有幾種。簡單DP亂加一通再建表O(1)輸出就好了。
EXIN 2 4
EXOUT 3 21
D.公車司機問題
Gready
http://ideone.com/WAbAzH
經典問題,盡可能的填滿即可達最佳解,就把最大加最小,以此類推即可。
E.股票走勢圖
Flow
none
GCJ 2009 R2 C Stock Charts
https://code.google.com/codejam/contest/204113/dashboard#s=p2
這題把模型建成NP問題,然後就悲劇了,由原題另一觀點構造其實這題很簡單。
F.機器人
模擬+數學
none
先模擬走一次,再用向量平移求整數解,沒解出也很悲劇
G.城市馬拉松
Shortest Path + 位元DP
http://ideone.com/9mfQE5
http://zerojudge.tw/ShowProblem?problemid=a416
原題的奇數點有20個,成大只有16個,不過其他方面相同,說這題防破台,也太常見此題了!
中國郵差問題,本題起終點不同,要補成歐拉環的基本概念就是加一條起點到終點的雙向邊,為不影響答案,權重設為極大數值。找出奇數點有哪些後,做最短路求出全奇點對間最短路徑長,個人用SPFA,然後再求奇數點的最小權匹配,一般圖的最小權匹配是NP,在此用位元DP,複雜度O(2^N),可在時間限制內完成,就把這題給爆開了。
H.(給老師了XD 同2012全國賽最後一題)
Flow
擺了兩年還是不會KM...... |
|