2015年2月28日 星期六

[TIOJ 1241] 倍因道 Factor and Points

這題我是去查解才會的,但證不出來為什麼這樣是對的........
如果有一天證出來了會在這補上(?

作法:

把題目要分的組叫作A和B好了,這樣比較不會搞混。從 1 開始,每次看他放A比較好還是放B比較好,而判斷的條件是如果放 A 就假設他的倍數通通都被放到 B 了,這樣是他的最高得分,而如果放B那得分就是他的因數在A裡的個數,這可以用類似篩法的方法在每次把數字加進A的時候維護好。如果放A有機會比較好就放A,否則放B。

====================================

3/5 更新證明:

當有一個數 a 被丟進A的時候,代表我們認為之後的最好情形( 也就是 a 的倍數都在 B )的 a 造成的貢獻會比把 a 移到 B 還多 ( 這時的貢獻是 a 的因數個數 ),但如果在之後的決定裡面 2a , 3a , ... , ka 們也跳槽進入A了,那 a 的貢獻就有可能變得太少以至於把 a 丟進B會更好,以下要證明這件事情不可能。

(以下的中括號為高斯符號,d(x) 代表 x 的因數個數)
用反證法,因為 ka 被放入A,由我們的決策方法可以得到 [ n/ ( k a ) ] >= d( k a ),又因為 a 的貢獻為 [ n / a ] - k ,所以此時有 [ n / a ] - k < d( a ),而考慮 [ n/ ( k a ) ] 和 [ n / a ] - k 兩個數,前者是 1~n 裡面 ka 的倍數個數,另一個是 1~n 裡面大於 ka 的 a 的倍數個數,顯然一個數整除 ka 就會整除 a ,所以後者會大於等於前者,也就是 [ n / a ] - k >= [ n/ ( k a ) ],所以 d( a ) > [ n / a ] - k >= [ n/ ( k a ) ] >= d( k a ) ,得到了 a 的因數個數比 ka 的因數個數多,矛盾。

code :

#include<bits/stdc++.h>
using namespace std;
 
int num[3000] ;
 
main()
{
    int T ; scanf("%d",&T) ;
    while(T--)
    {
        int n ; scanf("%d",&n) ;
        memset(num,0,sizeof(num)) ;
        int ans=0 ;
        for(int i=1;i<=n;i++)
        {
            if(num[i] < n/i-1)
                for(int j=2*i;j<=n;j+=i) num[j]++ ;
            else ans+=num[i] ;
        }
        printf("%d\n",ans) ;
    }
}
 

沒有留言:

張貼留言