竹園論壇

標題: [成大賽2015]野生題解_1(A~C) [打印本頁]

作者: jd3 時間: 2015-7-8 18:56
標題: [成大賽2015]野生題解_1(A~C)

如有錯誤歡迎指教~

A.
字串應該不用多說了
有0.1, 0.2, 0.3, 0.4四種相乘
0.1 = 1*10^(-1)
0.2 = 2*10^(-1)
...依此類推

先把整數部分拿來乘
10^n部分則是有幾個字n就多少

小數點後需要接 (字串長度) - (整數位數) 個 0
再把整數輸出

整數有多少位的計算方式
可以一直 / 10看看什麼時候=0
或
把1一直*10直到超過

B.
看起來很像一般常見的費式數列
小陷阱是他給的N是「整數」
有可能 <0

根據定義往回推
再經過一翻觀察發現F(N), N<0
是一正一負的
且絕對值和N>0的部分恰好相等
像這樣,
-3, 2, -1 ,1 ,0, 1, 1, 2, 3

(當然你也可以用數學算)

因為詢問多次，預先建表 ( f 數列成長很快, 表不大)
遇到負的N判斷奇數或偶數

C.
找1~N最短距離(路徑長)
邊權都是一樣的, 連Dijkstra都不用, 直接BFS
複雜度O(E)
最後判斷有沒有<=麵包數量

答案輸出的文字記得加句點 '.' 就完成了~

DFS在我們的實驗底下無法成功AC
至於原因
應該是要找到最短的複雜度較高
直接傻傻搜到底
最差O(N!)左右

===================
拋磚引玉
求D,G解答

歡迎光臨竹園論壇 (http://forum.tfcis.org/)