[Solution] Dhaka 2007
Bachelor
Arithmetic
秒殺題
Nested
Squares
模擬題
The
Dumb Grocer
首先要有1是吧。。。然后我們按照1的個數(shù)來分類，我們來計算恰有k個1的方案數(shù)。
我們在k個1的基礎(chǔ)上加入新的數(shù)，顯然第一個數(shù)只能是k+1
然后加入的數(shù)只能是k + 1
or 2 * (k + 1)
如法炮制。。。發(fā)現(xiàn)非1的數(shù)都具有(k + 1) * t的形式。。。設(shè)其依次為(k + 1) * ti
則{ti}這些數(shù)也滿足題目的性質(zhì)。。。共有f((n - k) / (k + 1))種方案。
設(shè)f(n)是要求的函數(shù)，則f(n) = sigma(f((n - k) / (k
+ 1)), (k + 1) | (n + 1) , k>=1
f(0) = 1
這樣直接做會T...
我們令g(n) = f(n
- 1)
則g(n) = f(n -
1) = sigma(f((n - k - 1) / (k + 1))) = sigma(f(n / (k + 1) - 1)) = sigma(g(n /
(k + 1)), (k + 1) | n, k >= 1
設(shè)n = p1^a1 *
p2^a2 * ... * pr*ar
令h(p1, p2,..,
pr, a1, a2...ar) = g(n)
= h(p1,p2, ...pr, b1, b2, ...br),
0<=bi <= ai, bi不全=ai
注意對于一個確定的n，h()中的p1, p2...pr在計算過程中始終不變。。。所以。。。計算結(jié)果與pi無關(guān),只與ai有關(guān)
這樣狀態(tài)數(shù)就大大減少了。。。直接因式分解后dp就行了。。。
ACM
Puzzles
狀態(tài)壓縮dp
、The
Bells are Ringing、 Photographic
Tour
這三題好像當(dāng)時沒寫summary。。。所以我們假設(shè)比較簡單～～～
You
are around me ...
首先旋轉(zhuǎn)坐標(biāo)，變成平行與xy軸的橢圓，然后坐標(biāo)伸縮。。。變成圓。。。最近點(diǎn)對。。。貼模板。。。
ZJU2107 Quoit Design
一道測最近點(diǎn)對的題。
Infinite
Matrix
顯然，對于固定的j, Ri,
j是一個關(guān)于i的多項(xiàng)式。
注意到數(shù)列Ri, j的差分序列R(i + 1, j) - R(i, j)是可以求出來的（利用Mj, k <= 10的條件，可以在O(10*n^2)的時間內(nèi)算出）
然后有了差分序列求通項(xiàng)就是O(n^2)的事情。
然后記S(p, j)(n)
= Sigma(i^p * R(i, j)) i <= n
繼續(xù)利用差分序列之類的方法求這個，最后再求一個Sum_S(p, j)
預(yù)處理復(fù)雜度大致是O(10*n^3)的。
后面的就好辦了，對每個詢問，把(i + 1)^p二項(xiàng)式展開，最多10項(xiàng)，然后利用公式直接計算。
處理詢問復(fù)雜度O(p*q*n)
POJ3529 Matrix
Analysis，類似的思想，更簡單～
Magnetic
Train Tracks
給定n個點(diǎn)，求可以構(gòu)成多少個銳角三角形。
n <= 1200
話說求銳角三角形不太好算是吧。。。補(bǔ)集轉(zhuǎn)換，我們來求鈍角/直角三角形
<=> 求鈍角/直角個數(shù)。。。
后面的事情就簡單了，是對每個點(diǎn)，將其他點(diǎn)按照極角排序 + 掃描。
Dhaka
2005 Counting Triangles 也是一道補(bǔ)集轉(zhuǎn)換的題～（轉(zhuǎn)化成求三點(diǎn)共線的個數(shù)）
Shanghai 2004
Amphiphilic Carbon Molecules 也是一道極角排序+掃描的題。