NPSC 補完計劃

請改到本站新網址

本站已停止更新，請改到本站之新網址
新NPSC補完計劃：
http://www3.tcgs.tc.edu.tw/npsc/index.php

NPSC 題型分析

這裡將 2005 年以來的 NPSC 題目做個簡單的分類，希望對各位同學有所幫助。(註：這些題目可能不只一種解法，僅以最簡單的一種去分類。)

一、暴力法、直解：暴力法是把所有的情況列出來一個一個判斷，通常是用迴圈來處理。(這邊不考慮要使用 BFS、DFS 的情況)；而直解是依照題意直接做就可以，(這邊不考慮模擬題的類型)，這兩種都是不太需要用什麼特別的演算法即可解決。

2005 初賽 - 題目 F - 密碼安全設定 (字串處理)
2005 決賽 - 題目 C - 節約尺
2005 決賽 - 題目 E - 智慧型單字查詢 (字串處理)
2006 決賽 - 題目 H - PS3
2007 初賽 - 題目 D - 打不倒的空氣人 (字串串接)
2007 決賽 - 題目 C - 小姐，我認識妳嗎？ (NPSC 計分模擬)
2008 初賽 - 題目 B - 下雨天
2008 決賽 - 題目 B - 幼稚國王去旅行

二、數學解：比直解的題目複雜一些，需要用到一些數學推導或公式。

2005 決賽 - 題目 G - 陽數 (位元層次思考)
2006 初賽 - 題目 C - 幼稚國王的獎賞 (位元層次思考、高斯消去法)
2006 決賽 - 題目 D - 分「樹」 (位元層次思考)
2007 初賽 - 題目 B - 完全子圖 (最大公因數、歐幾里德演算法)
2007 初賽 - 題目 E - 東方幻想鄉 (平面幾何、向量)
2008 初賽 - 題目 A - 畢達哥拉斯之謎 (畢氏定理、勾股數)
2008 初賽 - 題目 E - 幼稚的災難 (代數、次方、模數)
2008 決賽 - 題目 D - 輾轉難眠 (最大公因數、次方)

三、模擬題(Simulation)：依照給定的條件，去模擬出結果，有點類似寫遊戲的方式，只是不需要設計華麗的畫面。

2005 初賽 - 題目 A - 忍耐任務 (物理之平面運動)
2007 初賽 - 題目 A - 千里傳情
2007 決賽 - 題目 A - 誰來午餐？ (Priority Queue、最小公倍數)
2008 初賽 - 題目 C - 計票程式

四、貪婪演算法(Greedy)、排序(Sort)：貪婪演算法是依照一個自定的決策(貪婪法則)，每次取最有利的一個，而這決策的過程可能會需要對輸入的資料做排序。

2005 初賽 - 題目 B - 惱人的零錢
2005 決賽 - 題目 A - 誰先晚餐
2006 初賽 - 題目 B - 古力德
2006 決賽 - 題目 E - 海賊王
2007 決賽 - 題目 F - 交換禮物
2008 初賽 - 題目 D - 郵輪
2008 決賽 - 題目 H - 幼稚國王的行程 (Dijkstra's 最短路徑演算法)

五、動態規劃(DP)：以建表格的方式來記錄每一種情況，並推導出每一項與前面幾項的遞迴關係，依照這關係將表格建立起來。

2005 初賽 - 題目 C - 互質任務
2006 初賽 - 題目 E - 漢米頓的麻煩 (Floyd-Warshall 演算法)
2006 初賽 - 題目 F - 營地
2006 決賽 - 題目 C - 畢業演奏
2006 決賽 - 題目 F - 假日的奇想曲
2007 初賽 - 題目 F - 打不倒的樹木人
2007 決賽 - 題目 D - 正直DE (Matrix Chain Multiplication 問題)
2008 決賽 - 題目 A - 蜜蜂的約會 (LIS、LCS)
2008 決賽 - 題目 G - 獎金 (最大連續元素和)
2008 決賽 - 題目 C - 咒語

六、各個擊破法(D&C)、遞迴(Recursion)：各個擊破法是將問題分解成若干個和自己一樣但規模較小的問題，一直分解到可以直接解決為止，過程中我們通常是使用遞迴來處理。

七、廣度優先搜尋法(BFS)：圖形(Graph)走訪的一種，主要用於計算每個節點與起點之間相隔幾層(即深度)。

2006 初賽 - 題目 A - 跳格子遊戲
2006 決賽 - 題目 A - 好多油瓶
2006 決賽 - 題目 B - 射手座之日 (DFS 亦可)
2006 決賽 - 題目 G - 剖面導向程式設計 (DFS 亦可)
2007 初賽 - 題目 C - 排水系統 (DFS 亦可)

八、深度優先搜尋法(DFS)、回溯法(Back-tracking)：DFS 為另一種圖形的走訪方式，主要用於快速找到一條路徑，可以配合回溯法將不可能會有結果的分技直接返回。

2005 決賽 - 題目 F - 捷運漫遊
2006 初賽 - 題目 E - 漢米頓的麻煩
2007 決賽 - 題目 G - 丁丁共和國
2007 決賽 - 題目 H - 數字拼盤
2008 初賽 - 題目 F - 國家 (Strongly connected components, SCC)

九、其他：不屬於上述題型，難以歸類的題目。

2007 決賽 - 題目 E - 核心字串 (Queue)
2007 決賽 - 題目 B - 平行運算 (Graph)
2008 決賽 - 題目 E - 不景氣的年代
2008 決賽 - 題目 F - 數列 (本地建表)

NPSC 2008 決賽 - 題目 H - 幼稚國王的行程

說明：給你一個有重覆邊的有向權重圖，請你找出可以在指定距離內回到自己的點。

解法：Greedy 解，逐點使用 Dijkstra's 的最短路徑演算法，看是不是能在指定距離內回到自己。這一題的測資有兩個陷阱，一是有的邊是自己回到自己，二是兩點之間可能不只有一個邊，要特別處理。

參考程式：

// NPSC 2008 高中組決賽
// 題目 H - 幼稚國王的行程
// By sagit at TCGS
#include <cstdlib>
#include <cstdio>

using namespace std;

const int MAX=1002, VERY_LONG=100000;
int G[MAX][MAX], D[MAX], V[MAX], Ans[MAX], An, Num, Dis;
// G 記錄兩點之間的距離, D 記錄到某點的最短距離, V 記錄該點是否已完成
// Ans 記錄答案, An 為答案個數, Num 為點的總數, Dis 為要求的距離

int main()
{
    freopen("ph.in", "rt", stdin);
    freopen("ph.out", "w+t", stdout);
    int k, m, i, j, a, b, c;
    scanf("%d", &k);
    while (k--)
    {
        scanf("%d%d%d", &Num, &m, &Dis);
        for (i=1; i<=Num; i++)          // 將所有點的距離設為很大
            for (j=1; j<=Num; j++)
                G[i][j]=VERY_LONG;
        for (i=0; i<m; i++)             // 輸入每個點的距離
        {
            scanf("%d%d%d", &a, &b, &c);
            if (a==b||G[a][b]<c) continue; // 連到自己或重覆而較長的邊不處理
            G[a][b]=c;
        }
        for (i=1, An=0; i<=Num; i++)    // 逐點做 Dijkstra
        {
            for (j=1; j<=Num; j++)      // 啟始化動作
                D[j]=G[i][j], V[j]=0;
            while (1)
            {
                for (j=1, a=0, b=VERY_LONG-1; j<=Num; j++) // 找一個最近的點
                    if (!V[j]&&D[j]<b) a=j, b=D[j];
                if (a==0||b>Dis) break; // 找不到就離開
                V[a]=1;
                for (j=1; j<=Num; j++) // 以該點更新相鄰點的距離
                    if (!V[j]&&D[a]+G[a][j]<D[j]) D[j]=D[a]+G[a][j];
                if (D[i]<=Dis)          // 若回到原點在限定距離內, 則找到答案
                {
                    Ans[An++]=i;
                    break;
                }
            }
        }
        printf("%d\n", An);             // 列印答案
        for (i=0; i<An; i++)
        {
            if (i>0) printf(" ");
            printf("%d", Ans[i]);
        }
        printf("\n");
    }
//    system("PAUSE");
    return 0;
}

NPSC 2008 決賽 - 題目 G - 獎金

說明：給你一連串的數字，請你找出(一)某段連續數字減去1000後，加起來的總合是最大的。(二)某段連續數字減去1000後，加起來的總合再除以數字個數是最大的。

解法：動態規劃(DP)與直解的題目，方案二即是所有數字中最大的那個，而方案一則是最大連續元素和的題目，可以參考「DJWS的網路日誌」的說明。我們用 S[n] 記錄以第 n 個數為最後一個數的最大連續元素和，則如果 S[n-1] <=0 ，則 S [n] 為第 n 個數字的值A[n]；如果 S[n-1] >0 ，則我們將第 n 個元素也加進去，也就是 S[n]=S[n-1]+A[n]。因為我們只會使用到 S[] 的前一個元素，所以不需要使用一個陣列，只要用一個變數來記錄即可。

參考程式：

// NPSC 2008 高中組決賽
// 題目 G - 獎金
// By sagit at TCGS
#include <cstdlib>
#include <iostream>

using namespace std;

int main()
{
    freopen("pg.in", "rt", stdin);
    freopen("pg.out", "w+t", stdout);
    ios_base::sync_with_stdio(false);
    int n, best1, best2, sum, a, i;
    while (1)
    {
        cin >> n;
        if (n==0) break;
        best1=best2=sum=0;
        for (i=0; i<n; i++)
        {
            cin >> a;
            a-=1000;
            if (a>best2) best2=a;       // 方案二是單日最大值
            if (sum<=0) sum=a;
            else sum+=a;
            if (sum>best1) best1=sum;   // 方案一是最大連續整數和
        }
        cout << best1 << " " << best2 << endl;
    }
//    system("PAUSE");
    return 0;
}

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, 否則可能會出錯。

參考程式：

(一)建表程式

// 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;
}