TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P6099
  • 题目
  • P6099[Poi2000]代码
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,256m
    问题描述

    一棵二叉树要么为空,要么由一个结点和两棵与其相连的树组成。这两棵树分别称为左子树和右子树。每个结点处有一个英文字母。不包括在任何子树内的结点称为根结点。我们定义二叉搜索树(BST)为:若按字母表中的先后顺序排列,则二叉树的任一个结点均满足,其左子树上的所有字母均在该结点字母之前,而其右子树上所有字母均在该结点字母之后。
    于是,一棵BST的代码为:
    ●如果是一棵空树,则代码中不包括任何字母,即为空串;
    ●如果不是空树,则代码为:根结点上的字母,紧跟着左子树的代码和右子树的代码。
    一棵含k个结点的BST,其代码会有k个小写英文字母,按照字母顺序排列它所有可能的代码,并用(n,k)表示其中的第n条代码。
    例如,一棵有4个结点的BST共有14个不同的代码,按字母顺序列出:abcd 、abdc、 acbd、 adbc、 adcb、 bacd、 badc、 cabd、 cbad、 dabc、 dacb、 dbac、 dcab、 dcba。
    代码(7,4):badc,对应的BST如下图所示。

    任务:
    编写一个程序,完成下列工作:
    ●读入n,k;
    ●找出代码(n,k);
    ●把它写入

    输入格式

    仅一行,包括以空格分开的两个整数n和k(1≤K≤19)。n不超过BST代码的总数。

    输出格式

    仅一行,是以小写字母给出的代码(n,k)

    样例输入

    11 4

    样例输出

    dacb