BZOJ 3227: [Sdoi2008]红黑树(tree)
BZOJ 3227: [Sdoi2008]红黑树(tree)
标签(空格分隔): OI-BZOJ OI-其它
Time Limit: 10 Sec
Memory Limit: 128 MB
Description
红黑树是一类特殊的二叉搜索树,其中每个结点被染成红色或黑色。若将二叉搜索树结点中的空指针看作是指向一个空结点,则称这类空结点为二叉搜索树的前端结点。并规定所有前端结点的高度为-1。
一棵红黑树是满足下面“红黑性质”的染色二叉搜索树:
(1) 每个结点被染成红色或黑色;
(2) 每个前端结点为黑色结点;
(3) 任一红结点的子结点均为黑结点;
(4) 在从任一结点到其子孙前端结点的所有路径上具有相同的黑结点数。
从红黑树中任一结点x出发(不包括结点x),到达一个前端结点的任意一条路径上的黑结点个数称为结点x的黑高度,记作bh(x)。红黑树的黑高度定义为其根结点的黑高度。
给定正整数N,试设计一个算法,计算出在所有含有N个结点的红黑树中,红色内结点个数的最小值和最大值。
Input
输入共一个数N。
Output
输出共两行。
第一行为红色内结点个数的最小值,第二行为最大值。
Sample Input
8
Sample Output
1
4
HINT
对于 100% 的数据,1≤N≤5000
Solution####
可以把所有的前端节点看做初始物品,每次合并2个物品,把一个点看成其子树内的点的并。
算出前端节点的个数。
开始的时候有m个黑节点,为了转换为子问题,我们考虑将黑节点合并为新黑节点。
且原黑节点和新黑节点直接没有其它黑节点,实现问题规模缩小。
因此每个黑节点都要参与“合并”
有3种方案(用花括号表示红节点,中括号表示黑节点):
(1)将2个黑节点合并为1个黑节点
(2)将3个黑节点合并为1个红节点和1个黑节点形如[{[][]}[]]
(3)将4个黑节点合并为2个红节点和1个黑节点形如[{[][]}{[][]}]
所以可以贪心解决此问题
Code####
#include<stdio.h>
using namespace std;
int read()
{int s=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+ch-'0';ch=getchar();}
return s*f;
}
//smile please
int n,m;
int ans;
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n=read();
m=n+1;
ans=0;
while(m>1)
{if(m&1)
ans++;
m/=2;
}
printf("%d\n",ans);
m=n+1;
ans=0;
while(m>1)
{if(m==2)ans++;
if((m&3)==1)
ans+=m/4*2-1,m/=4,m++;
else if((m&3)==2)
ans+=m/4*2,m/=4,m++;
else if((m&3)==3)
ans+=m/4*2+1,m/=4,m++;
else
if(!(m&3))
ans+=m/4*2,m/=4;
}
printf("%d\n",ans);
//fclose(stdin);
//fclose(stdout);
return 0;
}
最新文章
- Delphi_06_Delphi_Object_Pascal_基本语法_04
- 将 xunit.runner.dnx 的 xml 输出转换为 Nunit 格式
- Lessons Learned 1(敏捷项目中的变更影响分析)
- 非智能手机通信录备份并还原至Android智能手机方法
- 自然语言16.1_Python自然语言处理学习笔记之信息提取步骤&;分块(chunking)
- phpcms图片模型调用组图的问题
- Node.js的线程和进程
- JS:操作样式表3:内联和外链样式
- Python使用UUID库生成唯一ID(转)
- jQuery点击div其他地方隐藏div
- cocos2d-x使用ant打包
- python 图片上添加数字源代码
- Myeclipse快捷键的设置
- 符合搜索引擎SEO规则的HTML代码
- Bag标签之中的一个行代码实行中文分词实例1
- 关于Java配置文件properties的学习
- Linux----CentOS-7搭建免流服务器
- zTree的调用设使用(跨两个系统,两类技术实现的项目案例SpringMVC+Spring+MyBatis和Struts2+Spring+ibatis框架组合)
- BigDecimal 准确的 double , float 计算
- openstack之~glance安装部署