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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[LCT第一题]弹飞绵羊  

2014-05-11 21:26:03|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |


真的是很神的算法.....

我看了好长时间才会

最巧妙的地方在于其用splay维护的路径被转化成了一个[类似集合的东西],原树的形态巧妙地转化成了无数棵Splay组成的树

犯了几个傻逼错误

代码惊人地短..

Orz Wangxz神犇的讲解

---------------------------------------------

另外,这个题目的做法也很巧妙,

通过 将i位置弹飞一次到的位置记为父亲

把问题转化为了求树上到根节点的路径长

#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int N = 200000+100;
int n,m,data[N];
int min(int a,int b){if(a<b) return a;return b;}
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+'){fh=1;cc=getchar();}
if(cc=='-'){fh=-1;cc=getchar();}
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}
return fh*re;
}
struct Node{
int size;
Node *ch[2],*fa;
Node(){}
Node(Node *l){ch[0]=ch[1]=fa=l;size=0;}
short pl(){return fa->ch[1]==this;}
void count(){size=ch[0]->size+ch[1]->size+1;}
}*null,Slist[N];
class Splay{
public:
bool notr(Node *r){return !((r!=r->fa->ch[0])&&(r!=r->fa->ch[1]));}
void rotate(Node *k){
Node *r=k->fa;if(k==null||r==null) return;
int x = k->pl()^1;
r->ch[x^1] = k->ch[x];
r->ch[x^1]->fa = r;
k->ch[x] = r;
if(notr(r)){r->fa->ch[r->pl()]=k;}
//else ROOT=k;
k->fa=r->fa;r->fa=k;
r->count();k->count();
}
void splay(Node *r){
for(;notr(r);rotate(r))
if(notr(r->fa))
rotate(r->fa->pl()!=r->pl()?r:r->fa);
}
}Stree;
class LCT{
private:
Node *hello(Node *r){
Node *l=null;
for(;r!=null;l=r,r=r->fa){
Stree.splay(r);
(r->ch[1]=l)->fa=r;
r->count();
}
return l;
}
public:
void work(int x){
int a,b;Node *l=&Slist[a=scan()+1];
if(x==1){
hello(l);
Stree.splay(l);
printf("%d\n",l->ch[0]->size);
}else{
b=scan();
Stree.splay(l);
l->ch[0]->fa=l->fa;
l->ch[0]=null;
l->fa=&Slist[min(a+b,n+1)];
}
}
}LinkTree;
int main(){
null=new Node();
*null=Node(null);
//freopen("input.txt","r",stdin);
int i,j,a,b;
n=scan();
Slist[0]=*null;
for(i=1;i<=n;i++){
a=scan();
Slist[i]=Node(null);
Slist[i].count();
Slist[i].fa=&Slist[min(i+a,n+1)];
}
Slist[n+1]=Node(null);
Slist[n+1].count();
m=scan();
for(i=1;i<=m;i++)
LinkTree.work(scan());
return 0;
}

  评论这张
 
阅读(12)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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