2013年3月4日 星期一

USACO 2012 三月 金組

第一題:

關鍵:


這個數量約等於 nlgn,因為你在建表的時候,大致像下面那樣



for(int i = 1; i < N; i++)
        for(int j = i; j < N; j += i) P[j].PB(i); 

這樣子的數量級差不多是O(nlgn),因為 sum of 1/x 是 lgn。

所以:2^質因數個數 <= 因數的數量 <= nlgn

至於第一項是哪裡來的呢?是排容原理。

總之因數數量的總和其實是很小的,要注意這一個地方。

第二題:

相信大家都寫過,這題直鏈的版本,想通就解決了,較為簡單的一個題目。

第三題:

       我寫的是一個暴力搜的方法,並用目前答案去做剪枝,但這種作法在暴力方式是1*2*3*4*5*6*7...這樣子會比較有效。

       我一開始寫的暴力方式 n*n-1*n-2...,就會顯得沒有什麼意義,以後要多想由小到大的方法,會比較好Cut。

      官方題解不知道是在寫什麼毛,明天再去看看。

沒有留言:

張貼留言