好像是俄羅斯 IOI camp 的比賽 (好似係), 據聞難度十分高
見在 URAL 上舉行, 忍不住去玩
開始後不久見到有人過 J
首先想到 f(n) 可寫成一堆連續數的 Fibonacci 次方
如果有 f(n) 的質因數分解 form, 可以輕易找到答案
算法1 - 把 1~n 分解, 把每個數的質數加進 primes[] 中, N * sqrt(N)
submit test case 5 便 TLE..
算法2 - precompute 1~n 的質數, 分解時只試質數
submit - 還是 TLE..
算法3 - 分解一個數時, 只試質數, 再加上如果剩下的數是質數便 break
加上這個優化後 (%mod 變成 -mod 那些應該是一定要的) 終於過了..
之後做 D
如果 n = a*a*b, 那麼 a3 ≤ n 或 b3 ≤ n
所以只要試 n1/3 以內的數
K - KMP + DP
狀態是 dp[i][j] = 前 i 個 character, prefix 為 j 可以 match 到多少次
但 '?' 轉移時有些麻煩, 因為不能 greedy 地 match 下一個, 我的做法是不斷走 fail 更新, 理論上好像會達到 N3, 不過還是過了
No comments:
Post a Comment