填充題

View as PDF

Submit solution


Points: 200 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

和去年不一樣的是,去年的選擇題只能提交一次,而填充題可以交不只一次。
另外,這次可以直接提交文字檔(選擇 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)\))請由小到大,以空白分隔,輸出正確的選項:

  1. 給兩個已排序數列,合併兩個數列並排序新數列
  2. 在一個已排序數列找出第 \(k\) 大的元素
  3. 在一個數列找出第 \(k\) 大的元素
  4. 支援查詢最小值,移除當前最小值,插入元素(保證插入的元素是當前最大或最小),操作 \(n\) 次
  5. 支援查詢最小值,移除當前最小值,插入任意元素,操作 \(n\) 次
  6. 支援查詢最小值,移除任意值,插入任意元素,操作 \(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是對的)

  1. 答對的時候會喵喵叫
  2. 選mixed抽題亂數會有約二、三十大小的循環節
  3. 會有字被擋住,改大小沒用
  4. 會有重複的字
  5. 承上,如果重複是在同一輪,打出答案時會一直算到第一個上
  6. 每15秒沒有過強制跳轉,但是再送已經過的可以重置
  7. 錯誤列表會有自己沒錯的,也會有錯了但沒列到的
  8. 如果你想辦法讓他忙碌(如一直按 Enter),計時器會失準
  9. 會動來動去的字令人煩躁
  10. 存在單字的長度 \(\leq 2\),還會直接判定通過

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

  1. 第一個抓到出題者的重要錯誤,如官方解答輸入輸出錯誤或不合法(包含填充 P4 找到更優的編輯距離)
  2. 寫出能在多項式平方中時限內求出所有正確係數的作法(如此一來你也能生成測資)
  3. AC 掉數字遊戲並給出正確性證明

Comments

There are no comments at the moment.