查看: 325|回復: 2

[競賽分享] [成大賽2015]野生題解_1(A~C)

[複製鏈接]
  • TA的每日心情
    鬱悶
    2015-5-15 22:38
  • 簽到天數: 33 天

    [LV.5]常住居民I

    75

    主題

    302

    帖子

    766

    積分

    版主

    TFcis - 105 附設監工官

    Rank: 7Rank: 7Rank: 7

    積分
    766

    台南一中資訊社程式設計達人 - 2014

    發表於 2015-7-8 18:56:10 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    x


    如有錯誤歡迎指教~

    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解答

    點評

    jd3
    說真的就算懂了沒AC也沒把握做題解XD  發表於 2015-7-10 00:03
    G太難了,應該是防破台,有誰能解答嗎?  發表於 2015-7-8 21:22
    <這是個人簽名欄位>
    回復

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表