【bzoj3227】红黑树

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

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

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

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

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

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

所以直接贪心就能做。

#include<bits/stdc++.h>

using namespace std;

int n,m,ans;

inline int read(){

    int f=,x=;char ch;

    do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');

    do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');

    return f*x;

}

int main(){

    n=read();m=n+;

    while(m>){if(m&)ans++;m>>=;}

    printf("%d\n",ans);

    m=n+;ans=;

    while(m>){

        if(m==)ans++;

        if((m&)==)ans+=(m>>)*-,m>>=,m++;

           else if((m&)==)ans+=(m>>)*,m>>=,m++;

           else if((m&)==)ans+=(m>>)*+,m>>=,m++;

           else if(!(m&))ans+=(m>>)*,m>>=;

    }

    printf("%d\n",ans);

}

巴特西

【bzoj3227】红黑树

最新文章

热门文章