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

【bzoj3227】红黑树

2024-09-22 00:22:11   214人阅读

神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】红黑树


联系
我们