PolarisChiba的code收藏區

題目： https://codeforces.com/problemset/problem/830/A MySol： https://codeforces.com/contest/830/submission/51925156 很明顯的，我根本沒腦袋。 很明顯的，會被撿到的鑰匙序列會是連續的 如果不是，那就把最旁邊的鑰匙改成中間斷掉的那支鑰匙肯定會變好 為甚麼呢？ 考慮在被選到的序列中，沒被選到的鑰匙所在的位置 假設它在終點左邊，然後它更左邊還有鑰匙的話，那就把那支換成這支肯定更好 畢竟更靠近終點不虧嘛 那就只剩下它更左邊沒咚咚了，可是聰明的你一定發現了這根本不是個 case 就這樣，對 b 做 sliding window 之類的東東 DP 就結束了唷 可惜我還是跑去看解了，嗯嗯，反正我的智商已經不可能再下降了，就隨便啦

題目： https://codeforces.com/problemset/problem/835/D MySol： https://codeforces.com/contest/835/submission/51920899 我是看解智障，不過我不在乎。 這題看完之後肯定會想到是甚麼區間DP之類的東東。 然後我就不太會了，沒多想後就跑去看解了。 一個 k 回文的兩半肯定是 k - 1 回文 一個 k 回文一定是個回文 所以只要 [ l + 1, r - 1 ] 是回文、 s[ l ] == s [ r ] 那就是符合條件的咚咚了 [ l + 1, r - 1 ] 在DP時就會弄好，那現在只剩下答案為多少了 明顯是 dp[ l ][ l、r 的 mid ] + 1 啊 很顯然吧，只可惜我不會思考

題目： https://codeforces.com/contest/983/problem/B MySol： https://codeforces.com/contest/983/submission/51883938 我是智障的一千種理由 其中之一是我根本無法多看題目一眼然後看出性質 看完這題後很明顯可以感覺到如果我能夠O(1)弄出[l, r]的答案的話，那麼隨便弄弄就可以求出所有答案了。 理由是按照長度做DP，就可以維護在[l, r]內的最佳答案了。 然後我的思路就跑到了要如何O(1)呢？我馬上就想到了巴斯卡三角形 每格被算到的次數剛好是巴斯卡三角耶，成功把算出區間的複雜度弄到O(N)了，因為可以O(N^2)預處理楊輝三角形 然後就不會了QQ 看解之後馬上就察覺到了，[l, r]的答案 = [l, r - 1]^[l + 1, r]的答案，我根本智障 上面那個式子看起來很顯然，對吧？ 嗯...，我也是這麼覺得的，那麼，一開始沒看出來的我是智障這件事就沒有爭議了，對吧？

題目： https://codeforces.com/contest/981/problem/D MySol： https://codeforces.com/contest/981/submission/51882872 我是智障 OK，這樣上面那句就可以在還沒點進去就看到了 這題有個大性質，那就是AND，這可跟甚麼XOR、OR不同，可是AND喔>< 雖然有點違和感，但我一開始就當作一般的東東隨便去DP看看，結果卻連範測都過不了 問題在哪呢？ 亂做的話它的子問題不能推到大問題，當然，如果你已經AC的話就另當別論了 那要怎樣才能有子問題的最優甚麼的性質呢？你應該要想到AND，像我就沒想到就去看解了 如果你有一塊的加起來的長相是mask，那你最終答案肯定小於mask 如果你有一次得到的結果是(1 << 60)，你就算是(1 << 59) - 1這麼多的1你也不care。 所以就會想到要從高位開始往下做DP 應該說看到是位元運算的題目就要想到對位元做事了，但我腦袋只閃過了一下下，就拋之腦後了QQ

題目： https://codeforces.com/problemset/problem/863/D MySol： https://codeforces.com/contest/863/submission/51850623 再不寫treap、再不寫資料結構、再不寫code啊，我。

題目： https://codeforces.com/problemset/problem/893/D MySol： https://codeforces.com/contest/893/submission/51845222 SAD，沒有做出來 可以知道要做事的時候大概只有要check的時候嘛 其他時候就只有判會不會超過而已 然後為了要使得要存錢的時候最少 我每次必須存錢的時候都要想辦法存最多的錢，並且使得以後不會爆掉 所以我要掃一遍，我現在到之後可能會變到的最大值 然後就是某種噁心的取max？ 但我不會寫，所以我就抄了別人的code 得證，我不會寫code。

題目： https://codeforces.com/problemset/problem/388/C MySol： https://codeforces.com/contest/388/submission/51600797 我根本就是個智障，又來了 看錯範測，然後就擅自去猜題目的意思，然後生了一個錯誤到令人發笑的code，而且還過到了第十筆測資== 這時候我又猜題目可能是要另外一個性質，所以就去看解，然後就發現我是全人類最大的智障了 這題是要最大化自己的所得，然後一人從頭拿、一人從尾拿 然後如果有一顆大腦的話，就會想到可以保護自己的這一半邊 假設你這一半有個巨大利益的東東，然後對方試圖拿這一堆，那你就也拿這一堆就可以保護這自己那一個了 不過問題就是如果是奇數的話中間那堆怎麼辦 然後你就會發現這根本不是個問題，sort之後相間著拿就OK了 我沒救了

題目： https://codeforces.com/contest/528/problem/B MySol： https://codeforces.com/contest/527/submission/51564334 我根本是個智障 看到題目後第一個想法是找一些規律，然後我還真的找到了 如果(i, j)滿足且(j, k)滿足並且 i < j < k，那麼(i, k)也滿足條件，這件事情是顯然 所以我就開始朝這邊開始想，我要怎麼快速找到一個連續序列，使的這序列相鄰兩兩都滿足呢？ 我就開始亂想一通 假設xi < xj，把那個不等式拆開，變成：xj - xi >= wi + wj，移項得到：xj - wj >= xi + wi，所以 i 這個點往後連到的點 j 可以用一些資料結構亂維護，所以我就可以好好dfs了 歡樂大結局...才怪，邊數多到銀河的星星數不完，可悲 最後看解之後才發現我根本是個智障 觀察一下那個不等式，根本就是兩個點之間距離不能超過兩個點所具有的某個長度嘛 這不就是最多有多少區間互相之間無overlap啊@@ 可悲，經典greedy題可是根本看不出來，人生失敗

題目： https://codeforces.com/contest/375/problem/B MySol： https://codeforces.com/contest/375/submission/51562040 這題時限莫名其妙的緊>< 然後arrange the rows是指列的order可以重新arrange 看到這題應該要先想到如果不交換的話要怎麼做 然後我的腦袋永遠就只有O(WH*W)的東東，可悲 然後後來才看了O(WH)的解，而且我查到的咚咚的code還爛了 實際上以目前最高能到哪裡，並且就往左右都看看可以跑多遠 然後就會發現往左右最遠到哪這件事很重要 因為列之間可以交換，所以就會想到從上面往下面做，然後以往左的距離為鍵值sort 最後從上而下做就OK了之類的 結論，我的大腦燒焦、可悲