HDU 5451 Best Solver

acm math

兩種推法

1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
(5 + 2*sqrt(6)) ^ n = An + Bn*sqrt(6)

f(n) = [(5 + 2*sqrt(6))] * [An-1 + Bn-1*sqrt(6)]
     = (5*An-1 + 12*Bn-1) + (2*An-1 + 5*Bn-1)*sqrt(6)


5   12          An-1      An
2   5     *     Bn-1   =  Bn

A1 = 5, B1 = 2

[An + Bn*sqrt(6)] + [An - Bn*sqrt(6)] = 2*An
因為(5 - 2*sqrt(6))比1小比0大, 他的n次方也一定比1小比0大
我們把這當1
[An + Bn*sqrt(6)] = 2*An - 1
Answer = = 2*An - 1

而因為n很大, 而mod小, 我們知道不停乘同一個數, 而且mod同一個mod, 會最終出現重複 (在n-1個格子中放入n個球, 一定有一個格子有至小2個球)
而且會是不停重複 ex: 1 2 3 1 2 3 1 ....
我們可以找出開始重複的位置

我覺得這個比較容易推, 但我看別人的解都是第二種

More...

ICPC 7400 / HDU 5572 An Easy Physics Problem

acm geometric

參考 http://www.cnblogs.com/helenawang/p/5465481.html
再加上一些註解

復習了一下 cross product 和 dot product
在這記錄一下如何找 line segment 和 circle 的 intersection

1
2
3
4
5
6
7
8
9
10
11
12
13
14
let we have Point A and B
We know the center of circle C and it radius

We set Point P which is between AB, angle CPA = 90 // 事實上OP 和 AB不是連起來也可以
let ( x(vector AB) + (vector CA) ) . (vector AB) = 0
since we know AB, CA. we can find x

x(vector AB) = (vector AP)

Then we can find x, y of P

radius^2 - CP^2 = QP ^ 2 // Q is the first intersection

Lastly we can use the ratio to get location of Q

More...

ICPC 7411 LCM Walk

acm math
  • LCM = A*B/gcd(A, B)
  • gcd 在前進後退時不會變.
    • let x = ab, y = bc , we can let every two integer in this form (3, 2) = (1 x 3, 1 x 2)
    • LCM = abc
    • abc + ab = a b (c+1)
    • gcd(a * b * (c+1), bc) = b = gcd(x, y), c and c+1 must be coprime
  • a2 = a1( (b/gcd) + 1 )
    • 因為gcd不變, gcd(b, a1) == gcd(b, a2)
    • 而a2, b 是己知的, 我們可求出a1

我們就不停往回dfs, 但要小心 gcd 最終會成為 1,
那gcd不變的那一條式就會不適用, 所以要檢查gcd有沒有變.

我們也可以先兩邊除去gcd, 那他們gcd就會成為1, 不用特別檢查.

More...

icpc 7304 Queue of Soldiers

acm dp

由最低的高度開始 dp, dp[i][x] i 是 第幾個高度, 由低至高. x 是有 i 個高度的情況下死了 x 個人

我一開始用了dfs, 果不其然 TLE 了.
之後用dp, 由高的那一邊的想, 發現比較高的人的情況 會 depend on 比較低的人的情況
多虧師兄指教才想通

反思: 如果之後再有這種情況, 應由被依賴的那一邊開始推進

而 nCr 就用 a^m-1 % m = 1 -> a^-1 % m = a^m-2 % m

而解決 TLE 的方法就是加 memorization

More...

ICPC 7305 Jumping Joey

acm dp

在最佳情況下

  1. 從後面開始, pads 之 間的距離越長越好, 那前間就有更多拉繩子的空間
  2. 不用在意 pads 的實際位置, 重要的是距離, 因為他決定了能不能跳
  3. 只要不違反繩子的限制, pads 的所有移位都是可行的

從後面開始想, 如果繩子 <= D, 那把他拉直(因為 1 ), 再跳
不然的有兩個選擇, 拉到D再跳, 或完全拉直再游

tight 指有多少段繩子被拉到 <= D 的最長長度

dp 不等於 pads 的位置, 因為他可能比 pad[n+1]-pad[0] 更大, 但那不要緊, 因為不影響結果

More...

icpc7306 Primorial vs LCM

acm Math

LCM(1 to 2) = (2)
LCM(1 to 3) = (2 3)
LCM(1 to 4) = (2 2 3)
LCM(1 to 5) = (2 2 3 5)
LCM(1 to 6) = (2 2 3 5)
LCM(1 to 7) = (2 2 3 5 7)
LCM(1 to 8) = (2 2 2 3 5 7)

LCM(1 to n) = 每個質數^最大次方 互乘

LCM(1 to n)/prime(1 to n) = 每個質數^(最大次方 - 1)互乘

問題解法: 先把prime找出來, 再列出他們的幕 (不列質數自身, 因為之後要除prime(1 to n))
把他們排一下, 再一直乘

More...