考古学家 - 华为OD统一考试(D卷)

OD统一考试(D卷)

分值： 200分

题解： Java / Python / C++

alt

题目描述

有一个考古学家发现一个石碑，但是很可惜发现时其已经断成多段。

原地发现N个断口整齐的石碑碎片，为了破解石碑内容，考古学家希望有程序能帮忙计算复原后的石碑文字组合数，你能帮忙吗？

备注：如果存在石碑碎片内容完全相同，则由于碎片间的顺序不影响复原后的碑文内容，仅相同碎片间的位置变化不影响组合

输入描述

第一行输入N，N表示石碑碎片的个数

第二行依次输入石碑碎片上的文字内容S共有N组

输出描述

输出石碑文字的组合(按照升序排列)，行尾无多余空格

示例1

输入：
3
a b c

输出：
abc
acb
bac
bca
cab
cba

示例2

输入：
3
a b a

输出：
aab
aba
baa

示例3

输入：
3
a b ab

输出：
aabb
abab
abba
baab
baba

题解

这是一个典型的排列组合问题，可以使用回溯算法来生成所有可能的组合。

代码大致描述：

主函数main中，读取石碑碎片的个数N和每个碎片的文字内容S，并进行排序，以便后续生成有序的排列组合。。

创建一个用于标记是否使用过的数组used和一个用于存储当前组合的容器collect，以及 rs 存储结果的字符串。

调用solve函数进行回溯，生成所有可能的排列组合。

在solve函数中，检查当前组合的长度是否等于石碑碎片的个数N，如果是则拼接成字符串并输出（避免重复输出相同的排列组合）。

递归调用solve函数，尝试不同的组合。

在每次递归调用前，标记当前石碑碎片为已使用，以防止重复使用。

递归调用后，将标记恢复，进行下一轮尝试。

这样，通过回溯算法，可以遍历所有可能的排列组合，最终输出升序排列的石碑文字组合。

Java

import java.util.*;

/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String[] cs = new String[n];
        for (int i = 0; i < n; i++) cs[i] = in.next();
        Arrays.sort(cs);

        Solution solution = new Solution(cs, n);
        solution.solve(new ArrayList<>());

        for (String result : solution.rs) {
            System.out.println(result);
        }
    }
}


class Solution {

    private final String[] cs;
    private final int n;
    private boolean[] used;
    public Set<String> rs;

    public Solution(String[] cs, int n) {
        this.cs = cs;
        this.n = n;
        this.used = new boolean[n];
        this.rs = new TreeSet<>();
    }

    public void solve(List<String> collect) {
        if (collect.size() == n) {
            rs.add(String.join("", collect));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (used[i]) continue;

            used[i] = true;
            collect.add(cs[i]);
            solve(collect);
            collect.remove(collect.size() - 1);
            used[i] = false;
        }
    }
}

Python

n = int(input())
ss = input().split()
ss.sort()

used, collect, rs = [False] * n, [], set()


def solve():
    global used, collect, rs, n, ss
    if len(collect) == n:   # 组合完成
        rs.add("".join(collect))
        return

    pre = None
    for i in range(n):
        if used[i]:  # 元素被使用
            continue

        used[i] = True
        collect.append(ss[i])
        solve()

        collect.pop()
        used[i] = False
        pre = ss[i]


solve()
print(*sorted(list(rs)), sep='\n')

C++

#include <algorithm>
#include <iostream>
#include <numeric>
#include <set>
#include <vector>


using namespace std;

int         n;
set<string> rs;

void solve(const vector<string>& cs, vector<bool>& used, vector<string>& collect)
{
    if (collect.size() == n) {
        string result = accumulate(collect.begin(), collect.end(), string(""));
        rs.insert(result);
        return;
    }

    for (int i = 0; i < n; i++) {
        if (used[i]) continue;

        used[i] = true;
        collect.push_back(cs[i]);
        solve(cs, used, collect);
        collect.pop_back();
        used[i] = false;
    }
}

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

    vector<bool>   used(n, false);
    vector<string> collect;

    solve(cs, used, collect);

    vector<string> result(rs.begin(), rs.end());
    sort(result.begin(), result.end());

    for (const string& s : result) {
        cout << s << endl;
    }

    return 0;
}