首页 > 代码库 > 【bzoj3227】红黑树

【bzoj3227】红黑树

神TM的红黑树,其实本质上应该还是一种树dp的问题……

一开始想了一个比较裸的树dp,后来发现还有更强的做法。

每个前端黑节点是看作一个物品,然后这就是很典型的树形dp的问题。

不过可以这么考虑,考虑怎么缩小问题的范围。

我们可以把黑色节点的连通块缩成一个点,这样的话就要考虑三个情况:

  1. 直接合并两个相邻的黑色节点
  2. 将三个黑节点合并为一红一黑
  3. 将四个黑节点合并为两红一黑

所以直接贪心就能做。

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
inline int read(){
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch==-)f=-1;}while(ch<0||ch>9);
    do{x=x*10+ch-0;ch=getchar();}while(ch>=0&&ch<=9);
    return f*x;
}
int main(){
    n=read();m=n+1;
    while(m>1){if(m&1)ans++;m>>=1;}
    printf("%d\n",ans);
    m=n+1;ans=0;
    while(m>1){
        if(m==2)ans++;
        if((m&3)==1)ans+=(m>>2)*2-1,m>>=2,m++;
           else if((m&3)==2)ans+=(m>>2)*2,m>>=2,m++;
           else if((m&3)==3)ans+=(m>>2)*2+1,m>>=2,m++;
           else if(!(m&3))ans+=(m>>2)*2,m>>=2;
    }
    printf("%d\n",ans);
}

 

【bzoj3227】红黑树