首页分享 BZOJ 1208 [HNOI2004] 宠物收养所题解&代码

BZOJ 1208 [HNOI2004] 宠物收养所题解&代码

来源：萌宠菠菠乐园时间：2025-04-24 23:14

其实是一道简单的Splay题目【虽然我写了很久
据说【本来就是】用set+二分很容易就过啦，的确一个不需要maintain和pushdown的Splay和咸鱼没什么区别，不过第一次写Splay我觉得自己写得好丑啊= =【还调了一个多小时

题意：
给出宠物和人出现的序列，宠物和人都会选择
①现在存在的
②和自己特征值之差的绝对值最小的
③特征值最小的
非同类【即宠物选择人，人选择宠物】，选择成功时将会累计一个特征值差的绝对值作为不满意度，当序列结束时输出不满意度的和对1000000取模的值
显而易见选择的方案是唯一的

思路：
set+二分：
利用set中元素的单调性进行二分查找匹配，插入复杂度logn，匹配复杂度logn
Splay：
维护一个以操作序列元素编号为值的Splay，可以预见，Splay中只有宠物/人/Splay为空。所以如果Splay现在是宠物，那么有人来的时候只要删除匹配点即可，有宠物来时加入Splay；如果Splay是空的，那么无论谁来都加入Splay。
插入操作：找到Splay中和这个点val相匹配的空节点，连接节点和它的父节点，然后Splay一次将它旋转到根【维护Splay平衡性
删除匹配点操作：将待匹配点插入Splay，然后找到该节点的前驱和后继，由上面的规则得到唯一的匹配元素，然后删除待匹配点和匹配元素所在的节点【删除操作即找到其前驱/后继，旋转至其下方，然后以其前驱/后继代替其位置即可】

#include<iostream> #include<stdio.h> #define LL long long using namespace std; const int maxn=80005; const int mod=1000000; int c=-1,d,r=0,s,n,fa[maxn],ch[maxn][2],val[maxn]; LL ans=0; LL abs(int a,int b) { LL k=(LL)val[a]-(LL)val[b]; if(k<0)k=-k; return k; } void link(int x,int y,int d) { ch[y][d]=x; fa[x]=y; } bool ischild(int x) { return ch[fa[x]][1]==x; } void rotate(int x,int d) { int y=fa[x],z=fa[y]; link(ch[x][!d],y,d); if(z)link(x,z,ischild(y)); else fa[x]=fa[y]; link(y,x,!d); } void Splay(int x,int goal=0) { int y=fa[x],z=fa[y]; while(y!=goal) { //cout<<y<<' '<<z<<endl; //getchar(); if(z==goal) { rotate(x,ischild(x)); break; } if(ischild(y)) { //cout<<ischild(x)<<endl; if(ischild(x))rotate(y,1); else rotate(x,0); rotate(x,1); } else { if(ischild(x))rotate(x,1); else rotate(y,0); rotate(x,0); } y=fa[x],z=fa[y]; } if(!fa[x])r=x; } int getpre(int x) { int y=ch[x][0]; while(ch[y][1])y=ch[y][1]; return y; } int getnext(int x) { int y=ch[x][1]; while(ch[y][0])y=ch[y][0]; return y; } int getmax(int x) { while(ch[x][1]) x=ch[x][1]; return r; } void addtree(int x) { int y=r; while(ch[y][val[x]>val[y]])y=ch[y][val[x]>val[y]]; link(x,y,val[x]>val[y]); //cout<<x<<' '<<y<<endl; Splay(x); } void delnode(int x) { if(s==1) { r=0; s=0; return; } addtree(x); int pre=getpre(x),nex=getnext(x),f; //cout<<pre<<' '<<nex<<endl; if(nex==0 || (pre && abs(pre,x)<=abs(nex,x))) f=pre,ans+=abs(pre,x); else f=nex,ans+=abs(nex,x); ans%=mod; if(pre) { Splay(pre,x); link(ch[x][1],pre,1); fa[pre]=0; r=pre; } else { Splay(nex,x); fa[nex]=0; r=nex; } Splay(f); pre=getpre(f); nex=getnext(f); if(pre) { Splay(pre,f); link(ch[f][1],pre,1); fa[pre]=0; r=pre; } else if(nex) { Splay(nex,f); fa[nex]=0; r=nex; } else r=0,s=0; } int main(void) { //freopen("pet2.in","r",stdin); //freopen("pet.ans","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&d,&val[i]); if(c==-1 || c==d) { if(r==0)r=i; else addtree(i); s++; c=d; continue; } delnode(i); if(r==0)c=-1; } printf("%lldn",ans); return 0; }

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155