NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2005高中組決賽
 NPSC 2005 高中組 決賽 G.陽數

作者 主題: NPSC 2005 高中組 決賽 G.陽數  (閱讀 1873 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 231
    • 檢視個人資料
NPSC 2005 高中組 決賽 G.陽數
« 於: 十二月 08, 2009, 02:29:15 pm »

NPSC 2005 高中組 決賽 G.陽數

說明:將一個數以二進位表示,如果 1 的個數比 0 多,則這個數就是陽數。現在給你一個正整數 M,請問你從 1 ~ M 之間有多少個陽數。

解法:不要一個一個去數到底從 1 到 M 之間有多少個陽數,而是將它分成幾個範圍,再去計算每個範圍有幾個陽數。

以 89 這個數字為例,以二進位表示為 1011001,我們以最高位元所在位置 1000000 將它分成兩部分: 1 ~ 111111 和 1000000 ~ 1011001。後面的部分可以依照 1 所在的位置在分成: 100XXXX 、 1010XXX 、 1011000 、 1011001 四個部分,最前面的 100XXXX 已經有 1 個 1 和 2 個 0,而有 4 個位數還不確定,要構成一個陽數,則這 4 個位數中至少要有 3 個 1,所以 100XXXX 的陽數個數為 C(4,3)+C(4,4) ,後面的 1010XXX 的陽數個數為 C(3,2)+C(3,3) ,以此類推。由於 10^15 大約為 2^50 ,因此我們將 C(M,N) M,N=0~50 的表格建好,可以加快執行速度。

至於前面 1 ~ 111111 的部分,也可以分解成 1XXXXX 、 1XXXX 、 1XXX 、 1XX 、 1X 、 1 等六個部分,可以用前面提到的技巧算出這些範圍的陽數個數,由於這個部分很常用,所以也可以建一個表將結果存起來,以節省時間。

參考程式:(By sagit)

代碼: [選擇]
// NPSC 2005 決賽 - 題目 G - 陽數 //
#include <iostream>
#include <fstream>
#include <cstdlib>
#define MAX 51

using namespace std;

long long int C[MAX][MAX]={1}; // 記錄組合 C(m, n) 的值
long long int T[MAX]={0}; // 記錄 0 ~ 2^N-1 之間有幾個陽數

void Init()
{
    int i, j;
    long long t;
   
    for (i=1; i<MAX; i++)
    {
        C[i][0]=1;
        C[i][i]=1;
        for (j=1; j<i; j++)
            C[i][j]=C[i-1][j]+C[i-1][j-1];
        for (j=0, t=0; j<(i+1)/2; j++)
            t+=C[i-1][j];
        T[i]=T[i-1]+t;
    }
}

long long int Sub(int len, int q)
{
    int i;
    long long int t;
    for (t=0, i=len; i>=0; i--)
    {
        if ( (i+q)<=(len-i) ) break;
        t+=C[len][i];
    }
    return t;
}

long long int Sun(long long int m)
{
    const long long int p=0x00000001;
    long long int t;
    int i, q;
    for (i=MAX; i>0; i--)
        if ( (p<<i)&m ) break;
    t=T[i--];
    for (q=0; i>=0; i--)
    {
        if ( (p<<i)&m )
        {
            t+=Sub(i, q);
            q++;
        }
        else q--;
    }
    if (q>=0) t++;
    return t;
}

int main()
{
    ifstream fin("pg.in");
    ofstream fout("pg.out");
    int n;
    long long m, t;

    Init();
    fin >> n;
    while (n--)
    {
        fin >> m;
        t=Sun(m);
        fout << t << endl;
    }

//    system("PAUSE");
    return 0;
}
記錄

littleflyer

  • 新手
  • *
  • 文章數: 1
    • 檢視個人資料
回覆: NPSC 2005 高中組 決賽 G.陽數
« 回覆 #1 於: 七月 31, 2010, 04:36:36 pm »

請問一下關於sagit所實作的方法我不太了解,可以請教sagit Sub 和sun這兩支副程式的實作原理嗎?
long long int Sub(int len, int q)
{
    int i;
    long long int t;           
    for (t=0, i=len; i>=0; i--)  <===這個for 迴圈是在做什麼事情??
    {
        if ( (i+q)<=(len-i) ) break;
        t+=C[len];
    }
    return t;
}

long long int Sun(long long int m)
{
    const long long int p=0x00000001;
    long long int t;
    int i, q;
    for (i=MAX; i>0; i--)    <==這邊的for我也不懂他的用意
        if ( (p<<i)&m ) break;
    t=T[i--];
    for (q=0; i>=0; i--)   <==這邊的for我也不懂他的用意
    {
        if ( (p<<i)&m )
        {
            t+=Sub(i, q);
            q++;
        }
        else q--;
    }
    if (q>=0) t++;
    return t;
}
記錄

qwqw

  • 新手
  • *
  • 文章數: 13
    • 檢視個人資料
回覆: NPSC 2005 高中組 決賽 G.陽數
« 回覆 #2 於: 八月 02, 2010, 08:15:37 pm »

long long int Sub(int len, int q)
==>回傳 0~2^len 有多少陽數,q則是1比0多q個。(排組機中組合的想法)

for (t=0, i=len; i>=0; i--)
{
    if ( (i+q)<=(len-i) ) break;
    t+=C[len];
}
==>將所有答案加進t裡。(排組機中組合的想法)

long long int Sun(long long int m)
==>回傳0~m有多少陽數。

for (i=MAX; i>0; i--)
    if ( (p<<i)&m ) break;
==>找出最左邊的1是第幾位。

for (q=0; i>=0; i--)
{
    if ( (p<<i)&m )
    {
        t+=Sub(i, q);
        q++;
    }
    else q--;
}
==>是1的就去尋找有多少是陽數。

※註:我可能解釋的不好,這題就用組合的方法就ok了!只是要想如何code出來。

上面的注解好像有一點錯,只是小錯~~可能有人看出來了.....不過我也不知要怎麼修改~~我建議是直接模擬上面的程式碼這樣會懂的比較快。原本是想說舉例說明.....可是舉太簡單的例子可能還是不懂....太難的又會很麻煩......結論是自己去模擬吧!
« 上次編輯: 八月 02, 2010, 09:55:31 pm 由 qwqw »
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2005高中組決賽
 NPSC 2005 高中組 決賽 G.陽數