Individual Training 22/06/2010

今次題目偏向數學..

比較興奮的是做到B (雖然其它人一開波就做到) , 但這題其實幾年前已見過, 但一直都未識/未敢做, 算是又對 number theory 踏前了一步..


F - PKU 1997 Word Puzzle

題目: given 一個 200*200 的 lowercase letter array, 再 given 1000 個長度不多於 20 的字串, 問係個 2D array 度起哂 d word 出黎後 (8方向) , 剩返邊d character


做法: 直接搵會超時 (200*200*8*20*1000) , 所以我將果 1000 個 word 用一棵 trie 儲起哂, 每次向8個方向行直接知道有無字, 將複雜度降為 200*200*8*20



B -  PKU 1061 青蛙的约会

題目: 在一個長為 L 的 ring 上, 兩隻青蛙分別為於 position x 和 y 上, 每一個 time period 它們都會向同一方向跳 m 和 n 格, 問最快幾時先會同時在同一個 position, 可以無解

L <= 2100000000


做法: 印象中第一年玩HKOI mini comp 就見過呢題, 不過當然唔識做.

如果把方程寫出.. 就是

x + T*m = y + T*n   (mod L)

T(m-n) = y-x   (mod L)

簡化一下.. 就是要解 T*a = b   (mod L) , 也就是所謂的解模方程

諗左好耐, 發現同 extended euclidean algorithm 有關 !

T*a = b   (mod L) 即

T*a + L*k = b

如果對 a 和 L 搵 GCD 的話, 由 extended 果 part 可以有

a*i + L*j = gcd(a,L)

結論 1: 如果 b % gcd(a,L) 不是 0, 則輸出 Impossible

如果將條方程左右乘大 b/gcd(a,L) 的話.. 就得到

a*i*b/gcd(a,L) + L*j*b/gcd(a,L) = b

解得 T = i*b/gcd(a,L)

但注意這只是 T 的其中一個解,  T 應該有無限個解的
output 要最小而非負的 T

由於 a*i + L*j = gcd(a,L) , 得知 T 的每一個解相差 L/gcd(a,L)

即一般解為 T + r*L/gcd(a,L) ,  r = integer

有呢樣野搞兩搞就可以將佢變返做最小而非負


其實做到呢題真係好開心, 算係一個突破吧
平時做 judge 一定唔會自己諗到, 要在果個環境下先會做到..



仲有一題很難但值得打出黎..

D -  UVa 10692 Huge Mod

搵 a₁^a₂^a₃...^a_n mod m

有少少想法.. 但如果真係要做應該有排 struggle ...