這場因為主辦方出包所以不算分
七題裡面我寫了 ABD 三題
放棄 C 改去寫 D 寫完沒多久就發現公告不算分了
E 想了一下沒想出來覺得麻煩就跑去洗澡了
https://codeforces.com/contest/1780
A. Hayato and School
加起來是奇數有兩種可能
奇奇奇或偶偶奇
B. GCD Partition
只需要考慮 k = 2 的情況
假如 k >= 3 是最佳解，也就是
m := gcd(b_1, b_2, ..., b_k)
有最大值，則考慮
m' := gcd(b1, b_2 + ... + b_k)
因為 b_2 + ... + b_k 還是會被 m 整除
所以 m' >= m，因此只需要考慮 k = 2 的情況
O(n) 從左到右找分割點即可
C. Bon appetit!
這題還是卡了我一陣子的
主要是我反覆檢查我題敘到底有沒有看錯
不然那個 NP-complete 感都要穿出螢幕了
就只差現場造個 reduction 出來
有快五千人寫出來(假解)讓人很疑惑
D. Bit Guessing Game
這題很有趣，是 interactive 問題
有另一支程式和你的程式互動
也就是你拿到的輸入會受到你之前的輸出影響
題目是猜數字，會告訴你以二進制表示時有幾個 1
你可以選擇減去某個數字，減完之後還是回答你有幾個 1
不過如果扣到負的會直接輸
N <= 10^9 配上必須在 30 次以內猜出來
感覺就在暗示一次要能找出一個 bit
方法是減去 1 可以讓最右端的 1 變成若干 1
像 101000 - 1 = 100111
根據數量差距就能知道最右邊的 1 在什麼位置
只要記得每一輪要把上輪造出的 1 也一起扣掉就好