NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2008高中組決賽
 NPSC 2008 高中組 決賽 F.數列

作者 主題: NPSC 2008 高中組 決賽 F.數列  (閱讀 2432 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 231
    • 檢視個人資料
NPSC 2008 高中組 決賽 F.數列
« 於: 十一月 30, 2009, 01:38:21 pm »

NPSC 2008 高中組 決賽 F.數列

說明:有一個數列的前幾項是:0、1、3、7、12、20,任兩項(可重覆)相加的和絕不會出現兩次,即 a+b != c+d (a、b、c、d 均為數列裡的元素),而且第 n 項元素一定是大於第 n-1 項中最小的那一個,請你找出 2^32 以內的每一項是多少。

解法:本地建表,因為這個程式無法在10秒鐘內計算出需要的答案,故先寫一個建表程式,把答案輸出到一個檔案,再利用這個檔案的內容當作主程式陣列的預設值,即可快速地以查表法得到答案。建表程式部分,利用類似篩法的作法,以一個位元陣列計錄每一個數字是不是答案,將不可能的一一去掉,便可以很快地找出答案。因為數字高達2^32,故兩者相加會超過 unsigned long int 的範圍,所以我們把原式 a+b != c+d 改成 a-d != c-d,a、c 是減法中較大的數,如此即可將數字控制在 unsigned long long int 的範圍中。下面的參考程式是一邊計算一邊輸出,可隨時中斷,再次執行時只要把上次的輸出檔更名為輸入檔的檔名,便可接著上一次找到的最後一個數字繼續執行。而主程式只是用一個陣列來儲存答案,沒什麼特別的,只是數字超過 2^31 的部分後面要加上 UL, 否則可能會出錯。

參考程式:(By sagit)

(一)建表程式

代碼: [選擇]
// NPSC 2008 高中組決賽
// 題目 F - 數列
// 建表程式
// By sagit at TCGS
#include <cstdlib>
#include <iostream>
#include <deque>
#include <bitset>

using namespace std;

const unsigned long int MAX=4294967250UL; // 處理的最大數字
deque<unsigned long int> Seq;           // 記錄該數列
bitset<MAX> V;                          // 記錄該數字是否使用過

bool Test(unsigned long int n)          // 測試這個數字是否正確
{
    int i;
    for (i=Seq.size()-1; i>0; i--)
        if (V[n-Seq[i]]) return false;
    return true;
}

void Insert(unsigned long int n)        // 插入一個數字到數列中
{
    int i;
    Seq.push_back(n);
    cout << n << ", ";
    if (Seq.size()%10==0) cout << "\n"; // 每10個換一次行
    for (i=0; i<Seq.size(); i++)        // 將不可能的先去掉
        V[n-Seq[i]]=true;
    cerr << Seq.size() << "-" << n << "\n"; // 輸出目前進度
}

int main()
{
    freopen("pf_1.txt", "rt", stdin);
    freopen("pf_2.txt", "w+t", stdout);
    ios_base::sync_with_stdio(false);
    unsigned long int i;
    char c;
    while (1)                           // 讀取已經處理好的數列
    {
        cin >> i >> c;
        if (cin.fail()) break;
        Insert(i);
    }
    if (Seq.empty())                    // 設定數列的啟始值
    {
        Insert(0);
        Insert(1);
    }
    for (i=Seq.back()+1; i<MAX; i++)    // 開始處理
        if (Test(i)) Insert(i);         // 測試正確則把它加到數列裡
    cout << "\n" << Seq.size() << endl; // 輸出數列元素個數
//    system("PAUSE");
    return 0;
}

(二)主程式

代碼: [選擇]
// NPSC 2008 高中組決賽
// 題目 F - 數列
// By sagit at TCGS
#include <cstdlib>
#include <iostream>

using namespace std;
const int MAX=7601;
const unsigned long int S[MAX]={
0,1,3,7,12,20,30,44,65,80,96,
122,147,181,203,251,289,360,400,474,564,
592,661,774,821,915,969,1015,1158,1311,1394,
1522,1571,1820,1895,2028,2253,2378,2509,2779,2924,
3154,3353,3590,3796,3997,4296,4432,4778,4850,5122,
5242,5297,5750,5997,6373,6800,6924,7459,7546,7788,
8219,8502,8729,8941,9881,10199,10586,10897,11288,11613,
11875,12033,12930,13393,14046,14533,14900,15165,15687,15971,
16618,17354,17931,18844,19070,19630,19669,20721,21947,22525,
23290,23563,23880,24595,24767,25630,26036,26254,27218,28565,
...... // 中間省略
4267538820UL,4268306780UL,4268768376UL,4271069618UL,4272199924UL,
4272853295UL,4274335619UL,4276397953UL,4276414928UL,4280258856UL,
4280719359UL,4281771507UL,4283826680UL,4285239463UL,4285344758UL,
4286414999UL,4287955925UL,4288242680UL,4288819021UL,4294853005UL};

int main()
{
    freopen("pf.in", "rt", stdin);
    freopen("pf.out", "w+t", stdout);
    ios_base::sync_with_stdio(false);
    int n;
    while (1)
    {
        cin >> n;
        if (n<0) break;
        if (n>=MAX) cout << 0 << endl;
        else cout << S[n] << endl;
    }
//    system("PAUSE");
    return 0;
}
記錄

electron

  • 新手
  • *
  • 文章數: 5
    • 檢視個人資料
回覆: NPSC 2008 高中組 決賽 F.數列
« 回覆 #1 於: 十二月 19, 2009, 07:45:21 pm »

實際測過...本地建表花的時間其實也很可觀...嘖嘖 :o
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 231
    • 檢視個人資料
回覆: NPSC 2008 高中組 決賽 F.數列
« 回覆 #2 於: 十二月 19, 2009, 11:02:43 pm »

沒錯, 那年的裁判長也說了,
這題是用來防破台的,
因為本地建表的程式要跑三~四個小時,
所以如果不是一開始就先建表,
之後有想到這個方法也來不及了....
記錄

electron

  • 新手
  • *
  • 文章數: 5
    • 檢視個人資料
回覆: NPSC 2008 高中組 決賽 F.數列
« 回覆 #3 於: 十二月 19, 2009, 11:43:56 pm »

囧...
記錄

electron

  • 新手
  • *
  • 文章數: 5
    • 檢視個人資料
回覆: NPSC 2008 高中組 決賽 F.數列
« 回覆 #4 於: 十二月 20, 2009, 09:20:48 am »

建完表上傳發現字元太多...超過最大限制...怎辦阿 囧
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 231
    • 檢視個人資料
回覆: NPSC 2008 高中組 決賽 F.數列
« 回覆 #5 於: 十二月 20, 2009, 03:06:42 pm »

NPSC的題目本來就不是為了Online Judge而設計的,
所以這一題, 你直接用官方提供的答案測資做輸出,
應該就會AC了....
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2008高中組決賽
 NPSC 2008 高中組 決賽 F.數列