演算法中階・數學與位元運算
最大公因數決定分批大小、質數篩回答區間查詢、位元遮罩表示集合找不相交的配對。
這一頁是題幹試閱;登入/註冊後每題可以在瀏覽器裡執行、對答案,第一次交對 +10 XP。
- 01
依分區鍵等量分批
中等數學一批事件要切成好幾個小批次送出,規則是:每個小批次的筆數都相同(至少 2 筆),而且同一個小批次裡的事件分區鍵都一樣。每筆事件都要分進某個小批次。請判斷能不能這樣切;能的話,列出所有可行的批次大小,並印出用最大批次大小時一共有幾批。
輸入:
第 1 行:組數 t
接下來 t 行:每行一組事件的分區鍵(以空白分隔,至少一筆)
輸出:每組一行
- 不能切:印
NO - 能切:印
MAX 最大批次大小 BATCHES 批數 SIZES 所有可行大小(可行大小由小到大,以空白分隔)
要求:可行的批次大小 g 必須整除每個分區鍵的筆數,所以先算所有筆數的最大公因數,再從它推出答案。
範例輸入:
2
u1 u2 u2 u1
u1 u1 u2
範例輸出:
MAX 2 BATCHES 2 SIZES 2
NO
類型對應:LeetCode「X of a Kind in a Deck of Cards」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 不能切:印
- 02
雜湊分區數挑質數
中等數學把資料雜湊分到 n 個分區時,分區數取質數比較不容易因為鍵的規律而分得不平均。規劃人員會問很多個上限值:不超過這個值的質數有幾個、最大的是哪一個。
輸入:一行,若干個查詢值(非負整數,以空白分隔,最大 200000)
輸出:每個查詢一行
查詢值 質數個數 最大質數(不超過查詢值的質數;沒有質數時最大質數印-)。要求:用埃拉托斯特尼篩法(Sieve of Eratosthenes)一次篩到所有查詢的最大值,再用前綴的方式回答每個查詢;不要對每個查詢逐一試除。
範例輸入:
5 20
範例輸出:
5 3 5
20 8 19
類型對應:LeetCode「Count Primes」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 03
不共用資料表的工作配對
中等位元運算每個批次工作會鎖住幾張共用資料表,資料表以小寫字母 a 到 t 代表(共 20 張)。兩個工作鎖的資料表完全沒有重疊時才能同時跑。排程器想找出一對可以同時跑、而且執行時間加總最長的工作。
用位元遮罩表示集合:資料表 a 是第 0 個位元、b 是第 1 個位元……,一個工作鎖的資料表集合就是一個整數,例如
abd是 1 + 2 + 8 = 11。兩個集合沒有交集,等價於兩個遮罩做&的結果是 0。輸入:
第 1 行:組數 t
每組:第 1 行是工作數 n,接下來 n 行是
工作名稱 執行時間 資料表字母(不鎖任何資料表時寫-,同一個字母不會重複)輸出:每組
- 先依輸入順序,每個工作一行
工作名稱 遮罩值 - 最後一行:
BEST 時間加總 工作A 工作B;加總相同時取工作A在輸入中較前面的,再相同取工作B較前面的(工作A一定排在工作B之前)。沒有任何一對能同時跑時印NONE
要求:先把每個工作轉成遮罩整數,配對時只用
&判斷,不要用 set 交集。範例輸入:
1
3
load 20 ab
clean 15 c
index 30 bt
範例輸出:
load 3
clean 4
index 524290
BEST 45 clean index
類型對應:LeetCode「Maximum Product of Word Lengths」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 先依輸入順序,每個工作一行

送件鴿飛出去了