https://www.luogu.com.cn/problem/P1118

P1118 [USACO06FEB] Backward Digit Sums G/S

题目描述

FJ 和他的奶牛们喜欢玩一个心算游戏。他们将数字从 到 按某种顺序写下来，然后将相邻的数字相加，得到一个数字更少的新列表。他们重复这个过程，直到只剩下一个数字。例如，游戏的一种情况（当 时）可能是这样的：

    3   1   2   4
      4   3   6
        7   9
         16

在 FJ 背后，奶牛们开始玩一个更难的游戏，她们试图从最终的总和和数字 中确定起始序列。不幸的是，这个游戏有点超出了 FJ 的心算能力。

编写一个程序来帮助 FJ 玩这个游戏，并跟上奶牛们的步伐。

输入格式

共一行两个正整数 。

输出格式

输出包括一行，为字典序最小的那个答案。

当无解的时候，请什么也不输出。

输入输出样例 #1

输入 #1

4 16

输出 #1

3 1 2 4

说明/提示

• 对于 的数据，；
• 对于 的数据，；
• 对于 的数据，，。 （由 ChatGPT 4o 翻译）

代码：

import sys

def main():
    data = sys.stdin.readline().split()
    if not data:
        return
    n = int(data[0])
    target = int(data[1])
    
    if n == 1:
        if target == 1:
            print(1)
        return
    
    def comb(n_val, k_val):
        if k_val < 0 or k_val > n_val:
            return 0
        res = 1
        for i in range(1, k_val + 1):
            res = res * (n_val - i + 1) // i
        return res
    
    coeffs = [comb(n - 1, i) for i in range(n)]
    used = [False] * (n + 1)
    path = []
    
    def dfs(pos, current):
        if pos == n:
            if current == target:
                print(" ".join(map(str, path)))
                return True
            return False
        
        if current > target:
            return False
        
        unused = []
        for num in range(1, n + 1):
            if not used[num]:
                unused.append(num)
                
        rest_coeffs = coeffs[pos:]
        len_rest = len(rest_coeffs)
        sorted_coeffs = sorted(rest_coeffs, reverse=True)
        sorted_asc = sorted(unused)
        sorted_desc = sorted(unused, reverse=True)
        
        min_rest = 0
        max_rest = 0
        for idx in range(len_rest):
            min_rest += sorted_coeffs[idx] * sorted_asc[idx]
            max_rest += sorted_coeffs[idx] * sorted_desc[idx]
            
        if current + min_rest > target or current + max_rest < target:
            return False
            
        for num in sorted_asc:
            if not used[num]:
                used[num] = True
                path.append(num)
                new_current = current + coeffs[pos] * num
                if dfs(pos + 1, new_current):
                    return True
                path.pop()
                used[num] = False
                
        return False
        
    dfs(0, 0)

if __name__ == "__main__":
    main()

题解：

特殊情况处理：若 N=1，直接检查 sum是否为 1。

组合数计算：使用函数 comb计算二项式系数 C(N−1,i)作为权重系数。

DFS 搜索： 参数：当前位置 pos，当前加权和 current。 终止条件：位置满时检查是否匹配目标。 剪枝：当前和超目标或剩余和范围不包含目标时剪枝。 递归尝试：按升序尝试未用数字，更新当前和，递归下一位置。