P5566 [SDOI2008]红黑树 题解

· · 题解

可以通过列出n在较小(如n<14)时的min和max，可以发现min和max的规律

n=1,min=0,max=1 n=2,min=1,max=1 n=3,min=0,max=2 n=4,min=1,max=2 n=5,min=1,max=3 n=6,min=2,max=4 n=7,min=0,max=5 n=8,min=1,max=4 n=9,min=1,max=5 n=10,min=2,max=6 n=11,min=1,max=7 n=12,min=2,max=7 n=13,min=2,max=8 n=14,min=3,max=9

min的规律很好找，可以注意到n=1和n=2时min值即为n=3和n=4时min值，而n=5和n=6时min值则分别为n=1时min值+1和n=2时min值+1。所以将其按2/4/8/……/2^k划分。每一段的前一半就是上一段，后一半则是上一段+1。

但是max的不是很好找，但也可以将max按照2/4/8/16/……/2^k划分的话可以较好发现规律,主要就是每一段前半段为上一段+上一段的第一个数，后半段为前半段+上一段第一个数+1，具体看代码，就不细讲了。

需要注意的是，max的规律有的地方有纰漏，可以观察到从n=2开始，偶数段后半段第一个数比我们的规律推出来少1，奇数段第一个数要多1。所以处理一下。

代码如下（时间复杂度O(N)）

#include<bits/stdc++.h>
using namespace std;
int n,minn[5010],maxx[5010],l,r;

int main()
{
    cin>>n;
    minn[1]=0;minn[2]=1;l=1;r=2;
    while(r<n)
    {
        int len=r-l+1;
        for(int i=l+len;i<=r+len;i++)
        {
            minn[i]=minn[i-len];
        }
        for(int i=l+len+len;i<=r+len+len;i++)
        {
            minn[i]=minn[i-len]+1;
        }
        l=l+len;r=r+len+len;
    }
        //min的规律                                         
    maxx[1]=1;maxx[2]=1;l=1;r=2;int cnt=1;
    while(r<n)
    {
        cnt++;
        int len=r-l+1,c=maxx[l];
        for(int i=l+len;i<=r+len;i++)
        {
            maxx[i]=maxx[i-len]+c;
        }
        for(int i=l+len+len;i<=r+len+len;i++)
        {
            maxx[i]=maxx[i-len]+c+1;
        }
        if(cnt%2==0)
        {
            maxx[l+len+len]-=1;
        }
        if(cnt%2==1)
        {
            maxx[l+len]+=1; 
        }
        l=l+len;r=r+len+len;
    }//max的规律
    cout<<minn[n]<<endl<<maxx[n]<<endl;
    return 0;
}