L3-010. 是否完全二叉搜索树

wang 发表于 分类,标签: 天梯赛二叉树
 将一系列给定数字顺序插入一个初始为空的二叉搜索树(定义为左子树键值大,右子树键值小),你需要判断最后的树是否一棵完全二叉树,并且给出其层序遍历的结果。输入格式:输入第一行给出一个不超过20的正整数N;第二行给出N个互不相同的正整数,其间以空格分隔。输出格式:将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果,数字间以1个空格分隔,行的首尾不得有多余空格。第二行输出“YES”,如果该树是完全二叉树;否则输出“NO”。输入样例1:938 45 42 24 58 30 67 12 51输出样例1:38 45 24 58 42 30 12 67 51YES输入样例2:838&nbs...

L3-001. 凑零钱(天梯赛)

wang 发表于 背包问题 分类,标签: 天梯赛
 韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里,发现这家店有个特别的规矩:你可以用任何星球的硬币付钱,但是绝不找零,当然也不能欠债。韩梅梅手边有104枚来自各个星球的硬币,需要请你帮她盘算一下,是否可能精确凑出要付的款额。输入格式:输入第一行给出两个正整数:N(<=104)是硬币的总个数,M(<=102)是韩梅梅要付的款额。第二行给出N枚硬币的正整数面值。数字间以空格分隔。输出格式:在一行中输出硬币的面值V1 <=V2 <=...<=Vk,满足条件V1 +V2 +...+Vk =M。数字间以1个空格分隔,行首尾不得有多余空格。若解不唯一,则输出最小序列。若无解,则输出“NoSolution”。注:我们说序列{A[1],A[2],...}比{B[1],B[2],.....

L2-014. 列车调度

wang 发表于 STL容器 分类,标签: 天梯赛
 火车站的列车调度铁轨的结构如下图所示。Figure两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在图中有9趟列车,在入口处按照{8,4,2,5,3,9,1,6,7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开,则至少需要多少条平行铁轨用于调度?输入格式:输入第一行给出一个整数N(2<=N<=105),下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。输出格式:在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。输入样例:98 4 2 5 3 9 1 6 7输出样例:4思路:要使列车按递减顺序离开,那么列车在平行轨道中也是按...

L2-012. 关于堆的判断

发表于 排序 分类,标签: 天梯赛
 将一系列给定数字顺序插入一个初始为空的小顶堆H[]。随后判断一系列相关命题是否为真。命题分下列几种:“xistheroot”:x是根结点;“xandyaresiblings”:x和y是兄弟结点;“xistheparentofy”:x是y的父结点;“xisachildofy”:x是y的一个子结点。输入格式:每组测试第1行包含2个正整数N(<=1000)和M(<=20),分别是插入元素的个数、以及需要判断的命题数。下一行给出区间[-10000,10000]内的N个要被插入一个初始为空的小顶堆的整数。之后M行,每行给出一个命题。题目保证命题中的结点键值都是存在的。输出格式:对输入的每个命题,如果其为真,则在一行中输出“T”,否则输出“F”。输入样例:5 446 23 26 24 ...

L2-011. 玩转二叉树(天梯赛)

发表于 分类,标签: 天梯赛
 给定一棵二叉树的中序遍历和前序遍历,请你先将树做个镜面反转,再输出反转后的层序遍历的序列。所谓镜面反转,是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。输入格式:输入第一行给出一个正整数N(<=30),是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。输出格式:在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。输入样例:71 2 3 4 5 6 74 1 3 2 6 5 7输出样例:4 6 1 7 5 3 2思路:根据二叉树的前序遍历和中序遍历恢复二叉树后遍历,不过恢复时将左右节点交换一下就行...

L2-010. 排座位(天梯赛)

发表于 并查集 分类,标签: 天梯赛
 布置宴席最微妙的事情,就是给前来参宴的各位宾客安排座位。无论如何,总不能把两个死对头排到同一张宴会桌旁!这个艰巨任务现在就交给你,对任何一对客人,请编写程序告诉主人他们是否能被安排同席。输入格式:输入第一行给出3个正整数:N(<=100),即前来参宴的宾客总人数,则这些人从1到N编号;M为已知两两宾客之间的关系数;K为查询的条数。随后M行,每行给出一对宾客之间的关系,格式为:“宾客1宾客2关系”,其中“关系”为1表示是朋友,-1表示是死对头。注意两个人不可能既是朋友又是敌人。最后K行,每行给出一对需要查询的宾客编号。这里假设朋友的朋友也是朋友。但敌人的敌人并不一定就是朋友,朋友的敌人也不一定是敌人。只有单纯直接的敌对关系才是绝对不能同席的。输出格式:对每个查询输出一行结果:如果两位宾客之间是朋友,且没有敌对关系,则输出“Noproblem”;如果他们之间并不是朋友...

L2-003. 月饼

发表于 背包问题 分类,标签: 天梯赛
  月饼是中国人在中秋佳节时吃的一种传统食品,不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量,请你计算可以获得的最大收益是多少。注意:销售时允许取出一部分库存。样例给出的情形是这样的:假如我们有3种月饼,其库存量分别为18、15、10万吨,总售价分别为75、72、45亿元。如果市场的最大需求量只有20万吨,那么我们最大收益策略应该是卖出全部15万吨第2种月饼、以及5万吨第3种月饼,获得72+45/2=94.5(亿元)。输入格式:每个输入包含1个测试用例。每个测试用例先给出一个不超过1000的正整数N表示月饼的种类数、以及不超过500(以万吨为单位)的正整数D表示市场最大需求量。随后一行给出N个正数表示每种月饼的库存量(以万吨为单位);最后一行给出N个正数表示每种月饼的总售价(以亿元为单位)。数字间以空格分隔。输出格式:对...

L2-002. 链表去重(天梯赛)

发表于 STL容器 分类,标签: 天梯赛
 给定一个带整数键值的单链表L,本题要求你编写程序,删除那些键值的绝对值有重复的结点。即对任意键值K,只有键值或其绝对值等于K的第一个结点可以被保留。同时,所有被删除的结点必须被保存在另外一个链表中。例如:另L为21→-15→-15→-7→15,则你必须输出去重后的链表21→-15→-7、以及被删除的链表-15→15。输入格式:输入第一行包含链表第一个结点的地址、以及结点个数N(<=105 的正整数)。结点地址是一个非负的5位整数,NULL指针用-1表示。随后N行,每行按下列格式给出一个结点的信息:AddressKeyNext其中Address是结点的地址,Key是绝对值不超过104的整数,Next是下一个结点的地址。输出格式:首先输出去重后的链表,然后输出被删除结点组成的链表。每个结点占一行,按输入的格式输出。输入样例:00100 59999...

简介c++ STL的常用方法(转)

发表于 STL容器 分类,标签:
 以下type可以代表intcharfloatdouble或者stringvectorset等等即是数据类型的都可以vector  容器类 头文件<vector>123456789101112131415161718192021222324252627282930313233定义      之间可以进行=  ==  !=  等逻辑运算 如v1==v2  判断两个容器是否相等vector<type>vvector<type>v(v1)    即v=v1vector<type>v(n) &...

stl结构体排序规则重载

发表于 STL容器 分类,标签:
struct node{    int add,key;    bool operator<(const node &r)const{        return key<r.key;    }};bool operator<(const node&a,const node&b){    return a.key<=b.key;} ...