牛客网暑期多校训练赛 第三场 C题 Shuffle Cards

本文主要是介绍牛客网暑期多校训练赛 第三场 C题 Shuffle Cards，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

 

题意：

有一堆卡牌，一开始是从1到n的序列放好，现在有M次操作。每次操作将从第Pi个卡牌开始往后拿出Si个卡牌放在剩余卡牌的上方。问最后序列是什么。

 

思路：

打完比赛的时候发现了大佬的解法，用了一个完全没听过的操作rope。代码几乎可以说是和string一样了，但是它的速度却是惊人的快，赶紧学起来！！！

 

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;
rope<int> a;
int main()
{int n,q,l,r;scanf("%d%d",&n,&q);for(int i=1;i<=n;i++)a+=i;for(int i=1;i<=q;i++){scanf("%d%d",&l,&r);a=a.substr(l-1,r)+a.substr(0,l-1)+a.substr(l+r-1,n-(l+r-1)+1);}for(int i=0;i<n;i++){if(i!=n-1)printf("%d ",a[i]);elseprintf("%d\n",a[i]);}return 0;
}

 

正常的思路：

 

用一个平衡树来处理，这个操作，先将1~Pi+Si-1这个区间翻转。然后再将1~Si区间翻转，和Si+1~Pi+Si-1区间翻转就是最后的区间。这里学了一下fhqtreap，一个非旋转的treap代码比SPLAY好写很多。

 

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ctime>
using namespace std;
const int maxn=1e5+5;
struct node
{int son[2],v,rnd,size;int fz;
}tr[maxn];
int n,m,l,r;
int tot,root;
int new_node(int v)//创建权值为v的结点。
{tot++;tr[tot].size=1;tr[tot].v=v;tr[tot].rnd=rand();tr[tot].fz=tr[tot].son[0]=tr[tot].son[1]=0;return tot;
}
void update(int x)
{tr[x].size=tr[tr[x].son[0]].size+tr[tr[x].son[1]].size+1;if(x&&tr[x].fz){tr[tr[x].son[0]].fz^=1;tr[tr[x].son[1]].fz^=1;swap(tr[x].son[0],tr[x].son[1]);tr[x].fz^=1;}
}
int build(int l,int r)
{if(l>r) return 0;int mid=(l+r)/2;int v=mid-1;int now=new_node(v);tr[now].son[0]=build(l,mid-1);tr[now].son[1]=build(mid+1,r);update(now);return now;
}
int merge(int x,int y)
{if(!x||!y)return x+y;update(x),update(y);if(tr[x].rnd<tr[y].rnd){tr[x].son[1]=merge(tr[x].son[1],y);update(x);return x;}else{tr[y].son[0]=merge(x,tr[y].son[0]);update(y);return y;}
}void split(int now,int k,int &x,int &y)//按照节点个数分离，把节点个数小于k的分给x，大于等于的分给y
{if(!now)x=y=0;else{update(now);if(k<=tr[tr[now].son[0]].size)y=now,split(tr[now].son[0],k,x,tr[now].son[0]);elsex=now,split(tr[now].son[1],k-tr[tr[now].son[0]].size-1,tr[now].son[1],y);update(now);}
}void rev(int l,int r)
{int x,y,u,v;split(root,r+1,x,y);split(x,l,u,v);tr[v].fz^=1;root=merge(merge(u,v),y);
}
void print(int now)
{if(!now)return;update(now);print(tr[now].son[0]);if(tr[now].v>=1&&tr[now].v<=n)printf("%d ",tr[now].v);print(tr[now].son[1]);
}
int main()
{srand((unsigned)time(NULL));scanf("%d%d",&n,&m);root=build(1,n+2);for(int i=1;i<=m;i++){scanf("%d%d",&l,&r);rev(1,l+r-1);rev(1,r);rev(r+1,l+r-1);}print(root);return 0;
}

 

这篇关于牛客网暑期多校训练赛 第三场 C题 Shuffle Cards的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---