题解 | 数列还原

解题思路

这是一个排列组合问题，需要计算满足特定顺序对数量的排列个数。由于看不清的位置不超过10个，可以使用DFS暴力枚举所有可能的排列。

关键点：

识别未知位置（值为0的位置）
找出所有未使用的数字
计算顺序对的数量
使用DFS枚举所有可能的排列

算法步骤：

收集所有未使用的数字和未知位置
DFS尝试在未知位置填入未使用的数字
计算每个排列的顺序对数量
统计满足条件的排列数量

代码

cpp
java
python

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

class Solution {
private:
    vector<int> arr;
    vector<int> unused;
    vector<int> positions;
    int n, k, count = 0;
    
    int countInversions() {
        int inversions = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (arr[i] < arr[j]) {
                    inversions++;
                }
            }
        }
        return inversions;
    }
    
    void dfs(int pos) {
        if (pos == positions.size()) {
            if (countInversions() == k) {
                count++;
            }
            return;
        }
        
        for (int i = 0; i < unused.size(); i++) {
            arr[positions[pos]] = unused[i];
            swap(unused[i], unused.back());
            unused.pop_back();
            
            dfs(pos + 1);
            
            unused.push_back(arr[positions[pos]]);
            swap(unused[i], unused[unused.size() - 1]);
        }
    }
    
public:
    int solve(int N, int K, vector<int>& A) {
        n = N;
        k = K;
        arr = A;
        
        // 收集未使用的数字和未知位置
        vector<bool> used(n + 1, false);
        for (int i = 0; i < n; i++) {
            if (arr[i] != 0) {
                used[arr[i]] = true;
            } else {
                positions.push_back(i);
            }
        }
        
        for (int i = 1; i <= n; i++) {
            if (!used[i]) {
                unused.push_back(i);
            }
        }
        
        dfs(0);
        return count;
    }
};

int main() {
    int n, k;
    cin >> n >> k;
    
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    Solution solution;
    cout << solution.solve(n, k, arr) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        private int[] arr;
        private List<Integer> unused;
        private List<Integer> positions;
        private int n, k, count;
        
        private int countInversions() {
            int inversions = 0;
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (arr[i] < arr[j]) {
                        inversions++;
                    }
                }
            }
            return inversions;
        }
        
        private void dfs(int pos) {
            if (pos == positions.size()) {
                if (countInversions() == k) {
                    count++;
                }
                return;
            }
            
            for (int i = 0; i < unused.size(); i++) {
                arr[positions.get(pos)] = unused.get(i);
                Collections.swap(unused, i, unused.size() - 1);
                int last = unused.remove(unused.size() - 1);
                
                dfs(pos + 1);
                
                unused.add(last);
                Collections.swap(unused, i, unused.size() - 1);
            }
        }
        
        public int solve(int N, int K, int[] A) {
            n = N;
            k = K;
            arr = A.clone();
            count = 0;
            unused = new ArrayList<>();
            positions = new ArrayList<>();
            
            boolean[] used = new boolean[n + 1];
            for (int i = 0; i < n; i++) {
                if (arr[i] != 0) {
                    used[arr[i]] = true;
                } else {
                    positions.add(i);
                }
            }
            
            for (int i = 1; i <= n; i++) {
                if (!used[i]) {
                    unused.add(i);
                }
            }
            
            dfs(0);
            return count;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        Solution solution = new Solution();
        System.out.println(solution.solve(n, k, arr));
        
        sc.close();
    }
}

class Solution:
    def __init__(self):
        self.arr = []
        self.unused = []
        self.positions = []
        self.n = 0
        self.k = 0
        self.count = 0
    
    def count_inversions(self):
        inversions = 0
        for i in range(self.n):
            for j in range(i + 1, self.n):
                if self.arr[i] < self.arr[j]:
                    inversions += 1
        return inversions
    
    def dfs(self, pos):
        if pos == len(self.positions):
            if self.count_inversions() == self.k:
                self.count += 1
            return
        
        for i in range(len(self.unused)):
            self.arr[self.positions[pos]] = self.unused[i]
            last = self.unused.pop(i)
            
            self.dfs(pos + 1)
            
            self.unused.insert(i, last)
    
    def solve(self, n: int, k: int, arr: list) -> int:
        self.n = n
        self.k = k
        self.arr = arr.copy()
        self.count = 0
        
        # 收集未使用的数字和未知位置
        used = [False] * (n + 1)
        self.positions = []
        
        for i in range(n):
            if arr[i] != 0:
                used[arr[i]] = True
            else:
                self.positions.append(i)
        
        self.unused = [i for i in range(1, n + 1) if not used[i]]
        
        self.dfs(0)
        return self.count

# 读取输入
n, k = map(int, input().split())
arr = list(map(int, input().split()))

solution = Solution()
print(solution.solve(n, k, arr))

算法及复杂度

算法：DFS + 回溯
时间复杂度： $O(P! \times n^2)$ ，其中 $P$ 是未知位置的数量（≤10）， $n$ 是序列长度
空间复杂度： $O(n)$ ，需要存储序列和未使用的数字