[Codeforces] 1034C
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，但事實上明顯不是@@
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，但事實上明顯不是@@
留言
張貼留言