斑的家

A. Matrix

題意：

給數字陣列Ai , 用A 去組成一個matrix B 且 Bi,j = Ai*Aj

有一個數字 n, 問有幾個 submatrix 內的數字合等於 n

題解：

令 sum(a,b) = A_a + A_(a+1) ... A_b.

假設有一個 submatrix from (a,b) to (c,d) , 要求它的合，除了把submatrix 裡的數字用暴力法算出

來，也可以使用Bi,j = Ai*Aj 這個特性。 submatrix 的合 = sum(a,b)*sum(c,d)。

也就是說，n = sum(a,b)*sum(c,d)。

我們先預處理： 暴力算出所有array A 的所有區間合且區間合是n 的因數

接下來就只要找出任2個區間合相乘= n 。

這題需要特別注意 n = 0 的情況。

B. Free Market

題意：

有n 個數字和一個數字d，算出所有的subset sum = si，每個si 都對應到一個點，若 si+d >=sj ，則此2點有一條邊。

另外有一個初始點 S，此點的subset sum = 0，現在從點S出發，找出可以到達最大subset sum 的點，且最少需要幾個邊？

題解：

類似dijkstra 。

注意：題目B的原意有點難懂。

C. Beautiful Set

題意：

有數字k，想找出一個beautiful set ，

beautiful set(B)的特性是

(1) 對於任意prime ，如果此prime 可以除以某Bi，則

此set 之中至少有一半的數字可以被此prime 整除。

(2) 數字大小不超過 2*k*k。

(3) set 大小是k。

題解：

看了解答後也不知原理。

D. Ghd

相當有趣的一題，用到隨機的概念去解。

題意：

有n 個數字Ai，找出ghd。

Ghd is a positive integer g, such that at least half of numbers from the set are evenly divisible by g

and there isn't such g' (g' > g) that at least half of the numbers from the set are evenly divisible by g'.

題解：

若隨便選一個r = Ai ，則其是用來算 ghd 的可能性有0.5。令ghd set 是用來算ghd 的 數字集合。

假設r 屬於 ghd set 。算出xj = gcd(r,Aj)。

ghd會是 r 的某個因數。

令r 的因數為 fac[i] 。

令 fac_count[j] 表示 xi % fac[j] == 0 的個數。

我們已知ghd 是r 的某個因數fac[i]，且 fac_count[i] >=(n+1)/2。

現在出現一個問題，就是如果fac[i] % fac[j] == 0的

話，那麼fac_count[j] 需要加上fac_count[i] 。

最後找出滿足fac_count[i] >=(n+1)/2 的最大因數就是答案。

由於r是亂選的，我們只要選得夠多次，失誤機率就會下降 1 - 2^g，g 為選的次數。

 E. Empty Rectangles

題意：給一個長方形，每個entry 只有0 或 1 的數字。 問有幾個sub rectangle 的合是等於 k。 兩邊長 < 2500。

題解： 若暴力解是O(n⁴)，鐵定不行。可以使用divide and conquer。見圖。

有一個函式 f(x1,y1,x2,y2) 可以找出在其範圍內sub rectangle 合等於 k 的有幾個。

對於一個rectangle 左上是(x1,y1) ，右下是(x2,y2)，去找出經過 x = (x1+x2)/2 ，的sub rectangle 合笒於k的

有幾個，假設有 s 個。那麼 f(x1,y1,x2,y2) = f(x1,y1,mid,y2) + f(mid+1,y1,x2,y2) + s 。

交替地去切長以及寬。

其中有一個trick 。見圖

上面虛線範圍內是某個sub rectangle 等於 g , 且 g <=k 。如果先算出這個，那麼要算出下圖中的sub rectangle 的合=g 的情況時，

就不必從中線開始重算。只要從上圖中虛線繼續往2側拓展及可。