這學期接了很多家教，之前給家教學生考試都是使用外部的題目，這次因為前陣子架設 Online Judge，平常的練習題目和作業都改用自架的 Judge，就乾脆當作測試比賽模式，直接出題讓學生去考。

雖然最後遇到很多學校的考試和報告，但也終於舉辦完畢，這裡寫一篇文章做紀錄，包括題目、題解和一些心得。

題目

文字遊戲

題敘

給字串 s 和字串 ss，問能否將字元 1 對 1 mapping，使 s 和 ss 相同。字元範圍可使用 char 儲存。

範圍

字串長度 <= 10^3

解法

將字串 s 的每個字元依照出現順序重新給值，std::map 或是 int index[128] 皆可 AC。

國小數學

題敘

給一個包含 ‘+’, ‘-’, ‘*’, ‘%’, ‘(’, ‘)’ 和數字的運算式，輸出計算結果 % 1e9+7 的結果。

範圍

0 <= 數字範圍 <= 10000，字串長度 <= 10000

解法

case 1 只有 +，單純做字串處理即可

case 2 和 case 3 只差在括號，實際上可以用 stack 去思考，邊計算要邊取模 => AC

排序問題

題敘

給一個字串，可以得到一個字串集為所有該字串的後綴字串組成的，照字典序排序這個字串集的字串並輸出前 k 小的字串。

範圍

字串長度 <= 10000

解法

Trie => 字串長度太長，TLE & MLE

pointer + sort => AC

String.substr + sort => AC，其實我不知道 substr 為什麼這麼快，原本這題是想考 pointer…。

旅行家

題敘

給一張保證連通的無向圖，問從哪個點開始到其他點的距離總合最小，輸出距離總合和到所有點的距離(到自己是0)

範圍

點數 <= 1000

邊數 <= 100000

解法

簡單圖論，用 floyd 可以輕鬆 AC 其他作法不用到 N * E^2 的應該都會過吧XD

交換禮物

題敘

有 n 個人圍成圓圈，報數後第 k 個人離開、第 2k 個人移到第 k 個人的位置，問第 m 個離開的人是誰。

範圍

n <= 10000

解法

這題有開到 linked list 會過的時間，看出是約瑟夫問題後再做一樣的事情即可，要注意的是，其實是砍掉第 2k 個人、把第 2k 個人的編號給第 k 個人，不需要兩個都砍再 insert。

感謝測題的學長，告訴我可以用線段樹解，這題線段樹解法和約瑟夫問題差不多，點維護剩餘人數、logn 找第 k、logn 找 2k 後把 2k 的編號給 k 再讓 2k 的人數減少。時間複雜度 O(n * logn * logn)，有趣的做法

聖誕節採購

題敘

有 n 個正整數，問任選兩個做 xor 的最大值

範圍

數字到 10^9

n <= 10^6

解法

最前面的測資是可以 N^2 解，這題對於沒寫過的人來說應該是防破台題，實際做法可以用 trie 維護 0 和 1 的節點再 greedy 去做，要小心記憶體會爆掉形成 MLE。

除了 trie，位元運算好好做也是可以過，思路和 trie 接近就只是改成一個 ans 變數用 while 維護每個 bit，做 n * 32 次 => AC。

心得

出題好難，產測資好難

水題還是不夠水，學生沒拿到我預期的分數有點難過

結果看下來玩最開心的是學長XDD

謝謝幫我測題的人和幫我生測資的人

採購那題是因為最近各種比賽出很多位元運算的題目，and or 都檢討過，剩下 xor 還沒，剛好也教過 trie，就順便出了

之後再找時間更新 blog，期末考前還在做這種事我還真勇敢