本文主要是介绍csu1329(双向链表)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。
代码如下：
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<string>
#include<vector>
#define N 100005
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 10e-6
int Left[N],Right[N];
using namespace std;
void link(int x,int y)
{Right[x] = y;Left[y] = x;
}
int main()
{int n,m,cas = 1;while(scanf("%d%d",&n,&m) != EOF){int flag = 0;Right[0] = 1;Left[n+1] = n;int i;for(i = 1; i <= n; i++)Left[i] = i-1,Right[i] = i+1;while(m--){int op;scanf("%d",&op);if(op == 4) {flag = !flag;continue;}if(op < 3 && flag) op = 3-op;int x,y;scanf("%d%d",&x,&y);if(op == 1 && Right[x] == y) continue;if(op == 2 && Right[y] == x) continue;if(Right[y] == x && op == 3) swap(x,y);int lx = Left[x],rx = Right[x],ly = Left[y],ry = Right[y];if(op == 1){link(lx,rx);link(ly,x);link(x,y);}else if(op == 2){link(lx,rx);link(y,x);link(x,ry);}else {if(rx == y) {link(lx,y);link(y,x);link(x,ry);}else{link(lx,y);link(y,rx);link(ly,x);link(x,ry);}}}long long ans = 0;i = Right[0];int cnt = 0;while(1){if(cnt%2 == 0)ans += i;cnt++;i = Right[i];if(i == n+1) break;}if(flag && n%2 == 0) ans = 1LL*(n+1)*n/2 - ans;printf("Case %d: %lld\n",cas++,ans);}return 0;
}
这篇关于csu1329(双向链表)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
