Luxin's Blog

Code & Life

势均力敌

发表于 更新于 分类于

题目描述

用 n>2 个不同的个位数字组成一个 n 位数，显然有 n! 个不同的结果。可以证明，这 n! 个数字可以被分为势均力敌的两组 —— 即平方和相等、且个数也相等的两组。

本题就请你用程序验证一下这个结论。因为本题是一道简单题，所以规模很小，只考虑 n≤4 的情况。

输入格式

输入第一行给出正整数 n（2<n≤4），随后一行给出 n 个不同的、在区间 [1, 9] 内的个位数字，其间以空格分隔。

输出格式

将所有组成的 n! 个不同的 n 位数分为平方和相等、且个数也相等的两组。但你只需要输出其中一组就可以了。每个数字占一行，共输出 n!/2 行。

注意：解可能不唯一，输出任何一组解就可以。

输入样例

1
2
3
5 2 1

输出样例

1
2
3
125
512
251

解题思路

这道题的核心是生成所有可能的排列，然后找到平方和相等的两组。

算法步骤

  1. 生成全排列：使用回溯算法生成所有 n! 个不同的 n 位数
  2. 计算平方和：对于每个数字，计算其各位数字的平方和
  3. 回溯搜索：找到平方和相等的两组数字，且每组个数为 n!/2

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n);
    for(ll i = 0; i < n; i++){
        cin >> a[i];
    }

    // vis 数组：标记是否使用过
    vector<bool> vis(n, false);
    // 结果数组
    vector<ll> res;

    // 回溯
    function<void(ll, ll, vector<bool>)> dfs = [&](ll sum, ll pos,vector<bool> vis) {
        // 如果已经处理完所有元素，保存结果
        if(pos == n){
            res.push_back(sum);
            return;
        }
        // 选择元素
        for(ll i = 0 ;i < n; i++){
            if(!vis[i]){
                vis[i] = true; // 标记为已使用
                dfs(sum * 10 + a[i], pos + 1, vis); // 递归处理下一个元素
                vis[i] = false; // 回退，标记为未使用
            }
        }
    };
    dfs(0, 0, vis);

    // 计算所有结果的平方和
    ll all = 0;
    for(ll i = 0; i < res.size(); i++){
        all += res[i] * res[i];
    }
    all /= 2;
    
    //  答案
    vector<ll>path;
    // find 标记是否找到结果
    bool find = false;
    vector<bool> vis1(res.size(), false);

    function<void(ll, ll, vector<bool>, ll)> dfs1 = [&](ll sum, ll pos,vector<bool> vis1, ll start) {
        // 如果已经找到结果，直接返回
        if(find) return;
        // 如果当前和等于目标值，标记找到结果并返回
        if (sum == all) {
            find = true;
            return;
        }
        if(sum > all){
            return;
        }
        if(pos == res.size() / 2){
            return;
        }
        for(ll i = start; i < res.size(); i++){
            if(!vis1[i]){
                vis1[i] = true;
                path.push_back(res[i]);
                dfs1(sum + res[i] * res[i], pos + 1, vis1, i + 1);
                if(find) return;
                path.pop_back();
                vis1[i] = false;
            }
        }
    };
    dfs1(0, 0, vis1, 0);
    // 输出结果
    for(ll i = 0; i < path.size(); i++){
        cout << path[i] << "\n";
    }
    return 0;
}

总结

通过回溯算法生成所有可能的排列，然后计算平方和，最后使用回溯搜索找到平方和相等的两组数字。这道题的关键是理解如何将问题分解为子问题，以及如何使用回溯算法高效地搜索解空间。