查看: 930|回復: 1

[CodeChef] LTIME21

[複製鏈接]
  • TA的每日心情
    慵懶
    2015-4-10 14:18
  • 簽到天數: 78 天

    [LV.6]常住居民II

    176

    主題

    612

    帖子

    3959

    積分

    管理員

    Rank: 9Rank: 9Rank: 9

    積分
    3959

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

    發表於 2015-2-23 19:09:45 | 顯示全部樓層 |閱讀模式

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

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

    x
    http://www.codechef.com/LTIME21/
    NameSuccessful SubmissionAccuracy
    Lucky Four134982.46
    The Warehouse 10721.54
    Heavy-light Decompositions259.28
    The First Cube 241.33
    052.PNG

    看到FB動態有人PO出了first ac才發現到這比賽XD,來湊一腳。寫到一半Forum就爆炸了跑去修理ORZ。這次題目Heavy-light Decompositions沒中文一開始也沒什麼人動所以跳過,結果最後AC數超過Cube... 晚點來研究
    Lucky Four
    放水無腦過... (看Code就知道為何了)


    The Warehouse
    最後的可能只有RGB的全排列共3!種組合,在此採取枚舉所有組合最佳解。題目所述的三個移動規則可以簡化成:與相鄰交換就得花費1代價。不難發現當RGB順序大小給定時,最小花費代價就是逆述對個數。反正數字只有三種,就不用做什麼BIT,直接暴力加一加就好了。

    The First Cube
    對於單一一個數字,如果存在 X^3 的因子,那X<10^6,如果存在 X^2,那可以找到 Y*X^2 ,使Y或X小於10^6。
    建一張10^6的質數表就可以判斷出是否有2次方以上因子。多變數狀況下,做gcd就可以找出兩數公共因子,處理重複的因數。
    (轉述linnil1)

    Heavy-light Decompositions
    ??

    回復

    使用道具 檢舉

  • TA的每日心情
    開心
    2015-4-12 10:09
  • 簽到天數: 137 天

    [LV.7]常住居民III

    142

    主題

    686

    帖子

    3559

    積分

    邁向天堂

    蘇多門

    Rank: 8Rank: 8

    積分
    3559

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

    發表於 2015-2-28 12:10:26 | 顯示全部樓層
    本帖最後由 domen111 於 2015-2-28 12:11 編輯

    Heavy-light Decompositions AC code:
    http://www.codechef.com/viewsolution/6361466
    英文的官方詳解: http://discuss.codechef.com/questions/64883/hldots-editorial


    題意:
    求有幾種樹練剖分方法數,一個合法的樹練剖分定義為從根節點到任意節點所經過的輕邊不得超過log2(N),N為節點總數。


    比賽時本來以為這題是應該照樹練剖分的方法去做,後來發覺就算不是依照樹練剖分的方法(重邊連到重兒子)也可能符合題目要求(log2)的性質。

    這題其實DP一下就行了
    dp[i ][j], i:節點編號, j:連到此節點前的輕邊數量, dp[i ][j]=方法數
    轉移時枚舉連接子節點的邊作為重邊,乘一乘計算方法數在加起來就行了
    計算連乘的時候不要太暴力直接乘,否則複雜度變成O(C[sup]2[/sup])(C為子節點數)就只能解出小測資,記得先預處理一下,轉移複雜度為O(C)、總複雜度為O(NlgN)就能完全AC。
    蘇多門 domen111
    My Web: https://sites.google.com/site/domenprg/
    回復 支持 反對

    使用道具 檢舉

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

    本版積分規則

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