[閒聊] CodeChef Starters 77

看板Marginalman作者fxfxxxfxx (愛麗絲)時間3年前 (2023/02/16 04:22)推噓4(4推 0噓 0→)

留言4則, 4人參與討論串1/1

這次是第二次參加 CodeChef Starters 我覺得還蠻有趣的這次六題裡寫出了五題排在 div2 的第二這場比完就到六星 2302 似乎有些比較簡單比賽的就不能比了 https://i.imgur.com/6nOAwem.png

今天嘗試不用他那個慢的要死的線上IDE 改在本地寫+測試後再複製貼上體驗整個就好很多 P1 CONCATPAL https://www.codechef.com/problems/CONCATPAL 因為可以隨便排順序所以只需要看各個字母的出現次數能成功若且唯若長的和短的抵消後每個字母出現次數 >= 0 且出現次數是奇數的字母數 <= 1 （可以當中心點） P2 THREENUMBERS https://www.codechef.com/problems/THREENUMBERS 目標是要讓三個數都一樣把兩個數加一且另一數減一其實就等價於把一個數減二答案就是與最小值的距離總和除二 P3 KPAL https://www.codechef.com/problems/KPAL 這題是 corner cases 題，分成 1. N = K (直接看 A 是不是回文) 2. N 是奇數 (一定成功) 3. N 是偶數，K 是奇數（一定成功） 4. N, K 都是偶數（看兩個半邊奇偶性是否一致） P4 SORTXOR https://www.codechef.com/problems/SORTXOR 從這題開始有挑戰一點可以用三次 xor 交換兩個值但如果只用到兩兩交換的話會超出 3N/2 的限制（最多需要 3(N - 1) 次操作）不過經過在紙上一陣亂試會發現對於 permutation 的一個長度是 k 的 cycle 實際上只需要 k + 1 次操作像是 (1 3 4) 這個 cycle 只需要作出 1: [1 3 4] 3: [1 3 4] 4: [1 3 4] 1: [1 3 4] 就可以直接排好位置因為長度是 1 的 cycle 不用做事所以最多就是 3/2 倍，剛好就是他的限制記得把一開始的值轉成 ranking 形式的 permutation 即可 P5 SORTSTR https://www.codechef.com/problems/SORTSTR 這題我蠻喜歡的，因為題目簡潔但最後的結果又出乎我意料對於一個字串，如果相鄰的兩個字元的值也是相鄰的就可以交換例如 aabbd 中的 ab 交界可以互換，但 bd 交界不行要找出能形成的字典序最小的字串假如某個字元是 k 一個很重要的觀察是這個位置不可能 >= k + 2 也不能 <= k - 2 例如想要變成 k - 2，首先必須變成 k - 1 但 (k, k-1) 交換後變成 (k-1, k) 後就又變成需要把後面的 k 變成 k-2 才能讓前面的 k-1 變小所以不可能達成要字典序最小，可以 greedy 的讓第一個最小假如第一個字元是 k 根據剛才的觀察，我們只有機會讓他變 k-1 所以只有不斷的進 k 或是 k-2 才有機會一路交換上來變成 k-1 維護一個 queue 就會變成像下面這樣只由 k 及 k-2 組成 --------------- queue --------------> k k k (k-2) (k-2) (k-2) 這時如果進來 k-1，則可以一路交換到最前面所以我把他稱作「隧道」考慮完 k, k-1, k-2 的情形後來討論進其他值的情況 1. > k，則不管是 k 還是 k-2 都不可能再更小了，可以把整個 queue pop 掉 2. < k-4，則同樣不管是 k 或 k-2 都不可能更小 3. k-3 或 k-4，則所有的 k 都失敗，但 queue 結尾的連續 k-2 還保有機會所以還要紀錄 queue 裡 k 的個數來讓我們知道 queue 裡是不是只剩 k-2 P6 KFOREST https://www.codechef.com/problems/KFOREST 這題我沒在比賽時寫出來，不過我方向大致正確就是了QQ 我有發現可以一個 bit 一個 bit 測試有想到能分成 K 塊等價於能分成 K + 2i 塊但我沒寫過把樹分成好幾塊的題目我一直想從 leaf 開始往內縮應該也會是對的但寫起來很複雜看解答才知道其實用 dfs 就可以解了這次的題目我還蠻喜歡的 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1676492567.A.BCA.html

推

Ericz7000

02/16 04:25, 3年前 , 1^F

02/16 04:25, 1^F

推

pandix

02/16 04:44, 3年前 , 2^F

02/16 04:44, 2^F

推

Mustafar

02/16 10:59, 3年前 , 3^F

02/16 10:59, 3^F