Codeforces1379-題解

很久以前，申蛤申請了一個cf號叫 wzxakioi

有一天，戌蛤帶著申蛤用這個帳號打了一場div3，然後它的rating超過了shzr

之後申蛤又用這個號打了三場div2,於是

CF1379C

題意：有一些禮物，當你第一次買第i個的時候會獲得$a_i$的快樂值，之後每個會獲得$b_i$的快樂值，問買n個最大快樂值$n\leq 1e9$

可以看出來的是如果已經確定了會買禮物的集合的話除了b最大的那個其餘每種都只會買一個

枚舉會買到b的那種禮物，如果其他禮物的a比這個b大就一定會買

所以把所有a和b都拿出來拍個序按順序買

這道題除了題目很長沒什麼意思= =

題意：有一個車站，在一些時刻有貨車需要離站。現在要每半小時發一輛客車，發客車前需要k min的時間使乘客上車，乘客上車時貨車不能發車。問最少取消多少貨車。

對於每個貨車可以輕鬆求出在哪段時間發客車會使他無法正常運行，把這些都差分下來排個序，找到前綴和最小的位置就是答案。

考試時寫到這裡就只剩20min了，所以後面目前都是口胡

題意：找到一個n個點的二叉樹，有m個點它的兩個子樹大小一個是另一個的兩倍。

看起來可以找找規律，比如貢獻最大的是毛毛蟲，比如只有$2^k-1$這樣的可以做到子樹沒有答案貢獻，但是這樣好像不能有1個貢獻。其餘情況可以做到一個貢獻？

驗證可行性以後dfs建樹？

題意：有一個$2n\times 2m$的棋盤。對於$x+y$是偶數的位置可以放棋子。有一些位置可能會不能放棋子或恢復。問每次操作後能不能放nm個棋子。

把2*2的棋盤當成一格，一格內顯然只能放一個棋子。所以需要每格內都能放一個棋子。

出現這種情況肯定就沒解了，然後這種好像還有傳遞性，也就是說甚至都沒有解

F1沒有恢復操作可以直接二分check

F2就線段樹分治嘛！但是題解好像是一個log的，等會兒再學習一下