ZeroJudge 解題筆記：d643. 勞動的符咒

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


ZeroJudge 題目連結：d643. 勞動的符咒

解題想法

如果輸入的字串 s 長度為 n，先找 n 的所有因數，再用字串切片，將 s 切成因數長度的子字串，將子字串排序後連接成新的字串 t。用集合 spells 儲存新的咒語，如果 t 不在 spells 之中才輸出。

Python 程式碼

使用時間約為 0.1 s，記憶體約為 14.4 MB，通過測試。

s = input().strip()  # 讀取字串
n = len(s)  # 字串長度
factors = {1}  # n 的因數，先放入 1
for i in range(2, int(n**0.5)+1):  # 找 2 ~ sqrt(n)+1 之間的因數
    if n%i == 0:
        factors.add(i)
        factors.add(n//i)
spells = {s}  # 可能的咒語，先放入 s
for factor in sorted(factors):  # 測試由小到大的所有因數
    # 取因數長度的子字串，排序後接成新的字串 t
    t = "".join(sorted([s[i:i+factor] for i in range(0, n, factor)]))
    if t not in spells:  # 如果 t 不在 spells 之中
        spells.add(t)  # t 加入 spells
        print(t)  # 印出 t
if len(spells) == 1: print("bomb!")  # 如果 spells 只有一項，印出 bomb!

C++ 程式碼

使用時間約為 65 ms，記憶體約為 7.5 MB，通過測試。

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s; cin >> s;  // 讀取字串
    int n = (int)s.size();  // 字串長度
    set<int> factors = {1};  // n 的因數，先放入 1
    for(int i=2; i*i <= n; i++) {  // 找 2 ~ sqrt(n)+1 之間的因數
        if (n%i == 0) {
            factors.insert(i);
            factors.insert(n/i);
        }
    }
    set<string> spells = {s};  // 可能的咒語，先放入 s
    for(int factor : factors) {  // 測試由小到大的所有因數
        vector<string> subs;  // 子字串
        for(int i=0; i<n; i+= factor) subs.push_back(s.substr(i, factor));
        sort(subs.begin(), subs.end());
        string t = "";  // 排序後的新字串
        for(string sub : subs) t += sub;
        if (spells.count(t) == 0) {  // 如果 t 不在 spells 之中
            spells.insert(t);  // t 加入 spells
            cout << t << "\n";  // 印出 t
        }
    }
    if (spells.size() == 1) cout << "bomb!\n";  // 如果 spells 只有一項，印出 bomb!
    return 0;
}