ZeroJudge 解題筆記：a524. 手機之謎

作者：王一哲
日期：2025年7月10日


ZeroJudge 題目連結：a524. 手機之謎

解題想法

這題在 Python 可以用 itertools.permutations，在 C++ 可以用 algorithm 函式庫的 prev_permutation 産生所有的排列，速度很快。也可以用函式遞迴産生所有的排列方式。由於測資有空行，用 Python 解題時要記得跳過空行，否則會吃 RE。

Python 程式碼

寫法1，用 itertools.permutations 産生所有的排列，使用時間約為 0.2 s，記憶體約為 7.5 MB，通過測試。

import sys
from itertools import permutations

result = []
lines = sys.stdin.readlines()
for line in lines:
    if not line.strip(): continue  # 跳過空行
    n = int(line)
    for arr in permutations(range(n, 0, -1), n):  # 從 n ~ 1 的數字取 n 個排列
        res = [f"{a:d}" for a in arr]  # arr 的內容轉成字串存入 res
        result.append("".join(res) + "\n")  # res 接成一個字串加入 result
sys.stdout.write("".join(result))  # 一次輸出所有的結果

寫法2，用函式遞迴窮舉所有的排列，使用時間約為 0.4 s，記憶體約為 7.5 MB，通過測試。

import sys

result = []
def perm(arr, nums, used, depth):
    # 代入已選數字串列 arr, 可用數字串列 nums，已選數字的集合 used，目標長度 depth
    if len(arr) == depth:  # 遞迴出口，如果 arr 長度等於 depth
        result.append("".join([f"{a:d}" for a in arr]) + "\n")  # 接成字串加入 result
        return
    for num in nums:  # 依序由 nums 讀取數字
        if num in used: continue  # 如果 num 已用過，找下一個數字
        arr.append(num)  # num 接到 arr 最後面
        used.add(num)  # num 加入 used
        perm(arr, nums, used, depth)  # 遞迴
        arr.pop()  # 從 arr 最後面移除數字
        used.remove(num)  # 從 used 移除 num

lines = sys.stdin.readlines()
for line in lines:
    if not line.strip(): continue  # 跳過空行
    n = int(line)
    perm([], list(range(n, 0, -1)), set(), n)
sys.stdout.write("".join(result))  # 一次輸出所有的結果

C++ 程式碼

寫法1，用 prev_permutation 産生所有的排列，使用時間約為 11 ms，記憶體約為 308 kB，通過測試。

#include <iostream>
#include <string>
#include <algorithm>  // for prev_permutation
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    while(cin >> n) {
        string s = "";
        for(int i=n; i>0; i--) s += char(i+'0');  // 産生 n ~ 1 的字串
        do {
            cout << s << "\n";  // 先印出一次
        } while(prev_permutation(s.begin(), s.end()));  // 改變排列方式
    }
    return 0;
}

寫法2，用函式遞迴窮舉所有的排列，使用時間約為 35 ms，記憶體約為 340 kB，通過測試。

#include <iostream>
#include <string>
#include <set>
using namespace std;

void perm(string arr, string nums, set<char>& used, int depth) {
    if ((int)arr.size() == depth) {
        cout << arr << "\n";
        return;
    }
    for(char num : nums) {
        if (used.find(num) != used.end()) continue;
        arr += num;
        used.insert(num);
        perm(arr, nums, used, depth);
        arr.pop_back();
        used.erase(num);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    while(cin >> n) {
        string arr = "", nums = "";
        for(int i=n; i>0; i--) nums += char(i+'0');
        set<char> used;
        perm(arr, nums, used, n);
    }
    return 0;
}