HDU 1015 Safecracker：DFS 暴力搜尋字母組合滿足多項式方程

問題重述

給定目標值 target（< 12,000,000）與 5~12 個大寫字母。從中選 5 個不同字母 v,w,x,y,z，按字母序位置（A=1..Z=26）代入：

v - w² + x³ - y⁴ + z⁵ = target

多解時輸出字典序最大者（即字母序最大），無解輸出 no solution。

DFS 剪枝策略

• 字母預先排序，從大到小嘗試，首個找到即為字典序最大解；
• 冪次預計算或快速冪函數；
• 搜索深度固定 5，狀態空間 P(12,5) = 95040，瞬間完成。

完整代碼

#include <bits/stdc++.h>
using namespace std;

int target;
string letters;
int vis[15], pick[5];

int pow_int(int x, int y) { // 返回帶符號值：奇次正、偶次負
    int r = 1;
    for (int i = 0; i < y; ++i) r *= x;
    return (y % 2) ? r : -r;
}

bool dfs(int pos, int sum) {
    if (pos == 5) return sum == target;
    for (int i = (int)letters.size() - 1; i >= 0; --i) {
        if (!vis[i]) {
            vis[i] = 1;
            pick[pos] = letters[i] - 'A' + 1;
            if (dfs(pos + 1, sum + pow_int(pick[pos], pos + 1))) return true;
            vis[i] = 0;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> target >> letters) {
        if (target == 0 && letters == "END") break;
        sort(letters.begin(), letters.end());
        memset(vis, 0, sizeof(vis));
        if (dfs(0, 0)) {
            for (int v : pick) cout << char('A' + v - 1);
            cout << '\n';
        } else {
            cout << "no solution\n";
        }
    }
    return 0;
}

關鍵細節

• pow_int 直接返回帶符號項值，避免在 DFS 中重複判斷正負；
• 字母排序後從大到小枚舉，保證首解即字典序最大；
• 輸入以 0 END 結束，注意讀取方式。