edward_mj

【题目】http://www.oi.bbjy.com/n38c10.aspx

【算法分析】

送分题，树形DP之。

虽然我写的比较复杂，但是第一感觉就这个，没所谓了，反正能AC。

首先风铃只能分布于相邻的两层。

判断以后，设cd为靠上的一层。

然后

F[i][0]表示我下面的都是层数为cd的风铃。

F[i][1]表示我下面的都是层数为cd+1的风铃。

F[i][2]表示我下面的是由cd和cd+1的风铃混合而成，而且满足题目性质。即先是一段cd+1的，然后再是一段cd的。

然后转移一下，就可以了。

【其他】1A

【CODE】

#include #include const int N=101111;
const int INF=1000000000;
int n,cd;
int F[N][3],L[N],R[N],dep[N],v[N];

void input(){
     scanf("%d",&n);
     for (int i=1;i<=n;i++) scanf("%d%d",&L[i],&R[i]);
}

void Get_dep(){
     dep[1]=1;
     for (int i=1;i<=n;i++){
         if (L[i]!=-1) dep[L[i]]=dep[i]+1;
         if (R[i]!=-1) dep[R[i]]=dep[i]+1;
     }
}

bool can_same_dep(){
     memset(v,0,sizeof(v));
     int depnum=0;
     for (int i=1;i<=n;i++)
       if (L[i]==-1 || R[i]==-1){
         if (!v[dep[i]]) depnum++;
         v[dep[i]]++;
       }
     if (depnum>2) return false;
     if (depnum<=1) return true;
     for (int i=1;i<=n;i++)
       if (v[i])
         if (v[i+1]){
           cd=i;
           return true;
         }
         else return false;
}

inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x

void dp(){
     int i,j;
     for (i=1;i<=n;i++)
       for (j=0;j<3;j++)
         F[i][j]=INF;
     for (i=1;i<=n;i++)
       if (L[i]==-1 && R[i]==-1)
         if (dep[i]==cd) F[i][0]=0;
                    else F[i][1]=0;
     for (i=n;i>=1;i–)
       if (L[i]!=-1 || R[i]!=-1)
         if (L[i]==-1){
           if (dep[i]==cd){
             F[i][0]=F[R[i]][0];
             F[i][2]=min(F[i][2],F[R[i]][2]+1);
             F[i][2]=min(F[i][2],F[R[i]][1]+1);
           }
           else{
             F[i][1]=F[R[i]][1];
             F[i][2]=min(F[i][2],F[R[i]][2]);
             F[i][2]=min(F[i][2],F[R[i]][0]);
           }
         }
         else if (R[i]==-1){
           if (dep[i]==cd){
             F[i][0]=F[L[i]][0];
             F[i][2]=min(F[i][2],F[L[i]][1]);
             F[i][2]=min(F[i][2],F[L[i]][2]);
           }
           else{
             F[i][1]=F[L[i]][1];
             F[i][2]=min(F[i][2],F[L[i]][2]+1);
             F[i][2]=min(F[i][2],F[L[i]][0]+1);
           }
         }
         else{
           F[i][0]=min(F[i][0],F[L[i]][0]+F[R[i]][0]);
           F[i][1]=min(F[i][1],F[L[i]][1]+F[R[i]][1]);
           int &t=F[i][2];
           t=min(t,F[L[i]][1]+F[R[i]][0]);
           t=min(t,F[L[i]][1]+F[R[i]][2]);
           t=min(t,F[L[i]][2]+F[R[i]][1]+1);
           t=min(t,F[L[i]][2]+F[R[i]][0]);
           t=min(t,F[L[i]][0]+F[R[i]][1]+1);
           t=min(t,F[L[i]][0]+F[R[i]][2]+1);
         }
     int ans=INF;
     ans=min(ans,F[1][0]);
     ans=min(ans,F[1][1]);
     ans=min(ans,F[1][2]);
     if (ans==INF) printf("-1n");
              else printf("%dn",ans);
}

int main(){
    freopen("mobiles.in","r",stdin);
    freopen("mobiles.out","w",stdout);
    input();
    Get_dep();
    if (can_same_dep()) dp();
    else printf("-1n");
}

【题目】http://wenku.baidu.com/view/079ae6f9aef8941ea76e0599.html

【算法分析】非原创。。。。

首先不考虑字典序，那么就是按r排序，然后贪心取就可以了。

现在考虑字典序。

我们考虑到搞字典序有一个通法，那就是尝试加入某一个点，然后判断结果是否仍可以达到最优，如果是，那么就加进去。否则不加。然后就可以得到一个保证字典序的解了。。。

我们先对data按r排一下序，然后注意到如果一个区间包含另一个区间，那么大区间对判断能否构成最优解必然是没用的。删掉。。。

然后我们就会发现，不只R递增，连L也递增了！

然后设MIS(I,J)表示经过处理以后，第I个区间到第J个区间都可以选用，最多能连成多少个区间。

我们加入一条线段的话，那么就只需要判断是否满足

MIS(pos(preR),pos(L))+MIS(pos(R),pos(nextL))+1==MIS(pos(preR),pos(nextL))就行了。

现在来搞MIS

令right(i)^k=right(right(right(i)))…..(right()出现k次)

那么MIS(i,j)=max(k)   条件：right(i)^k<=j

如果是这样的话，就好搞多了。

我们就像rmq的ST算法一样把right(i)^(2^p)处理出来。

然后从i每次以2^step步长向后走，看什么时候不能走就行了。

因为存在一个性质：

2^0、2^1、2^2、2^3……..2^n

它们能通过每个只用一次的加法组成[1..2^(n+1)-1]这个区间里的任意数。

证明的话很容易，直接把+2^k相当于把二进制的某位数变成1，因为2进制与10进制一一对应，所以必然可以组合成。

纵观所以操作，发现平衡树可以解决。。。于是果断写了SBT。。。

【其它】代码写庛了。。。长达250行

【CODE】

#include #include #include #include using namespace std;
const int N=201111;
const int INF=1000000000;
struct Type{int l,r;}d[N],td[N];
int n,xt,tdn,ans,TOT;
int xl[N+N],lg[N],ansl[N];
int right[N][20];

struct SBTType{
    int tot,root;
    struct PointType{int l,r,s,zz;}tr[N];
   
    void update(int &p){
        if (!p) return;
        tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    }   
   
    void left(int &p){
        int k=tr[p].r;
        tr[p].r=tr[k].l;
        tr[k].l=p;
        update(p);
        update(k);
        p=k;
    }   
   
    void right(int &p){
        int k=tr[p].l;
        tr[p].l=tr[k].r;
        tr[k].r=p;
        update(p);
        update(k);
        p=k;
    }
       
    void repair(int &p){
        if (!p) return;
        bool flag=false;
        if (tr[tr[tr[p].l].l].s>tr[tr[p].r].s){
          right(p);
          flag=true;
        }   
        if (tr[tr[tr[p].l].r].s>tr[tr[p].r].s){
            left(tr[p].l);
            right(p);
            flag=true;
        }   
        if (tr[tr[tr[p].r].r].s>tr[tr[p].l].s){
            left(p);
            flag=true;
        }   
        if (tr[tr[tr[p].r].l].s>tr[tr[p].l].s){
            right(tr[p].r);
            left(p);
            flag=true;
        }   
        if (flag){
            repair(tr[p].l);
            repair(tr[p].r);
            repair(p);
        }   
    }   
   
    void ins(int &p,int i){
        if (!p){
            p=++tot;
            tr[p].l=0; tr[p].r=0; tr[p].zz=i; update(p);
        }
        else{
            tr[p].s++;
            if (d[tr[p].zz].r                                 else ins(tr[p].l,i);
            repair(p);
        }   
    }   
   
    bool cross(int &p,int l,int r){
        if (!p) return false;
        if (r        if (l>d[tr[p].zz].r) return cross(tr[p].r,l,r);
        return true;
    }
   
    int FindR(int &p,int limit){
        if (!p) return 0;
        if (d[tr[p].zz].r<=limit) return max(d[tr[p].zz].r,FindR(tr[p].r,limit));
        return FindR(tr[p].l,limit);
    }   
   
    int FindL(int &p,int limit){
        if (!p) return INF;
        if (d[tr[p].zz].l>=limit) return min(d[tr[p].zz].l,FindL(tr[p].l,limit));
        return FindL(tr[p].r,limit);
    }   
}sbt;   

void input(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d%d",&d[i].l,&d[i].r);
    lg[1]=0;
    for (int i=2;i<=n;i++)
      lg[i]=lg[i-1]+(i==1<}   

int binary(int x){
    int l=1,r=xt,mid;
    while (l        mid=(l+r)/2;
        if (x<=xl[mid]) r=mid;
                   else l=mid+1;
    }   
    return l;
}   

void LiSan(){
    xt=0;
    for (int i=1;i<=n;i++){
        xl[++xt]=d[i].l;
        xl[++xt]=d[i].r;
    }
    sort(xl+1,xl+xt+1);
    int tot=xt; xt=0;
    for (int i=1;i<=tot;i++)
      if (!xt || xl[xt]!=xl[i])
        xl[++xt]=xl[i];
    for (int i=1;i<=n;i++){
        d[i].l=binary(d[i].l);
        d[i].r=binary(d[i].r);
    }   
}   

bool cmp(Type x,Type y){
    if (x.r    if (x.r>y.r) return false;
    if (x.l>y.l) return true;
    return false;
}   

void init(){
    for (int i=1;i<=n;i++) td[i]=d[i];
    sort(td+1,td+1+n,cmp);
    tdn=0;
    for (int i=1;i<=n;i++)
      if (!tdn || td[i].l>td[tdn].l)
        td[++tdn]=td[i];
}

void getans(){
    ans=1; int R=td[1].r;
    for (int i=2;i<=tdn;i++)
      if (td[i].l>R){
          ans++;
          R=td[i].r;
      }   
}   

void make_right(){
    for (int k=0;1<    for (int i=1;i<=tdn;i++){
        int l=i+1,r=tdn,mid;
        while (l            mid=(l+r)/2;
            if (td[i].r                              else l=mid+1;
        }   
        if (l>tdn || td[i].r>=td[l].l) right[i][0]=tdn+1;
                                  else right[i][0]=l;
    }   
    for (int k=1;1<      for (int i=1;i<=n;i++)
        right[i][k]=right[right[i][k-1]][k-1];
}  

int MIS(int l,int r){
    if (r    int res=1;
    for (int cur=l,step=lg[r-l+1];step>=0;step–)
      if (right[cur][step]<=r){
          res+=1<          cur=right[cur][step];
      }   
    return res;
}  

int Findmax(int x){
    int l=1,r=tdn,mid;
    while (l        mid=(l+r)/2;
        if (td[mid].l>x) r=mid;
                    else l=mid+1;
    }   
    if (td[l].l>x) return l;
    return INF;
}

int Findmin(int x){
    int l=1,r=tdn,mid;
    while (l+1        mid=(l+r)/2;
        if (td[mid].r                    else r=mid-1;
    }   
    if (td[r].r    if (td[l].r    return -INF;
}   

bool Can(int i){
    if (sbt.cross(sbt.root,d[i].l,d[i].r)) return false;
    int L,R,l,r,tmp1=0,tmp2=0;
    L=sbt.FindR(sbt.root,d[i].l-1);
    R=sbt.FindL(sbt.root,d[i].r+1);
    if (!L) L=1;       else L=Findmax(L);
    if (R==INF) R=tdn; else R=Findmin(R);
    l=Findmin(d[i].l);
    r=Findmax(d[i].r);
    tmp1=MIS(L,l);
    tmp2=MIS(r,R);
    if (tmp1+tmp2+1!=MIS(L,R)) return false;
    return true;
}   

void work(){
    for (int i=1;i<=n;i++)
      if (Can(i)){
        sbt.ins(sbt.root,i);
        ansl[++TOT]=i;
      }   
    printf("%dn",ans);
    for (int i=1;i<=ans;i++){
        printf("%d",ansl[i]);
        if (i!=ans) printf(" ");
    }   
    printf("n");
}   

int main(){
    freopen("convention.in","r",stdin);
    freopen("convention.out","w",stdout);
    input();
    LiSan();
    init();
    getans();
    make_right();
    work();
}