Bzoj3227 [Sdoi2008]红黑树(tree)
2024-10-21 05:40:11
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 204 Solved: 125
Description
红黑树是一类特殊的二叉搜索树，其中每个结点被染成红色或黑色。若将二叉搜索树结点中的空指针看作是指向一个空结点，则称这类空结点为二叉搜索树的前端结点。并规定所有前端结点的高度为-1。
一棵红黑树是满足下面“红黑性质”的染色二叉搜索树：
(1) 每个结点被染成红色或黑色；
(2) 每个前端结点为黑色结点；
(3) 任一红结点的子结点均为黑结点；
(4) 在从任一结点到其子孙前端结点的所有路径上具有相同的黑结点数。
从红黑树中任一结点x出发(不包括结点x)，到达一个前端结点的任意一条路径上的黑结点个数称为结点x的黑高度，记作bh(x)。红黑树的黑高度定义为其根结点的黑高度。
给定正整数N，试设计一个算法，计算出在所有含有N个结点的红黑树中，红色内结点个数的最小值和最大值。
Input
输入共一个数N。
Output
输出共两行。
第一行为红色内结点个数的最小值，第二行为最大值。
Sample Input
8
Sample Output
1
4
4
HINT
对于 100% 的数据，1≤N≤5000
Source
名叫红黑树的DP题……
让我想起了之前的名叫最大流的树剖题2333
动规/贪心
脑补了一阵子，觉得是树规或者区间DP，然而都好麻烦
这时旁边神奇的licone说可以贪心 http://blog.csdn.net/senyelicone/article/details/59058778
-----
如果树形DP的话，设f[非前端结点数][黑高度][当前结点是红色/黑色]=最大/最小红结点数
如果区间DP的话，设f[左端点][右端点][当前结点状态]=最大/最小红结点数 ←只是一个想法，目测就算正确也T得飞起
-----
/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
int main(){
int i,j,n,m;
scanf("%d",&n);
m=n+;
int ans=;
while(m>){
if(m&)ans++;
m>>=;
}
printf("%d\n",ans);//mini
m=n+;
ans=;
while(m>){
if(m==)ans++;
if(m&){
if((m&)==){
ans+=m/*-;
m/=;m++;
}
else if((m&)==){
ans+=m/*;
m/=;m++;
}
else if((m&)==){
ans+=m/*+;
m/=;m++;
}
}
else{
ans+=m/*;
m/=;
}
}
printf("%d\n",ans);//max
return ;
}
最新文章
- Git简易的命令行入门教程
- python批量GBK转UTF-8
- ActiveMQ(5.10.0) - Spring Support
- 如何调试什么时候SaveFileDialog会被Dispose
- C51汇编语言完整源码
- android怎样写一个循环文字滚动的TextView
- Linux学习之traceroute命令
- jxl读写excel, poi读写excel,word, 读取Excel数据到MySQL
- apache .htaccess文件详解和配置技巧总结
- syntaxhighlighter的使用
- 利用工具MailUtils实现邮件的发送,遇到的大坑,高能预警!!
- dedecms文章页调用上一篇和下一篇文章
- R学习笔记：了解R的使用
- HtmlUnit入门一
- PCIE错误分析
- Codeforces Round #419 Div. 1
- BZOJ4695 最假女选手（势能线段树）
- 深挖android low memory killer
- 解决VMware虚拟机的CentOS无法上网
- POJ1995:Raising Modulo Numbers(快速幂取余）