首页 > 代码库 > Uva 12657 双向链表
Uva 12657 双向链表
题目链接：https://uva.onlinejudge.org/external/126/12657.pdf
题意：
给你一个从1~n的数，然后给你操作方案
• 1 X Y : move box X to the left to Y (ignore this if X is already the left of Y )
• 2 X Y : move box X to the right to Y (ignore this if X is already the right of Y )
• 3 X Y : swap box X and Y
• 4: reverse the whole line.
WA的地方：
1、指针的赋值顺序，还是先保存一下。
2、交换的时候，如果相邻，要特判，否则指针会乱。
3、反转的时候，我这里是实际上没有反转的，因此，操作 1,2，就会由于是否反转而混乱。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int maxn = 100005; 6 int lefts[maxn]; 7 int rights[maxn]; 8 9 void link(int x,int y)10 {11 rights[x] = y;12 lefts[y] = x;13 }14 15 int main()16 {17 int n,m;18 int kase = 1;19 while(~scanf("%d%d",&n,&m))20 {21 for(int i=1; i<=n; i++)22 {23 lefts[i] = i-1;24 rights[i] = (i+1)%(n+1);25 }26 lefts[0] = n;27 rights[0] = 1;28 int re = 0;29 while(m--)30 {31 int op;32 scanf("%d",&op);33 if(op==4)34 {35 re = !re;36 continue;37 }38 int x,y;39 scanf("%d%d",&x,&y);40 41 if(op==3&&rights[y]==x) swap(x,y);42 if(op!=3&&re) op = 3 - op;43 if(op==1&&lefts[y]==x) continue;44 if(op==2&&rights[y]==x) continue;45 46 int lx = lefts[x],rx = rights[x],ly =lefts[y],ry = rights[y];47 if(op==1)48 {49 link(lx,rx);50 link(ly,x);51 link(x,y);52 }53 else if(op==2)54 {55 link(lx,rx);56 link(x,ry);57 link(y,x);58 }59 else if(op==3) {60 61 if(rights[x]==y) {62 link(lx,y);63 link(y,x);64 link(x,ry);65 }66 else {67 link(lx,y);68 link(y,rx);69 link(ly,x);70 link(x,ry);71 }72 }73 }74 int b = 0;75 long long ans = 0;76 for(int i=1; i<=n; i++)77 {78 b = rights[b];79 if(i%2==1)80 ans +=(long long)b;81 }82 if(re)83 {84 ans = (long long)n*(long long)(n+1)/2 - ans;85 }86 printf("Case %d: %lld\n",kase++,ans);87 }88 return 0;89 }
Uva 12657 双向链表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。