注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1483][HNOI2009]梦幻布丁  

2014-12-03 21:27:13|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1483: [HNOI2009]梦幻布丁

不能算非常难的题
但是自己写的时候各种细节问题不停WA....
搞了一个晚上快wa哭了
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 1E5+100;
const int M = 1E6+100;
int n,m,ans;
int data[N],hash[M];
int gl[N],gr[N];
struct Point{
Point(){next = NULL;l=0;}
int l,r;Point *next;
void push(int a,int b){
Point *i = new Point;
i->l = a;i->r = b;
i->next = next;next = i;
l++;
}
}point[M];
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;
if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}return re*fh;
}
int main(){
int i,j,a,b,last=0;
//freopen("in.txt","r",stdin);
//freopen("haha.txt","r",stdin);
n = scan();m = scan();
for(i=1;i<=n;i++){
data[i] = scan();
if(i==1||data[i]!=data[i-1]){
hash[data[i]] = data[i];
if(i>1){
point[data[i-1]].push(last,i-1);
gr[last] = i-1;
gl[i-1] = last;
}
last = i;
ans++;
}
}
point[data[i-1]].push(last,i-1);
gr[last] = i-1;
gl[i-1] = last;

data[0] = data[n+1] = -100;
for(i=1;i<=m;i++){
a = scan();
//printf("[%d]",i);
//if(i==18) printf("haha");
if(a==1){
int aa,bb;
a = scan();b = scan();
aa = a;bb = b;
if(!hash[a])continue;//not exist
if(!hash[b]){hash[b] = hash[a];hash[a]=0;continue;}
a = hash[a];
b = hash[b];
if(a==b)continue;
if(point[a].l > point[b].l){
//cout << "MODE1" << endl;
Point *r = &point[b];
for(Point *l = point[b].next;l!=NULL;r=l,l=l->next){
int &ll = l->l,&rr = l->r;
//del
if(gr[ll]!=rr || gl[rr]!=ll){
r->next = l->next;
l = r;point[b].l--;
continue;
}
if(data[ll-1] == a)ll = gl[ll-1],ans--;//,cout<<"A";
if(data[rr+1] == a)rr = gr[rr+1],ans--;//,cout<<"A";
data[ll] = data[rr] = a;
gr[ll] = rr;gl[rr] = ll;
//if(DE)printf("%d %d\n",ll,rr);
}
point[a].l += point[b].l;
r -> next = point[a].next;
point[a].next = point[b].next;
point[b].next = NULL;
point[b].l=0;
hash[aa]=0;hash[bb]=a;
}else{
//cout << "MODE2" << endl;
Point *r = &point[a];
for(Point *l = point[a].next;l!=NULL;r=l,l=l->next){
int &ll = l->l,&rr = l->r;
//del
if(gr[ll]!=rr || gl[rr]!=ll){
r->next = l->next;
l = r;point[a].l--;
continue;
}
if(data[ll-1] == b)ll = gl[ll-1],ans--;
if(data[rr+1] == b)rr = gr[rr+1],ans--;
data[ll] = data[rr] = b;
gr[ll] = rr;gl[rr] = ll;
//if(DE)printf("%d %d\n",ll,rr);
}
point[b].l += point[a].l;
r -> next = point[b].next;
point[b].next = point[a].next;
point[a].next = NULL;
point[a].l=0;
hash[aa]=0;hash[bb]=b;
}
}else{
printf("%d\n",ans);
}
}
return 0;
}

题解:
启发式合并 + 链表。
合并的时候需要注意姿势......
需要建一个映射数组hash
如果是反着题目合并需要交换两个的映射值
  评论这张
 
阅读(47)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017