PolarisChiba的code收藏區

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個數字也是能過。