[BZOJ 1483][HNOI2009]梦幻布丁

danihao123 posted @ 2017年11月30日 12:45 in 题解 with tags 链表 HNOI bzoj 启发式合并 , 125 阅读
转载请注明出处:http://danihao123.is-programmer.com/

做了很久了吧,但现在才写题解……(斜眼

首先记录一个起始的颜色段数,然后每种颜色都要用链表顺序记下该颜色有哪些点。然后合并的时候合并两个链表——最优策略显然是启发式合并。

但是,很多时候并不是把小链表的扔到大的里面的情况,而是恰好反过来的情况,如何处理?

这种时候,我们可以交换两个颜色的“真实身份”。合并的时候,把每个点当成它的“真实身份”处理即可。

代码:

/**************************************************************
    Problem: 1483
    User: danihao123
    Language: C++
    Result: Accepted
    Time:444 ms
    Memory:20352 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using std::swap;
const int maxn=1000005;
int fact[maxn];
int first[maxn],next[maxn];
int siz[maxn];
 
int color[maxn];
int cnt=0;
int main(){
  register int i,j,last,ans=0;
  int n,m,op,a,b;
  scanf("%d%d",&n,&m);
  for(i=1;i<=n;i++){
    scanf("%d",&color[i]);
    cnt++;
    next[cnt]=first[color[i]];
    first[color[i]]=cnt;
    fact[color[i]]=color[i];
    siz[color[i]]++;
    if(color[i]!=color[i-1]){
      ans++;
    }
  }
  while(m--){
    scanf("%d",&op);
    if(op==2){
      printf("%d\n",ans);
    }else{
      scanf("%d%d",&a,&b);
      if(a==b){
        continue;
      }
      if(siz[fact[a]]>siz[fact[b]]){
        swap(fact[a],fact[b]);
      }
      a=fact[a];b=fact[b];
      if(siz[a]==0){
        continue;
      }
      for(j=first[a];j;j=next[j]){
        if(color[j-1]==b) ans--;
        if(color[j+1]==b) ans--;
      }
      for(j=first[a];j;j=next[j]){
        color[j]=b;
        last=j;
      }
      next[last]=first[b];
      first[b]=first[a];
      siz[b]+=siz[a];
      siz[a]=0;
      first[a]=0;
    }
  }
  return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter