P1118 [USACO06FEB]数字三角形`Backward Digit Su`…

    • 2.8K通过
    • 7.3K提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 搜索 枚举,暴力 深度优先搜索,DFS USACO 2006
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    FJ and his cows enjoy playing a mental game. They write down the numbers from $1$ to $ N(1 \le N \le 10)$ in a certain order and then sum adjacent numbers to produce a new list with one fewer number. They repeat this until only a single number is left. For example, one instance of the game (when $N=4$ ) might go like this:

        3   1   2   4
          4   3   6
            7   9
             16

    Behind FJ's back, the cows have started playing a more difficult game, in which they try to determine the starting sequence from only the final total and the number $N$ . Unfortunately, the game is a bit above FJ's mental arithmetic capabilities.

    Write a program to help FJ play the game and keep up with the cows.

    有这么一个游戏:

    写出一个 $1$ 至 $N$ 的排列 $a_i$ ,然后每次将相邻两个数相加,构成新的序列,再对新序列进行这样的操作,显然每次构成的序列都比上一次的序列长度少 $1$ ,直到只剩下一个数字位置。下面是一个例子:

    $3,1,2,4$

    $4,3,6$

    $7,9$

    $16$

    最后得到 $16$ 这样一个数字。

    现在想要倒着玩这样一个游戏,如果知道 $N$ ,知道最后得到的数字的大小 $sum$ ,请你求出最初序列 $a_i$ ,为 $1$ 至 $N$ 的一个排列。若答案有多种可能,则输出字典序最小的那一个。

    [color=red]管理员注:本题描述有误,这里字典序指的是 $1,2,3,4,5,6,7,8,9,10,11,12$

    而不是 $1,10,11,12,2,3,4,5,6,7,8,9$ [/color]

    输入输出格式

    输入格式:

    两个正整数 $n,sum$ 。

    输出格式:

    输出包括 $1$ 行,为字典序最小的那个答案。

    当无解的时候,请什么也不输出。(好奇葩啊)

    输入输出样例

    输入样例#1: 复制
    4 16
    输出样例#1: 复制
    3 1 2 4

    说明

    对于 $40\%$ 的数据, $n≤7$ ;

    对于 $80\%$ 的数据, $n≤10$ ;

    对于 $100\%$ 的数据, $n≤12,sum≤12345$ 。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。