填充題

分数： 200 （部分）

时间限制： 1.0s

内存限制： 64M

作者：

题目类型

和去年不一樣的是，去年的選擇題只能提交一次，而填充題可以交不只一次。
另外，這次可以直接提交文字檔（選擇 Text 為語言），文字檔中請寫入 10 行（如果行數不夠出現 IE 乃正常情形），分別代表每一題的答案。若一題有數個空格請將數個答案以空白分隔。
標粗體字的是專有名詞，很容易可以用網路搜尋的到，故不在題敘中定義。

1.（4 %）簽到題：答案從 1 到 4 的整數猜一個。

2.（10 %）一個 \(n\times n\) 的方格表，起點在左下角 \((0,0)\)，終點在右上角 \((n,n)\)，將 \((0,0)\) 和 \((n,n)\) 連起來稱為對角線。若規定只能沿著格子線從起點向右或向上走到終點，且只能走在對角線上或對角線以下，這樣的總方法數記做卡特蘭數 \(C_n\)。已知 \(C_5=42\)，回答 \(C_{30}=\)？

3.（9 %）依以下順序 \([2,5,3,11,7,4,8,12,9,0,13,15,6,1,14,10]\) 將數字丟入二元搜尋樹內，求後序遍歷（post-order）序列。

4.（9 %）考慮以下題目：給你多組 \((n,m)\)，\(0\leq n,m\leq 2^{31}-1\)，輸入以 \(n=m=0\) 結束，要輸出 \(gcd(n,m)\)。
設某 Choder 給出的錯誤做法如下：
#include <iostream>
int main()
{
    int n, m;
    while (std::cin >> n >> m && (n || m))
    {
        while((n %= m) && (m %= n));
        std::cout << m + n << std::endl;
    }
}
請回答三個值：前兩個值是最小會使程式出錯的 \((n,m)\)（先比較 \(n\) 再比較 \(m\)），第三個值是修正到對的最小編輯距離（edit distance）。

5.（4 %）填空（全部小寫）：NP（_______ _______），是指可以多項式時間確定性做法驗證解的問題。一個著名的問題 _______ ________ problem（TSP），問圖上繞過所有點回到原點的最短路徑，是 NP-_______（NP-C）的，也就是說他是 NP 問題，而且如果這個問題有多項式時間解，那所有 NP 問題都有多項式時間解。
（註：空格 _ 的個數和答案無關，且答案全是小寫英文字母）

6.（5 %）下列哪些問題有 \(O(n)\) 時間複雜度解？（假設對兩個數字加減乘除取模或比較是 \(O(1)\) 的，複雜度和值域有關的算法不計，排序算 \(O(nlogn)\)）請由小到大，以空白分隔，輸出正確的選項：

給兩個已排序數列，合併兩個數列並排序新數列

在一個已排序數列找出第 \(k\) 大的元素

在一個數列找出第 \(k\) 大的元素

支援查詢最小值，移除當前最小值，插入元素（保證插入的元素是當前最大或最小），操作 \(n\) 次

支援查詢最小值，移除當前最小值，插入任意元素，操作 \(n\) 次

支援查詢最小值，移除任意值，插入任意元素，操作 \(n\) 次

7.（15 %）序列 1415926... 是 \(\pi\) 小數點後的位數，把他 \(k\) 個 \(k\) 個一組取出來取 \(10\) 次，得到 \(10\) 個 \(k\) 位數，求總和。
例如：\(k=2\) 時是 \(14+15+92+...=505\)，求 \(k=20\) 時的值。

8.（5 %）學長小莫寫過 C++ 語言教學，在社團中推廣過，希望你還記得怎麼進入他的部落格。另外，黃于軒也有部落格 Nerde Nolzda，希望大家多多督促他發廢文？看完後依序輸出兩個首頁網址通過這題。（請忽略 http:// 等通訊協定，輸出如 xxx.yyy.tld 的網域格式）

9.（39 %）EnglishStar 是社長鐘凡的傑作，然而都沒有人玩，他很傷心。EnglishStar 目前有許多已知 bug（feature），下面有哪些編號是 EnglishStar 的特性？你可以在 judge 首頁看到 EnglishStar 的載點。輸出時要以空白分隔，把編號從小到大排序。(應選7項，已知1是對的)

答對的時候會喵喵叫

選mixed抽題亂數會有約二、三十大小的循環節

會有字被擋住，改大小沒用

會有重複的字

承上，如果重複是在同一輪，打出答案時會一直算到第一個上

每15秒沒有過強制跳轉，但是再送已經過的可以重置

錯誤列表會有自己沒錯的，也會有錯了但沒列到的

如果你想辦法讓他忙碌（如一直按 Enter），計時器會失準

會動來動去的字令人煩躁

存在單字的長度 \(\leq 2\)，還會直接判定通過

10.（100%）這題是加分題，如果你達成以下條件之一，可以拿到這題答案神奇密碼。

第一個抓到出題者的重要錯誤，如官方解答輸入輸出錯誤或不合法（包含填充 P4 找到更優的編輯距離）

寫出能在多項式平方中時限內求出所有正確係數的作法（如此一來你也能生成測資）

AC 掉數字遊戲並給出正確性證明

目前没有评论。