p1118

问题分析

题目要求找出字典序最小的 1 到 N 的排列，使得通过相邻数字相加直到只剩一个数的过程，最终结果等于给定的 sum。若无解，则不输出任何内容。

关键观察：最终的总和等于初始序列中每个数字乘以一个特定系数的和。这些系数是二项式系数，具体为组合数 C(n-1, i)，其中 i 为数字在序列中的位置（0-indexed）。例如，当 n=4 时，系数为 [1, 3, 3, 1]。

解法思路

1. 预处理组合数：计算 0 到 11 行的二项式系数（因为 N ≤ 12）。
2. 构建系数数组：根据输入的 n，生成长度为 n 的系数数组，其中第 i 个元素为 C(n-1, i)。
3. 预处理后缀系数：对于每个起始位置 pos，预先计算从 pos 到 n-1 的系数并降序排序，用于后续剪枝。
4. 深度优先搜索 (DFS)：
   • 状态：当前放置的位置 pos，当前累加和 current_sum。
   • 剪枝：在每一步，计算剩余位置的最小和最大可能贡献：
     • 最小贡献：将剩余数字升序排列，与降序排列的剩余系数相乘求和。
     • 最大贡献：将剩余数字降序排列，与降序排列的剩余系数相乘求和。
     • 若 current_sum + 最小贡献 > sum 或 current_sum + 最大贡献 < sum，则剪枝。
   • 字典序：按数字从小到大的顺序尝试放置，确保找到的第一个解为字典序最小。
   • 终止条件：当放置完所有数字（pos == n）且 current_sum 等于 sum 时，输出序列并退出程序。
5. 无解处理：若 DFS 结束未找到解，程序自然结束，无输出。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;

int n, total_sum;
vector<int> coeff;
vector<vector<int>> suffix_coeffs;

vector<int> ans;
vector<bool> used;

bool dfs(int pos, long long current_sum) {
    if (pos == n) {
        if (current_sum == total_sum) {
            for (int i = 0; i < n; i++) {
                cout << ans[i];
                if (i < n-1) cout << " ";
            }
            cout << endl;
            exit(0);
        }
        return false;
    }

    vector<int> rem_nums;
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            rem_nums.push_back(i);
        }
    }

    vector<int>& rem_coeffs = suffix_coeffs[pos];
    int cnt = rem_nums.size();

    sort(rem_nums.begin(), rem_nums.end());
    long long min_rem = 0;
    for (int i = 0; i < cnt; i++) {
        min_rem += (long long)rem_nums[i] * rem_coeffs[i];
    }

    sort(rem_nums.rbegin(), rem_nums.rend());
    long long max_rem = 0;
    for (int i = 0; i < cnt; i++) {
        max_rem += (long long)rem_nums[i] * rem_coeffs[i];
    }

    if (current_sum + min_rem > total_sum || current_sum + max_rem < total_sum) {
        return false;
    }

    for (int num = 1; num <= n; num++) {
        if (used[num]) continue;
        used[num] = true;
        ans[pos] = num;
        long long new_sum = current_sum + (long long)num * coeff[pos];
        if (dfs(pos + 1, new_sum)) {
            return true;
        }
        used[num] = false;
    }
    return false;
}

int main() {
    cin >> n >> total_sum;

    vector<vector<int>> C_table(12, vector<int>(12, 0));
    for (int i = 0; i < 12; i++) {
        C_table[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C_table[i][j] = C_table[i-1][j-1] + C_table[i-1][j];
        }
    }

    coeff.resize(n);
    for (int i = 0; i < n; i++) {
        coeff[i] = C_table[n-1][i];
    }

    suffix_coeffs.resize(n);
    for (int i = 0; i < n; i++) {
        vector<int> tmp;
        for (int j = i; j < n; j++) {
            tmp.push_back(coeff[j]);
        }
        sort(tmp.rbegin(), tmp.rend());
        suffix_coeffs[i] = tmp;
    }

    ans.resize(n);
    used.assign(n+1, false);

    dfs(0, 0);

    return 0;
}

DFS 搜索：

• 剪枝：计算剩余数字的最小和最大可能贡献，若当前和加上最小贡献超过 total_sum 或加上最大贡献仍不足 total_sum，则剪枝。

• 字典序保证：按数字 1 到 n 的顺序尝试放置，确保找到的第一个解字典序最小。

• 终止与输出：当放置完所有数字且和等于 total_sum 时，输出序列并退出程序。

复杂度分析

时间复杂度

• 最坏情况：
  在没有剪枝的情况下，需要遍历所有 种排列。当 时，，理论上可能超时。

• 实际运行（含剪枝）：远低于

空间复杂度

• 显式存储：
  • 组合数表：（固定大小）
  • 系数数组：
  • 后缀系数表：（ 时最大 78 个整数）
  • DFS 栈深度：
• 总空间：
  时，总内存占用 KB，可视为常数空间。