比赛描述不是我写的！！！！
回过神来发现就公开赛已经已经过审了orz
题解
这道题目有一个思维陷阱，那就是题目过分强调了集合的概念，导致大家一拿到这个题目就会往并查集上面去向，不过稍微玩过数据之后就会发现，这其实就是一道简单的维护最大值的题目。
因为本次比赛的题目原本是OI赛制，在我们学校内部考的，所以这道题给了几个梯度，顺着梯度来是很好想到正解的，但是想要实现还是要有不错的代码功底。（为了防止网络赛的复制模板的行为，特意复杂化了题目）
优先队列——期望得分30
观察约定我们发现，有6个点是既满足没有单点修改（清零），又满足单点插入（合并）的性质，很容易想到用优先队列维护。
优先队列里存的是一个二元组，分别是该点的值以及编号。
但是优先队列有个问题就是没办法单点修改，这时候就要我们手写堆。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int MAXN=2000001; long long m,n,w,k,t; priority_queue<pair<long long,int> >s[MAXN]; int set[MAXN];//i点在哪个优先队列里，并查集实现 bool v[MAXN];//确保每个集合只贡献一次答案 inline long long read() { char ch = getchar(); long long x = 0, f = 1; while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); } while('0' <= ch && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } void clear(){//每组输入要重置 memset(set,0,sizeof(set)); memset(v,0,sizeof(v)); } int main(){ cin>>t>>w>>k; while(t--){ clear(); n=read(),m=read(); for(int i=1;i<=n;i++){ while(s[i].size())s[i].pop();//这里会比较慢 long long a; a=read(); set[i]=i; s[i].push(make_pair(a,i)); } while(m--){ long long way,a,b; way=read(); if(way==2)a=read();//不管2操作 else if(way==3){//由于优先队列是只读的，所以要先取出来再弄进去 a=read(),b=read(); a=set[a]; pair<long long,int> tmp=s[a].top(); s[a].pop(); tmp.first-=b; if(tmp.first<0)tmp.first=0; s[a].push(tmp); } else{//将小的集合并入大的集合 a=read(),b=read(); if(a==b)continue; int sa=set[a],sb=set[b]; if(s[sb].size()==1)swap(sa,sb); s[sb].push(s[sa].top()); set[s[sa].top().second]=sb; s[sa].pop(); } } long long sum=0,mx=0; for(int i=1;i<=n;i++){ if(v[set[i]])continue; v[set[i]]=1; sum+=s[set[i]].top().first; mx=max(mx,s[set[i]].top().first); } if(w==2)sum-=mx; if(w==3)sum+=mx; if(sum==0)printf("Gensokyo 0\n"); else if(sum<=k)printf("Heaven %lld\n",sum); else printf("Hell %lld\n",sum); } return 0; } |
大根堆——期望得分60
按照刚刚优先队列的思路，要想单点修改，还得自己写堆。
但是因为不确定每个堆的大小，所以不能直接开2000000个堆，所以得用链表实现，或者用数组模拟，这样子就能过掉所有有特殊约定的点。
对于不满足约定①的数据，当然也可以将两个堆合并，说不定还能多过一两个点。
左偏树（或者其他可并堆）——期望得分100
普通的堆的合并时间复杂度都是\(O(n^2)\)的，而对于不满足约定①的数据，我们显然需要一种数据结构，来实现快速合并，通过上面两种方法的引导，我们可以采用可并堆（这里用的是左偏树，最简单的可并堆），合并两个堆的时间复杂度为\(O(nlogn)\)
如果你不清楚左偏树做这道题，在思维的过程中，也应该体会到了左偏树的用法。
左偏树在维护了堆的性质的同时，还用\(dis\)来维护一个距离值，具体是说，节点i的距离(dis(i))是节点i到它的子树中，最近的叶子节点所经过的边数。
两个基本性质：
[性质1 堆] 节点的键值小于或等于它的左右子节点的键值。
[性质2 左偏] 节点的左子节点的距离不小于右子节点的距离。（在合并操作时起作用）
这里有篇文章专门讲左偏树，比较详细
然后你会发现这是道模板题（不好意思我太弱了orz），就用pb_ds库给A掉了。
先贴我的代码，比较丑，没有常数优化（个人不是很喜欢卡常）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MAXN=2000000; long long m,n,w,k,t; int set[MAXN];//并查集 bool v[MAXN]; struct node{ long long l,r,dis,key; }tree[MAXN]; namespace LF{ int find(int a){//并查集 int root=a; while(root!=set[root])root=set[root]; int pa=set[a]; while(pa!=root){ set[a]=root; a=pa; pa=set[a]; } return root; } int merge(int a,int b){//合并 if(!a)return b; if(!b)return a; if(tree[a].key<tree[b].key)swap(a,b); tree[a].r=merge(tree[a].r,b); set[tree[a].r]=a; if(tree[tree[a].l].dis<tree[tree[a].r].dis)swap(tree[a].l,tree[a].r); if(tree[a].r)tree[a].dis=tree[tree[a].r].dis+1; else tree[a].dis=0; return a; } int pop(int a){ int l=tree[a].l; int r=tree[a].r; set[l]=l; set[r]=r; tree[a].l=tree[a].r=tree[a].dis=0; return merge(l,r); } } void clear(){//初始化 memset(set,0,sizeof(set)); memset(v,0,sizeof(v)); } int main(){ cin>>t>>w>>k; while(t--){ clear(); scanf("%lld%lld",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&tree[i].key); set[i]=i;//并查集初始化 tree[i].r=tree[i].l=tree[i].dis=0; } while(m--){ int way; scanf("%d",&way); if(way==2){ int x; scanf("%d",&x); tree[x].key=0; int tmp=LF::pop(x); LF::merge(x,tmp); } else if(way==3){ int a,b,ra; scanf("%d%d",&a,&b); ra=LF::find(a); tree[ra].key-=b; if(tree[ra].key<0)tree[ra].key=0; int tmp=LF::pop(ra); LF::merge(tmp,ra); } else { int a,b,ra,rb; scanf("%d%d",&a,&b); if(a==b)continue; ra=LF::find(a),rb=LF::find(b); LF::merge(ra,rb); } } long long sum=0,mx=0; for(int j=1;j<=n;j++){ int i=LF::find(j); if(v[set[i]])continue; v[set[i]]=1; int root=LF::find(i); mx=max(mx,(long long)tree[root].key); sum+=tree[root].key; } if(w==2)sum-=mx; if(w==3)sum+=mx; if(sum==0)printf("Gensokyo 0\n"); else if(sum<=k)printf("Heaven %lld\n",sum); else printf("Hell %lld\n",sum); } return 0; } |
这个是@Ajsoabk大佬写的，短小精悍，加了快读都比我短。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include<iostream> #include<cstdio> using namespace std; const int N=2000000+5; struct Node{ int val,disx,lson,rson; }nod[N]; int fa[N],t,w,n,m,typ,A,B,tem; bool vis[N]; long long k; inline void read(int &num){ char ch; while(!isdigit(ch=getchar())); num=ch-'0'; while(isdigit(ch=getchar()))num=num*10+ch-'0'; } int merge(int a,int b){//合并 if(a==0)return b; if(b==0)return a; if(nod[a].val<nod[b].val)swap(a,b); fa[nod[a].rson=merge(nod[a].rson,b)]=a; nod[a].disx=(nod[a].rson==0)?0:nod[nod[a].rson].disx+1; if(nod[nod[a].lson].disx<nod[nod[a].rson].disx)swap(nod[a].lson,nod[a].rson); return a; } int find(const int &a){//并查集 return (a==fa[a])?a:find(fa[a]); } inline void decline(const int &A,const int &val,bool fla){ nod[A].val-=val; if(nod[A].val<0)nod[A].val=0; fa[nod[A].lson]=nod[A].lson; fa[nod[A].rson]=nod[A].rson; int l=nod[A].lson,r=nod[A].rson; nod[A].lson=nod[A].rson=nod[A].disx=0; tem=merge(l,r); if(fla)merge(find(A),tem); else merge(tem,A); } int main(){ read(t),read(w); cin>>k; while(t--){ read(n),read(m); for(int i=1;i<=n;++i)fa[i]=i,read(nod[i].val),vis[i]=0,nod[i].lson=nod[i].rson=nod[i].disx=0; for(int i=1;i<=m;++i){ read(typ),read(A); switch(typ){ case 2: decline(A,nod[A].val,1); break; case 3: read(B); decline(find(A),B,0); break; case 4: read(B); merge(find(A),find(B)); break; } } B=0; typ=0; for(int i=1;i<=n;++i){ A=find(i); if(!vis[A]){ vis[A]=true; B=max(B,nod[A].val); typ+=nod[A].val; } } if(w==2)typ-=B; else if(w==3)typ+=B; if(typ==0)printf("Gensokyo "); else if((long long)typ<=k)printf("Heaven "); else printf("Hell "); printf("%d\n",typ); } return 0; } |
写在后面
其实这道题目一开始还更难，后面就变成了一道模板题
数据是随机生成的，可能这一点比较坑吧，只要有点微小的差错就会WA（我反省）
其实数据挺弱的，set+并查集，暴力合并，都只超时1个点