博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
codevs 1743 反转卡片
阅读量:5875 次
发布时间:2019-06-19

本文共 2406 字,大约阅读时间需要 8 分钟。

题目描述
Description

【dzy493941464|yywyzdzr原创】 

小A将N张卡片整齐地排成一排,其中每张卡片上写了1~N的一个整数,每张卡片上的数各不相同。

比如下图是N=5的一种情况:3 4 2 1 5

接下来你需要按小A的要求反转卡片,使得左数第一张卡片上的数字是1。操作方法:令左数第一张卡片上的数是K,如果K=1则停止操作,否则将左数第1~K张卡片反转。

第一次(K=3)反转后得到:2 4 3 1 5

第二次(K=2)反转后得到:4 2 3 1 5

第三次(K=4)反转后得到:1 3 2 4 5

可见反转3次后,左数第一张卡片上的数变成了1,操作停止。

你的任务是,对于一种排列情况,计算要反转的次数。你可以假设小A不会让你操作超过100000次。

输入描述
Input Description

第1行一个整数N

第2行N个整数,为1~N的一个全排列。

输出描述
Output Description

仅1行,输出一个整数表示要操作的次数。

如果经过有限次操作仍无法满足要求,输出-1。

样例输入
Sample Input

5

3 4 2 1 5

 

 

样例输出
Sample Output

3

数据范围及提示
Data Size & Hint

0<N≤300,000。

 

splay翻转裸题,又调了一个下午

1 #include
2 #include
3 using namespace std; 4 const int N=300010; 5 int size[N],c[N][2],rev[N],fa[N],id[N],a[N]; 6 int n,rt; 7 void pushup(int k){ 8 int l=c[k][0],r=c[k][1]; 9 size[k]=size[l]+size[r]+1;10 }11 12 void pushdown(int k){13 if (rev[k]){14 int l=c[k][0],r=c[k][1]; 15 swap(c[k][1],c[k][0]);16 rev[l]^=1;rev[r]^=1;17 rev[k]=0;//第一次k打成l,wa18 }19 }20 21 void rotate(int x,int &k){22 int y=fa[x],z=fa[y],l,r;23 if (c[y][0]==x)l=0;else l=1;r=l^1;24 if (y==k)k=x;25 else if (c[z][0]==y)c[z][0]=x; else c[z][1]=x;26 fa[c[x][r]]=y; fa[x]=z; fa[y]=x;27 c[y][l]=c[x][r];c[x][r]=y;28 pushup(y);pushup(x);29 }30 31 void splay(int x,int &k){32 while (x!=k){
//忘记打这一句 wa*233 int y=fa[x],z=fa[y];34 if (y!=k){35 if (c[z][0]==y^c[y][0]==x) rotate(x,k);36 else rotate(y,k);37 }38 rotate(x,k);39 }40 }41 42 void build(int l,int r,int f)43 {44 if(l>r)return;45 int mid=(l+r)>>1;46 if(mid
=rk) return find(l,rk);59 return find(r,rk-size[l]-1);60 }61 62 void rever(int l,int r){63 int x=find(rt,l),y=find(rt,r+2);64 splay(x,rt); splay(y,c[x][1]);65 int z=c[y][0];//这句写错了wa*466 rev[z]^=1;67 }68 69 int main(){70 scanf("%d",&n);71 for (int i=2;i<=n+1;i++) scanf("%d",&a[i]);72 for (int i=1;i<=n+2;i++) id[i]=i;73 build(1,n+2,0); rt=(n+3)>>1;74 int sum=0;75 bool flag=0;76 while (sum<=100000){77 int mid=a[find(rt,2)];78 if (mid==1){79 flag=1;80 break;81 }82 sum++;83 rever(1,mid);84 }85 if (flag) printf("%d",sum);86 else printf("-1");87 }

 

转载于:https://www.cnblogs.com/wuminyan/p/5137906.html

你可能感兴趣的文章
Struts2中Date日期转换的问题
查看>>
mysql 数据类型
查看>>
Ubuntu 设置当前用户sudo免密码
查看>>
设置tomcat远程debug
查看>>
android 电池(一):锂电池基本原理篇【转】
查看>>
Total Command 常用快捷键
查看>>
ionic 调用手机的打电话功能
查看>>
怎么使用阿里云直播服务应用到现在主流直播平台中
查看>>
Xcode全局替换内容,一键Replace
查看>>
1000 加密算法
查看>>
exif_imagetype() 函数在linux下的php中不存在
查看>>
Ruby的case语句
查看>>
Linux的链接文件-ln命令
查看>>
maven的tomcat插件如何进行debug调试
查看>>
table表头固定
查看>>
截取字符串中两个字符串中的字符串
查看>>
spring xml properties split with comma for list
查看>>
判断点是否在三角形内
查看>>
Android实战简易教程-第二十三枪(基于Baas的用户注冊验证username是否反复功能!)...
查看>>
在odl中怎样实现rpc
查看>>