GCA

這題很明顯就是打表題，不過發現在 git 上面有很漂亮的剪枝 只要前三個乘起來小於1的話代表可以直接continue了 為什麼呢? 因為d*1.0=d d*(0.???)<d 既然乘起來都小於d了 那麼a+b+c還要加上d 絕對會小於d 所以可以屏除掉 // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCC

求所有線段中，最靠近m點且再線段上面的座標是多少 模板題，參考 git 資料 // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::A A:::::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A

枚舉就可以了，記得機率有可能是0 // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::A A:::::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A A:::::A //

一開始以為是水題結果沒這麼簡單 <a> <a> <d> <d> <f> <f> <a> <b> <c> <c> <e> <e> <g> q 上面測資的答案為 q q q q q q q 需要構圖，再用disjoint Set有連接的縮起來成為一個父節點 記得判斷相衝的狀況 // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C::::

Bell Number 新學的一個東西，也是類似卡特蘭數能解特定的問題 // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::A A:::::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A

直接全暴力搜索+記憶化表單 數據感覺好像很小，過得很快 // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::A A:::::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A A:

BFS AC // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::A A:::::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A A:::::A // GGG::::::

一開始以為degree是度…結果是距離 用floyd就水過了 // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::A A:::::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A

只要超過w+l的話代表兩邊繩子繞過去會重覆到 所以把兩邊多出來的繩子做一個三角形，算出面積再加上兩個扇形的面積即可 // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::A A:::::A // GG:::::::::::::::G CC::::::::::::

這題非常的複雜+麻煩，需要用到BFS+Hamilton Path+DP // // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::A A:::::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A