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了之類的 結論，我的大腦燒焦、可悲

LINK： http://codeforces.com/problemset/problem/1068/C SOL： http://codeforces.com/contest/1068/submission/45190518 題解是意外的精妙的解法。 總之對於顏色i丟到( i, i )的格子確保至少有一個，然後對於某一對和諧的顏色，都在某一行還沒有rooks的地方塞( i, res ), ( j, res ) 這樣一來就保證了同樣顏色的聯通性了。 話說最近超級無敵頹的QQ

LINK： http://codeforces.com/contest/980/problem/D SOL： http://codeforces.com/contest/980/submission/45034217 CODE越來越毒了@@ 簡而言之就是因為是完美平方數，所以就可以把將所有質因數的次方mod2，之後被分到同一組的就只能是相同的數啦，然後再把0的case判掉就OK了......( 就是這裡出bug後code就變毒了@@ )

LINK： http://codeforces.com/contest/980/problem/C SOL： http://codeforces.com/contest/980/submission/45033349 想不出來，或者我沒想？ 總之要字典序最小，所以就會是某種greedy...吧，然後就greedy下去囉XD

LINK： http://codeforces.com/contest/1065/problem/D SOL： http://codeforces.com/contest/1065/submission/44892468 FST掉的一題。 我原本的寫法是DP，然後每次轉移的時候都BFS一次，然後寫到快瘋掉，賽中就鏘了一百多行，然後就FST了QAQ 之後好長一段時間因為這題感覺很麻煩所以就一直放著，直到後來看了別人的code後才發現原來只是我的寫法很複雜而已@@ 事實上，可以將座標(x, y)、棋子編號為0, 1, 2，將所有狀態寫成( ( x*n + y )*3 + 棋子編號 )，然後就可以建出一張圖，處理只換一次棋子、只走一步的所有可能後，再用floyd warshall做全點對最短距離，接著再好好DP就OK了。 話說floyd warshall那裏應該可以更好的，因為我其實只要求從第 i 格走到第 i+1 格的不同棋子間的最短路徑就好了，所以其實是可以用dijkstra，又或者雖然沒研究過，不過好像可以用0-1DFS？ 至今仍然不確定為何會FST QAQ

LINK： http://codeforces.com/problemset/problem/1034/C SOL： http://codeforces.com/contest/1047/submission/44828198 這題思緒上好複雜@@，趴在桌上、一直理解不了解答QQ 先想想只分兩層的情況，假設整棵樹總合為S，以i節點為root的subtree的總合為Si，然後我想將整棵樹分成k塊的話，那麼每一塊的總和必須是S/k，所以明顯只有Si mod S/k == 0的i是需要考慮的，假設恰有k個滿足條件好了，那就把那些i和其祖先斷開，又顯然每一塊總和還是S/k的倍數，又因為每塊總合的加總為S，所以每塊大小必為S/k。 也就是說，對於想分成k塊，我們只需要考慮所有Si mod S/k == 0的節點數是否為k就好了。 現在反過來想，對於每一個Si，取S / gcd( S, Si )，這就是這塊所能提供的塊數中的最小值了，舉例來說，這張圖可能可以以gcd( S , Si )為一塊來切，也可以以gcd的因數來切，也就是這塊所能提供的k。 那對每一個節點都取 S / gcd( S, Si )，再用類似埃式篩法的方法對倍數進行加總就好了。 只切一塊的方法數顯然只有1種。 最後再看看每一個算出來的塊數k是否真的有k，有的話，對於k的所有倍數，因為k可以當作它們的上一層，所以它們每個的方法數都要加上切成k塊的方法數。 在code裡面有S/gcd(S,Si) <= n，是因為切的塊數要少於n塊，然後S的最小值是n，所以這樣寫是好的。 話說我估不好複雜度，前面大概是n( logn + logC ) ，但是最後的那面算一下好像是n^2，但事實上明顯不是@@

LINK： http://codeforces.com/contest/1072/problem/E SOL： http://codeforces.com/contest/1072/submission/44821667 好毒的一題@@ 照慣例看完還是沒想法，然後就去看解了。 題目要求O(n/3)之內完成，所以大約每3個就要用一次操作完成，但發現 ... 0 1 1無法辦到，所以就轉而考慮每6個用2次完成，接著暴力構一下就會發現在數列長度>=11時可以辦到。 這樣一來在 >=11 時都可以暴力弄好，那 <= 10 的時候嘞？ 其實題目這裡給得比較鬆，有12次操作，我的作法是直接從後面掃，掃到1的話就將後3個反轉，最後會剩下前2個數字，然後暴力一下會發現1出現在最邊邊的時候數列長度>=7的話可以做好；1出現在第2個位置的時候數列長度>=8的話可以，這邊就判一下就OK了。 不過好像有個漏洞，會不會在長度<=7，亂掃後會在第2個位置剩下一個1的序列是否有其他掃法可以做好呢？不會的原因是因為我們暴力確認了只在第2個位置剩下一個1的時候是不可能達成的，如果有其他掃法的話就代表是有可能的，因為反轉是個步步可逆的操作。 為甚麼這題我覺得毒呢？因為一大堆暴力啊orz，看完官解後，我自己寫了一堆暴力，亂WA一片QQ

LINK： http://codeforces.com/contest/1072/problem/F SOL： http://codeforces.com/contest/1072/submission/44824735 這題看了就沒想法，花了一小時多才終於看懂解了。 首先會想到質因數表示法，然後可以將其表示為一個vector，注意到這個向量在題目的要求下，sort完後等價於原本的，所以將1e6以下的所有數字所表示的vector sort後會發現數量其實很少。 接者問題就變成了兩個vector之間最少需要多少次操作才能相等。 錯誤解：floyd-warshall，因為操作過程中的向量有可能是在1e6以下表示不出來的 ( 像是2^20 ) 觀察題目要求，它要求我們要將兩個數字的vector的個元素相乘後相等，所以可以試著bruteforce每個vector變成每種乘積最少需要多少操作，估計一下乘積後會發現最大值一定在1000以下，因為2*3*5*7*11*13*17 > 1e6，對1000以下的所有數字，bruteforce每種乘積的不同表示法，並對所有vector求出最小所需操作，這樣我們就有每種vector到每種乘積所需的最小操作步數了。 最後對於題目詢問的x, y，去bruteforce兩個向量元素乘積變成哪個數字比較好。 總結： 我認為牽扯到"相乘等於多少"、"質數"......之類的題目的複雜度都不好估，像是這題雖然範圍高達1e6，但其實不等價的向量竟然只有300個，還有1000以下分成少於等於10個數字乘積的分法，這個直觀來看也不好估；總之題目可能會出一些等價的東西來混淆視聽，要多加注意！ 話說這題那個1000，我試了幾個數字後發現512也可以過；分成10個數字乘積，我改成7個數字也是能過。

LINK： http://codeforces.com/contest/1042/submission/43004397

LINK： http://codeforces.com/contest/1005/problem/F 我覺得我的潛意識就覺得自己很弱了，不過在實際試試看之前怎麼知道到底弱不弱呢？ http://codeforces.com/contest/1005/submission/41564409

LINK： http://codeforces.com/problemset/problem/999/E 我竟然寫不出這個咚咚@@ http://codeforces.com/contest/999/submission/41519719 要注意圖的走訪順序，然後deg+就好了啊@@

LINK： http://codeforces.com/contest/997/problem/C QAQ http://codeforces.com/contest/998/submission/41515819 可悲，數學好難，一整個上午都在弄排容；麻將也一直輸；喝紅茶然後就肚子痛，好羨慕K-ON的放學時光、還有真紅，可以暢快地喝紅茶；CF rating掉到1700以下