第1題

在內存儲器中每個存儲單元都被賦予一個唯一的序號，稱為（ ）。

第2題

編譯器的主要功能是（ ）。

第3題

設x = true，y = true，z = false，以下邏輯運算表達式值為真的是（ ）。

第4題

現有一張分辨率為 2048×1024 像素的 32 位真彩色圖像。請問要存儲這張圖像，需要多大的存儲空間？（ ）

第5題

冒泡排序算法的偽代碼如下：

輸入：數組 L，n ≥ 1。輸出：按非遞減順序排序的 L。
算法 BubbleSort：
    1. FLAG ← n // 標記被交換的最后元素位置
    2. while FLAG > 1 do
    3.      k ← FLAG - 1
    4.      FLAG ← 1
    5.      for j = 1 to k do
    6.          if L(j) > L(j+1) then do
    7.              L(j) ? L(j+1)
    8.              FLAG ← j

對 n 個數用以上冒泡排序算法進行排序，最少需要比較多少次？（ ）

第6題

設 A 是 n 個實數的數組，考慮下面的遞歸算法：

XYZ(A[1..n])
1) if n=1 then return A[1]
2) else temp ← XYZ(A[1..n-1])
3)      if temp < A[n]
4)      then return temp
5)      else return A[n]

第7題

鏈表不具有的特點是（ ）。

第8題

有 10 個頂點的無向圖至少應該有（ ）條邊才能確保是一個連通圖。

第9題

二進制數 1011 轉換成十進制數是（ ）

第10題

五個小朋友并排站成一列，其中有兩個小朋友是雙胞胎，如果要求這兩個雙胞胎必須相鄰，則有（ ）種不同排列方法？

第11題

下圖中所使用的數據結構是（ ）。

第12題

獨根樹的高度為 1。具有 61 個結點的完全二叉樹的高度為（ ）。

第13題

干支紀年法是中國傳統的紀年方法，由 10 個天干和 12 個地支組合成 60 個天干地支。由公歷年份可以根據以下公式和表格換算出對應的天干地支。

天干=（公歷年份）除以 10 所的余數

地支=（公歷年份）除以 12 所的余數

例如，今年是 2020 年，2020 除以 10 余數為 0，查表為“庚”；2020 除以 12，余數為 4，查表為“子”，所以今年是庚子年。

請問 1949 年的天干地支是（ ）

第14題

10 個三好學生名額分配到 7 個班級，每個班級至少有一個名額，一共有（ ）種不同的分配方案。

第15題

有五副不同顏色的手套（共 10 只手套，每副手套左右手各 1 只），一次性從中取 6 只手套，請問恰好能配成兩副手套的不同取法有（ ）種。

第16題

#include <cstdlib>
#include <iostream>
using namespace std;

char encoder[26] = {'C', 'S', 'P', 0};
char decoder[26];

string st;

int main() {
    int k = 0;
    for (int i = 0; i < 26; ++i)
        if (encoder[i] != 0) ++k;
    for (char x = 'A'; x <= 'Z'; ++x) {
        bool flag = true;
        for (int i = 0; i < 26; ++i)
            if (encoder[i] == x) {
                flag = false;
                break;
            }
        if (flag) {
            encoder[k] = x;
            ++k;
        }
    }
    for (int i = 0; i < 26; ++i)
        decoder[encoder[i] - 'A'] = i + 'A';
    cin >> st;
    for (int i = 0; i < st.length(); ++i)
        st[i] = decoder[st[i] - 'A'];
    cout << st;
    return 0;
}

1）判斷：輸入的字符串應當只由大寫字母組成，否則在訪問數組時可能越界。（ ）

第17題

#include <cstdlib>
#include <iostream>
using namespace std;

char encoder[26] = {'C', 'S', 'P', 0};
char decoder[26];

string st;

int main() {
    int k = 0;
    for (int i = 0; i < 26; ++i)
        if (encoder[i] != 0) ++k;
    for (char x = 'A'; x <= 'Z'; ++x) {
        bool flag = true;
        for (int i = 0; i < 26; ++i)
            if (encoder[i] == x) {
                flag = false;
                break;
            }
        if (flag) {
            encoder[k] = x;
            ++k;
        }
    }
    for (int i = 0; i < 26; ++i)
        decoder[encoder[i] - 'A'] = i + 'A';
    cin >> st;
    for (int i = 0; i < st.length(); ++i)
        st[i] = decoder[st[i] - 'A'];
    cout << st;
    return 0;
}

2）判斷：若輸入的字符串不是空串，則輸入的字符串與輸出的字符串一定不一樣。（ ）

第18題

#include <cstdlib>
#include <iostream>
using namespace std;

char encoder[26] = {'C', 'S', 'P', 0};
char decoder[26];

string st;

int main() {
    int k = 0;
    for (int i = 0; i < 26; ++i)
        if (encoder[i] != 0) ++k;
    for (char x = 'A'; x <= 'Z'; ++x) {
        bool flag = true;
        for (int i = 0; i < 26; ++i)
            if (encoder[i] == x) {
                flag = false;
                break;
            }
        if (flag) {
            encoder[k] = x;
            ++k;
        }
    }
    for (int i = 0; i < 26; ++i)
        decoder[encoder[i] - 'A'] = i + 'A';
    cin >> st;
    for (int i = 0; i < st.length(); ++i)
        st[i] = decoder[st[i] - 'A'];
    cout << st;
    return 0;
}

3）判斷：將第 12 行的“i < 26”改為“i < 16”，程序運行結果不會改變。（ ）

第19題

#include <cstdlib>
#include <iostream>
using namespace std;

char encoder[26] = {'C', 'S', 'P', 0};
char decoder[26];

string st;

int main() {
    int k = 0;
    for (int i = 0; i < 26; ++i)
        if (encoder[i] != 0) ++k;
    for (char x = 'A'; x <= 'Z'; ++x) {
        bool flag = true;
        for (int i = 0; i < 26; ++i)
            if (encoder[i] == x) {
                flag = false;
                break;
            }
        if (flag) {
            encoder[k] = x;
            ++k;
        }
    }
    for (int i = 0; i < 26; ++i)
        decoder[encoder[i] - 'A'] = i + 'A';
    cin >> st;
    for (int i = 0; i < st.length(); ++i)
        st[i] = decoder[st[i] - 'A'];
    cout << st;
    return 0;
}

4）若輸出的字符串為“ABCABCABCA”，則下列說法正確的是（ ）

第20題

#include <cstdlib>
#include <iostream>
using namespace std;

char encoder[26] = {'C', 'S', 'P', 0};
char decoder[26];

string st;

int main() {
    int k = 0;
    for (int i = 0; i < 26; ++i)
        if (encoder[i] != 0) ++k;
    for (char x = 'A'; x <= 'Z'; ++x) {
        bool flag = true;
        for (int i = 0; i < 26; ++i)
            if (encoder[i] == x) {
                flag = false;
                break;
            }
        if (flag) {
            encoder[k] = x;
            ++k;
        }
    }
    for (int i = 0; i < 26; ++i)
        decoder[encoder[i] - 'A'] = i + 'A';
    cin >> st;
    for (int i = 0; i < st.length(); ++i)
        st[i] = decoder[st[i] - 'A'];
    cout << st;
    return 0;
}

5）若輸出的字符串為“CSPCSPCSPCSP”，則下列說法正確的是（ ）

第21題

#include <cstdlib>
#include <iostream>
using namespace std;

char encoder[26] = {'C', 'S', 'P', 0};
char decoder[26];

string st;

int main() {
    int k = 0;
    for (int i = 0; i < 26; ++i)
        if (encoder[i] != 0) ++k;
    for (char x = 'A'; x <= 'Z'; ++x) {
        bool flag = true;
        for (int i = 0; i < 26; ++i)
            if (encoder[i] == x) {
                flag = false;
                break;
            }
        if (flag) {
            encoder[k] = x;
            ++k;
        }
    }
    for (int i = 0; i < 26; ++i)
        decoder[encoder[i] - 'A'] = i + 'A';
    cin >> st;
    for (int i = 0; i < st.length(); ++i)
        st[i] = decoder[st[i] - 'A'];
    cout << st;
    return 0;
}

6）判斷：將第 26 行的“i < 26”改為“i < 16”，程序運行結果不會改變。（ ）

第22題

#include <iostream>
using namespace std;

long long n, ans;
int k, len;
long long d[1000000];

int main() {
    cin >> n >> k;
    d[0] = 0;
    len = 1;
    ans = 0;
    for (long long i = 0; i < n; ++i) {
        ++d[0];
        for (int j = 0; j + 1 < len; ++j) {
            if (d[j] == k) {
                d[j] = 0;
                d[j + 1] += 1;
                ++ans;
            }
        }
        if (d[len - 1] == k) {
            d[len - 1] = 0;
            d[len] = 1;
            ++len;
            ++ans;
        }
    }
    cout << ans << endl;
    return 0;

假設輸入的 n 是不超過2⁶² 的正整數，k 都是不超過 10000 的正整數。

1）判斷：若 k=1，則輸出 ans 時，len = n。（ ）

第23題

#include <iostream>
using namespace std;

long long n, ans;
int k, len;
long long d[1000000];

int main() {
    cin >> n >> k;
    d[0] = 0;
    len = 1;
    ans = 0;
    for (long long i = 0; i < n; ++i) {
        ++d[0];
        for (int j = 0; j + 1 < len; ++j) {
            if (d[j] == k) {
                d[j] = 0;
                d[j + 1] += 1;
                ++ans;
            }
        }
        if (d[len - 1] == k) {
            d[len - 1] = 0;
            d[len] = 1;
            ++len;
            ++ans;
        }
    }
    cout << ans << endl;
    return 0;
     }

假設輸入的 n 是不超過262 的正整數，k 都是不超過 10000 的正整數。

2）判斷：若 k>1，則輸出 ans 時，len 一定小于 n。（ ）

第24題

#include <iostream>
using namespace std;

long long n, ans;
int k, len;
long long d[1000000];

int main() {
    cin >> n >> k;
    d[0] = 0;
    len = 1;
    ans = 0;
    for (long long i = 0; i < n; ++i) {
        ++d[0];
        for (int j = 0; j + 1 < len; ++j) {
            if (d[j] == k) {
                d[j] = 0;
                d[j + 1] += 1;
                ++ans;
            }
        }
        if (d[len - 1] == k) {
            d[len - 1] = 0;
            d[len] = 1;
            ++len;
            ++ans;
        }
    }
    cout << ans << endl;
    return 0;
     }

3）判斷：若 k>1，則輸出 ans 時，klen 一定大于 n。（ ）

第25題

#include <iostream>
using namespace std;

long long n, ans;
int k, len;
long long d[1000000];

int main() {
    cin >> n >> k;
    d[0] = 0;
    len = 1;
    ans = 0;
    for (long long i = 0; i < n; ++i) {
        ++d[0];
        for (int j = 0; j + 1 < len; ++j) {
            if (d[j] == k) {
                d[j] = 0;
                d[j + 1] += 1;
                ++ans;
            }
        }
        if (d[len - 1] == k) {
            d[len - 1] = 0;
            d[len] = 1;
            ++len;
            ++ans;
        }
    }
    cout << ans << endl;
    return 0;
     }

假設輸入的 n 是不超過262 的正整數，k 都是不超過 10000 的正整數。

4）若輸入的 n 等于 1015，輸入的 k 為 1，則輸出等于（ ）。

第26題

#include <iostream>
using namespace std;

long long n, ans;
int k, len;
long long d[1000000];

int main() {
    cin >> n >> k;
    d[0] = 0;
    len = 1;
    ans = 0;
    for (long long i = 0; i < n; ++i) {
        ++d[0];
        for (int j = 0; j + 1 < len; ++j) {
            if (d[j] == k) {
                d[j] = 0;
                d[j + 1] += 1;
                ++ans;
            }
        }
        if (d[len - 1] == k) {
            d[len - 1] = 0;
            d[len] = 1;
            ++len;
            ++ans;
        }
    }
    cout << ans << endl;
    return 0;
     }

假設輸入的 n 是不超過262 的正整數，k 都是不超過 10000 的正整數。

5）若輸入的 n 等于 205,891,132,094,649（即 3^{30}），輸入的 k 為 3，則輸出等于（ ）。

第27題

#include <iostream>
using namespace std;

long long n, ans;
int k, len;
long long d[1000000];

int main() {
    cin >> n >> k;
    d[0] = 0;
    len = 1;
    ans = 0;
    for (long long i = 0; i < n; ++i) {
        ++d[0];
        for (int j = 0; j + 1 < len; ++j) {
            if (d[j] == k) {
                d[j] = 0;
                d[j + 1] += 1;
                ++ans;
            }
        }
        if (d[len - 1] == k) {
            d[len - 1] = 0;
            d[len] = 1;
            ++len;
            ++ans;
        }
    }
    cout << ans << endl;
    return 0;
     }

假設輸入的 n 是不超過262 的正整數，k 都是不超過 10000 的正整數。

6）若輸入的 n 等于 100,010,002,000,090，輸入的 k 等于 10，則輸出等于（ ）。

第28題

#include <algorithm>
#include <iostream>
using namespace std;

int n;
int d[50][2];
int ans;

void dfs(int n, int sum) {
    if (n == 1) {
        ans = max(sum, ans);
        return;
    }
    for (int i = 1; i < n; ++i) {
        int a = d[i - 1][0], b = d[i - 1][1];
        int x = d[i][0], y = d[i][1];
        d[i - 1][0] = a + x;
        d[i - 1][1] = b + y;
        for (int j = i; j < n - 1; ++j)
            d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1];
        int s = a + x + abs(b - y);
        dfs(n - 1, sum + s);
        for (int j = n - 1; j > i; --j)
            d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1];
        d[i - 1][0] = a, d[i - 1][1] = b;
        d[i][0] = x, d[i][1] = y;
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> d[i][0];
    for (int i = 0; i < n; ++i)
        cin >> d[i][1];
    ans = 0;
    dfs(n, 0);
    cout << ans << endl;
    return 0;
}

假設輸入的 n 是不超過 50 的正整數，d[i][0]、d[i][1] 都是不超過 10000 的正整數。

1）判斷：若輸入的 n 為 0，此程序可能會死循環(huán)或發(fā)生運行錯誤。（ ）

第29題

#include <algorithm>
#include <iostream>
using namespace std;

int n;
int d[50][2];
int ans;

void dfs(int n, int sum) {
    if (n == 1) {
        ans = max(sum, ans);
        return;
    }
    for (int i = 1; i < n; ++i) {
        int a = d[i - 1][0], b = d[i - 1][1];
        int x = d[i][0], y = d[i][1];
        d[i - 1][0] = a + x;
        d[i - 1][1] = b + y;
        for (int j = i; j < n - 1; ++j)
            d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1];
        int s = a + x + abs(b - y);
        dfs(n - 1, sum + s);
        for (int j = n - 1; j > i; --j)
            d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1];
        d[i - 1][0] = a, d[i - 1][1] = b;
        d[i][0] = x, d[i][1] = y;
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> d[i][0];
    for (int i = 0; i < n; ++i)
        cin >> d[i][1];
    ans = 0;
    dfs(n, 0);
    cout << ans << endl;
    return 0;
}

假設輸入的 n 是不超過 50 的正整數，d[i][0]、d[i][1] 都是不超過 10000 的正整數。

2）判斷：若輸入的 n 為 20，接下來的輸入全為 0，則輸出為 0。（ ）

第30題

#include <algorithm>
#include <iostream>
using namespace std;

int n;
int d[50][2];
int ans;

void dfs(int n, int sum) {
    if (n == 1) {
        ans = max(sum, ans);
        return;
    }
    for (int i = 1; i < n; ++i) {
        int a = d[i - 1][0], b = d[i - 1][1];
        int x = d[i][0], y = d[i][1];
        d[i - 1][0] = a + x;
        d[i - 1][1] = b + y;
        for (int j = i; j < n - 1; ++j)
            d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1];
        int s = a + x + abs(b - y);
        dfs(n - 1, sum + s);
        for (int j = n - 1; j > i; --j)
            d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1];
        d[i - 1][0] = a, d[i - 1][1] = b;
        d[i][0] = x, d[i][1] = y;
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> d[i][0];
    for (int i = 0; i < n; ++i)
        cin >> d[i][1];
    ans = 0;
    dfs(n, 0);
    cout << ans << endl;
    return 0;
}

假設輸入的 n 是不超過 50 的正整數，d[i][0]、d[i][1] 都是不超過 10000 的正整數。

3）判斷：輸出的數一定不小于輸入的 d[i][0] 和 d[i][1] 的任意一個。（ ）

第31題

#include <algorithm>
#include <iostream>
using namespace std;

int n;
int d[50][2];
int ans;

void dfs(int n, int sum) {
    if (n == 1) {
        ans = max(sum, ans);
        return;
    }
    for (int i = 1; i < n; ++i) {
        int a = d[i - 1][0], b = d[i - 1][1];
        int x = d[i][0], y = d[i][1];
        d[i - 1][0] = a + x;
        d[i - 1][1] = b + y;
        for (int j = i; j < n - 1; ++j)
            d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1];
        int s = a + x + abs(b - y);
        dfs(n - 1, sum + s);
        for (int j = n - 1; j > i; --j)
            d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1];
        d[i - 1][0] = a, d[i - 1][1] = b;
        d[i][0] = x, d[i][1] = y;
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> d[i][0];
    for (int i = 0; i < n; ++i)
        cin >> d[i][1];
    ans = 0;
    dfs(n, 0);
    cout << ans << endl;
    return 0;
}

假設輸入的 n 是不超過 50 的正整數，d[i][0]、d[i][1] 都是不超過 10000 的正整數。

4）若輸入的 n 為 20，接下來跌輸入是 20 個 9 和 20 個 0，則輸出為（ ）

第32題

#include <algorithm>
#include <iostream>
using namespace std;

int n;
int d[50][2];
int ans;

void dfs(int n, int sum) {
    if (n == 1) {
        ans = max(sum, ans);
        return;
    }
    for (int i = 1; i < n; ++i) {
        int a = d[i - 1][0], b = d[i - 1][1];
        int x = d[i][0], y = d[i][1];
        d[i - 1][0] = a + x;
        d[i - 1][1] = b + y;
        for (int j = i; j < n - 1; ++j)
            d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1];
        int s = a + x + abs(b - y);
        dfs(n - 1, sum + s);
        for (int j = n - 1; j > i; --j)
            d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1];
        d[i - 1][0] = a, d[i - 1][1] = b;
        d[i][0] = x, d[i][1] = y;
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> d[i][0];
    for (int i = 0; i < n; ++i)
        cin >> d[i][1];
    ans = 0;
    dfs(n, 0);
    cout << ans << endl;
    return 0;
}

假設輸入的 n 是不超過 50 的正整數，d[i][0]、d[i][1] 都是不超過 10000 的正整數。

5）若輸入的 n 為 30，接下來的輸入是 30 個 0 和 30 個 5，則輸出為（ ）。

第33題

#include <algorithm>
#include <iostream>
using namespace std;

int n;
int d[50][2];
int ans;

void dfs(int n, int sum) {
    if (n == 1) {
        ans = max(sum, ans);
        return;
    }
    for (int i = 1; i < n; ++i) {
        int a = d[i - 1][0], b = d[i - 1][1];
        int x = d[i][0], y = d[i][1];
        d[i - 1][0] = a + x;
        d[i - 1][1] = b + y;
        for (int j = i; j < n - 1; ++j)
            d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1];
        int s = a + x + abs(b - y);
        dfs(n - 1, sum + s);
        for (int j = n - 1; j > i; --j)
            d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1];
        d[i - 1][0] = a, d[i - 1][1] = b;
        d[i][0] = x, d[i][1] = y;
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> d[i][0];
    for (int i = 0; i < n; ++i)
        cin >> d[i][1];
    ans = 0;
    dfs(n, 0);
    cout << ans << endl;
    return 0;
}

假設輸入的 n 是不超過 50 的正整數，d[i][0]、d[i][1] 都是不超過 10000 的正整數。

6）若輸入的 n 為 15，接下來輸入是 15 到 1，以及 15 到 1，則輸出為（ ）。

第34題

（質因數分解）給出正整數 n，請輸出將 n 質因數分解的結果，結果從小到大輸出。

例如：輸入n=120，程序應該輸出 2 2 2 3 5，表示 120=2×2×2×3×5。輸入保證 2≤n≤10⁹。提示：先從小到大枚舉變量 i，然后用 i 不停試除 n 來尋找所有的質因子。

試補全程序。

#include <cstdio>
using namespace std;

int n, i;

int main() {
    scanf("%d", &n);
    for (i = ①; ② <= n; i ++) {
        ③ {
            printf("%d ", i);
            n = n / i;
        }
    }
    if (④) {
        printf("%d ", ⑤);
    }
    return 0;
}

① 處應填（ ）

第35題

（質因數分解）給出正整數 n，請輸出將 n 質因數分解的結果，結果從小到大輸出。

例如：輸入n=120，程序應該輸出 2 2 2 3 5，表示 120=2×2×2×3×5。輸入保證 2≤n≤109。提示：先從小到大枚舉變量 i，然后用 i 不停試除 n 來尋找所有的質因子。

試補全程序。

#include <cstdio>
using namespace std;

int n, i;

int main() {
    scanf("%d", &n);
    for (i = ①; ② <= n; i ++) {
        ③ {
            printf("%d ", i);
            n = n / i;
        }
    }
    if (④) {
        printf("%d ", ⑤);
    }
    return 0;
}

② 處應填（ ）

第36題

（質因數分解）給出正整數 n，請輸出將 n 質因數分解的結果，結果從小到大輸出。

例如：輸入n=120，程序應該輸出 2 2 2 3 5，表示 120=2×2×2×3×5。輸入保證 2≤n≤109。提示：先從小到大枚舉變量 i，然后用 i 不停試除 n 來尋找所有的質因子。

試補全程序。

#include <cstdio>
using namespace std;
int n, i;
int main() {
    scanf("%d", &n);
    for (i = ①; ② <= n; i ++) {
        ③ {
            printf("%d ", i);
            n = n / i;
        }
    }
    if (④) {
        printf("%d ", ⑤);
    }
    return 0;
}

③ 處應填（ ）

第37題

（質因數分解）給出正整數 n，請輸出將 n 質因數分解的結果，結果從小到大輸出。

例如：輸入n=120，程序應該輸出 2 2 2 3 5，表示 120=2×2×2×3×5。輸入保證 2≤n≤109。提示：先從小到大枚舉變量 i，然后用 i 不停試除 n 來尋找所有的質因子。

試補全程序。

#include <cstdio>
using namespace std;

int n, i;

int main() {
    scanf("%d", &n);
    for (i = ①; ② <= n; i ++) {
        ③ {
            printf("%d ", i);
            n = n / i;
        }
    }
    if (④) {
        printf("%d ", ⑤);
    }
    return 0;
}

④ 處應填（ ）

第38題

（質因數分解）給出正整數 n，請輸出將 n 質因數分解的結果，結果從小到大輸出。

例如：輸入n=120，程序應該輸出 2 2 2 3 5，表示 120=2×2×2×3×5。輸入保證 2≤n≤109。提示：先從小到大枚舉變量 i，然后用 i 不停試除 n 來尋找所有的質因子。

試補全程序。

#include <cstdio>
using namespace std;

int n, i;

int main() {
    scanf("%d", &n);
    for (i = ①; ② <= n; i ++) {
        ③ {
            printf("%d ", i);
            n = n / i;
        }
    }
    if (④) {
        printf("%d ", ⑤);
    }
    return 0;
}

⑤處應填（ ）

第39題

（最小區(qū)間覆蓋）給出 n 個區(qū)間，第 i 個區(qū)間的左右端點是[ai,bi]?，F在要在這些區(qū)間中選出若干個，使得區(qū)間 [0,m][0,m] 被所選區(qū)間的并覆蓋（即每一個 0≤i≤m 都在某個所選的區(qū)間中）。保證答案存在，求所選區(qū)間個數的最小值。

輸入第一行包含兩個整數 n 和 m（1≤n≤5000, 1≤m≤10⁹）。

接下來 n 行，每行兩個證書 ai，bi（0≤ai，bi≤m）。

提示：使用貪心法解決這個問題。先用 Θ(n^2) 的時間復雜度排序，然后貪心選擇這些區(qū)間。

試補全程序。

#include <iostream>

using namespace std;

const int MAXN = 5000;
int n, m;
struct segment { int a, b; } A[MAXN];

void sort() // 排序
{
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++)
            if (①)
            {
                segment t = A[j];
                ②
            }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> A[i].a >> A[i].b;
    sort();
    int p = 1;
    for (int i = 1; i < n; i++)
        if (③)
            A[p++] = A[i];
    n = p;
    int ans = 0, r = 0;
    int q = 0;
    while (r < m)
    {
        while (④)
            q++;
        ⑤;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

① 處應填（ ）

第40題

（最小區(qū)間覆蓋）給出 n 個區(qū)間，第 i 個區(qū)間的左右端點是[ai,bi]。現在要在這些區(qū)間中選出若干個，使得區(qū)間 [0,m][0,m] 被所選區(qū)間的并覆蓋（即每一個 0≤i≤m 都在某個所選的區(qū)間中）。保證答案存在，求所選區(qū)間個數的最小值。

輸入第一行包含兩個整數 n 和 m（1≤n≤5000, 1≤m≤109）。

接下來 n 行，每行兩個證書 ai，bi（0≤ai，bi≤m）。

提示：使用貪心法解決這個問題。先用 Θ(n^2) 的時間復雜度排序，然后貪心選擇這些區(qū)間。

試補全程序。

#include <iostream>
using namespace std;
const int MAXN = 5000;
int n, m;
struct segment { int a, b; } A[MAXN];
void sort() // 排序
{
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++)
            if (①)
            {
                segment t = A[j];
                ②
            }
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> A[i].a >> A[i].b;
    sort();
    int p = 1;
    for (int i = 1; i < n; i++)
        if (③)
            A[p++] = A[i];
    n = p;
    int ans = 0, r = 0;
    int q = 0;
    while (r < m)
    {
        while (④)
            q++;
        ⑤;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

② 處應填（ ）

第41題

（最小區(qū)間覆蓋）給出 n 個區(qū)間，第 i 個區(qū)間的左右端點是[ai,bi]。現在要在這些區(qū)間中選出若干個，使得區(qū)間 [0,m][0,m] 被所選區(qū)間的并覆蓋（即每一個 0≤i≤m 都在某個所選的區(qū)間中）。保證答案存在，求所選區(qū)間個數的最小值。

輸入第一行包含兩個整數 n 和 m（1≤n≤5000, 1≤m≤109）。

接下來 n 行，每行兩個證書 ai，bi（0≤ai，bi≤m）。

提示：使用貪心法解決這個問題。先用 Θ(n^2) 的時間復雜度排序，然后貪心選擇這些區(qū)間。

試補全程序。

#include <cstdio>
using namespace std;

int n, i;

int main() {
    scanf("%d", &n);
    for (i = ①; ② <= n; i ++) {
        ③ {
            printf("%d ", i);
            n = n / i;
        }
    }
    if (④) {
        printf("%d ", ⑤);
    }
    return 0;
}

③ 處應填（ ）

第42題

（最小區(qū)間覆蓋）給出 n 個區(qū)間，第 i 個區(qū)間的左右端點是[ai,bi]?，F在要在這些區(qū)間中選出若干個，使得區(qū)間 [0,m][0,m] 被所選區(qū)間的并覆蓋（即每一個 0≤i≤m 都在某個所選的區(qū)間中）。保證答案存在，求所選區(qū)間個數的最小值。

輸入第一行包含兩個整數 n 和 m（1≤n≤5000, 1≤m≤109）。

接下來 n 行，每行兩個證書 ai，bi（0≤ai，bi≤m）。

提示：使用貪心法解決這個問題。先用 Θ(n^2) 的時間復雜度排序，然后貪心選擇這些區(qū)間。

試補全程序。

#include <iostream>

using namespace std;

const int MAXN = 5000;
int n, m;
struct segment { int a, b; } A[MAXN];

void sort() // 排序
{
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++)
            if (①)
            {
                segment t = A[j];
                ②
            }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> A[i].a >> A[i].b;
    sort();
    int p = 1;
    for (int i = 1; i < n; i++)
        if (③)
            A[p++] = A[i];
    n = p;
    int ans = 0, r = 0;
    int q = 0;
    while (r < m)
    {
        while (④)
            q++;
        ⑤;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

④ 處應填（ ）

第43題

（最小區(qū)間覆蓋）給出 n 個區(qū)間，第 i 個區(qū)間的左右端點是[ai,bi]?，F在要在這些區(qū)間中選出若干個，使得區(qū)間 [0,m][0,m] 被所選區(qū)間的并覆蓋（即每一個 0≤i≤m 都在某個所選的區(qū)間中）。保證答案存在，求所選區(qū)間個數的最小值。

輸入第一行包含兩個整數 n 和 m（1≤n≤5000, 1≤m≤109）。

接下來 n 行，每行兩個證書 ai，bi（0≤ai，bi≤m）。

提示：使用貪心法解決這個問題。先用 Θ(n^2) 的時間復雜度排序，然后貪心選擇這些區(qū)間。

試補全程序。

#include <iostream>

using namespace std;

const int MAXN = 5000;
int n, m;
struct segment { int a, b; } A[MAXN];

void sort() // 排序
{
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++)
            if (①)
            {
                segment t = A[j];
                ②
            }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> A[i].a >> A[i].b;
    sort();
    int p = 1;
    for (int i = 1; i < n; i++)
        if (③)
            A[p++] = A[i];
    n = p;
    int ans = 0, r = 0;
    int q = 0;
    while (r < m)
    {
        while (④)
            q++;
        ⑤;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

⑤處應填（ ）