「CODEVS1743」反转卡片
题目描述 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。
题解
用rope写了一下。。。
然后T了。。。似乎原来是可以过的。。
没关系我再复习下splay
|
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 |
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include<ext/rope> #define ll long long #define inf 1000000000 using namespace std; using namespace __gnu_cxx; inline int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int n,ans; int a[300005]; rope<int> s1,s2,t1,t2; void rev(int x) { t1=s1.substr(0,x); t2=s2.substr(n-x,x); s1=t2+s1.substr(x,n-x); s2=s2.substr(0,n-x)+t1; } int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++)s1.push_back(a[i]); for(int i=1;i<=n;i++)s2.push_back(a[n-i+1]); while(s1[0]!=1) { rev(s1[0]); ans++; if(ans>100000){puts("-1");return 0;} } printf("%d",ans); return 0; } |
splay
|
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 |
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #define ll long long #define inf 3000000000 using namespace std; inline int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int n,ans,rt; int a[300005]; int c[300005][2],fa[300005],size[300005],val[300005]; bool rev[300005]; void update(int k) { int l=c[k][0],r=c[k][1]; size[k]=size[l]+size[r]+1; } void rotate(int x,int &k) { int y=fa[x],z=fa[y],l,r; if(c[y][0]==x)l=0;else l=1;r=l^1; if(y==k)k=x; else {if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;} fa[x]=z;fa[y]=x;fa[c[x][r]]=y; c[y][l]=c[x][r];c[x][r]=y; update(y);update(x); } void splay(int x,int &k) { while(x!=k) { int y=fa[x],z=fa[y]; if(y!=k) { if(c[y][0]==x^c[z][0]==y)rotate(x,k); else rotate(y,k); } rotate(x,k); } } void pushdown(int k) { int l=c[k][0],r=c[k][1]; rev[k]^=1;rev[l]^=1;rev[r]^=1; swap(c[k][0],c[k][1]); } void build(int l,int r,int f) { if(l>r)return; int mid=(l+r)>>1; if(mid<f)c[f][0]=mid; else c[f][1]=mid; size[mid]=1;val[mid]=a[mid];fa[mid]=f; if(l==r)return; build(l,mid-1,mid);build(mid+1,r,mid); update(mid); } int find(int k,int rk) { if(rev[k])pushdown(k); int l=c[k][0],r=c[k][1]; if(size[l]+1==rk)return k; else if(size[l]>=rk)return find(l,rk); else return find(r,rk-size[l]-1); } void rever(int l,int r) { int x=find(rt,l),y=find(rt,r+2); splay(x,rt);splay(y,c[x][1]); int z=c[y][0]; rev[z]^=1; } int main() { n=read(); for(int i=1;i<=n;i++) a[i+1]=read(); build(1,n+2,0);rt=(n+3)>>1; while(val[find(rt,2)]!=1) { ans++; rever(1,val[find(rt,2)]); if(ans>100000) { puts("-1");return 0; } } printf("%d\n",ans); return 0; } |
计数器 9786910
OI 课件=>
OI 课件=>
这splay难道是双旋的。。
难道您是传说中的单旋犇…