锐客网

  1. 首页 > it技术 > >

链表---移动盒子（双向链表）

题目：移动盒子UVa 12657
你有一行盒子，从左到右依次编号为1,2,3,…,n。可以执行以下4种指令：
1 x y：表示把盒子x移动到盒子y的左边（如果x已经在y的左边则忽略此指令）。
2 x y：表示把盒子x移动到盒子y的右边（如果x已经在y的右边则忽略此指令）。
3 x y：表示交换盒子x和y的位置。
4：表示反转整条链。
指令保证合法，即x不等于y。
【输入格式】
输入包含不超过10组数据，每组数据第一行为盒子数n和指令m，以下m行每行包含一条指令。
【输出格式】
每组数据输出一行，即所有奇数位置的盒子编号之和。位置从左到右编号为1~n。
【输入样例】
6 4
1 1 4
2 3 5
3 1 6
4
6 3
1 1 4
2 3 5
3 1 6
100000 1
4
【输出样例】
case 1: 12
case 2: 9
case 3: 2500050000
[作者：大1234草]
原文：(https://blog.csdn.net/sinat_38816924/article/details/83514484)

【链表---移动盒子（双向链表）】如果是使用数组会超时。
--->Left[i]和Right[i]分别表示编号为i的盒子左边和右边的盒子编号
但是注意了 如果执行了操作4后， 如果操作1 2操作不变的话， 那么操作1就是2，2 就是1（放在左边 + 反转 = 放在右边）
表格（以样例1为例）
输入6个盒子，4条指令
0 1 2 3 4 5 6
Left [i] 1 0 1 2 3 4 5
Right [i] 6 2 3 4 5 6 0
盒变化
盒子0 1 2 3 4 5 6
1 1 4
盒子1 2 3 1 4 5 6
2 3 5
盒子2 2 1 4 5 3 6
3 1 6
盒子3 2 6 4 5 3 1
4
盒子4 1 3 5 4 6 2
书上代码：
#include #include #include #define N 100001 using namespace std; int Left[N],Right[N]; //左右盒子编号 int n; int swap(int a,int b){//交换两个值 int t; t=a; a=b; b=t; return a,b; } //双向链表的一个比较实用的函数 void link(int l,int r){//连接两个节点 Right[l]=r; Left[r]=l; } int main() { int m,kase=0; //n,m分别为盒子个数和指令条数 while(scanf("%d%d",&n,&m)==2){//读取两个整形值到n和m for(int i=1; i<=n; i++){ Left[i]=i-1; Right[i]=(i+1)%(n+1); } Right[0]=1; Left[0]=n; int op,X,Y,inv=0; //inv表示操作4是否执行 while(m--){ scanf("%d",&op); if(op==4)inv=!inv; //翻转整条链 else { scanf("%d%d",&X,&Y); if(op==3&&Right[Y]==X)swap(X,Y); // !为了转换成同一种情况来处理 if(op!=3&&inv)op=3-op; if(op==1&& X==Left[Y]) continue; if(op==2&& X==Right[Y])continue; 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); }//X的左右连起来，按照链的顺序来写可能更加清晰 else if(op==3){ if(Right[X]==Y){ link(LX,Y); link(Y,X); link(X,RY); } else{ link(LX,Y); link(Y,RX); link(LY,X); link(X,RY); } } } } //奇数位置盒子编号之和 int b=0; long long ans=0; for(int i=1; i<=n; i++){ b=Right[b]; //向右推移 if(i%2==1)ans+=b; } if(inv && n%2==0) ans=(long long)n*(n+1)/2-ans; // printf("case %d: %lld\n",++kase,ans); //输出 } return 0; }

大佬的代码：
链表解法:::作者：不羡
#include using namespace std; int bigflag = 0; struct node { int x; node * next; }; int main() { int n, m; while (cin >> n >> m) { node *head = new node; ; head->x = 1; node *temp = head; for (int i = 2; i <= n; i++) { node *p = new node; p->x = i; temp->next = p; temp = p; } temp->next = NULL; int a, b, c; for (int flag = 0; flag < m; flag++) { cin >> a; if (a == 1) { cin >> b >> c; int i, j; node *zz = head; node *hh = head; if (zz->x == b)i = 0; else { for (i = 1; i < n; i++) { if (zz->next->x == b)break; zz == zz->next; } }//真实位置i+1,要单独考虑在头的情况； if (hh->x == c)j = 0; else { for (j = 1; j < n; j++) { if (hh->next->x == c)break; hh = hh->next; } }//真实情况j+1; if (i + 1 + 1 != j + 1) { if (i == 0) { head = zz->next; zz->next = hh->next; hh->next = zz; } else { node *s = new node; s = zz->next; zz->next = zz->next->next; s->next = hh->next; hh->next = s; } } node * w = head; } else if (a == 2) { cin >> b >> c; int i, j; node *zz = head; node *hh = head; if (zz->x == b)i = 0; else { for (i = 1; i < n; i++) { if (zz->next->x == b)break; zz == zz->next; } }//真实位置i+1,要单独考虑在头的情况； for (j = 1; j < n; j++) { if (hh->x == c)break; hh = hh->next; } if (i + 1 != j + 1) { if (i == 0) { head = zz->next; zz->next = hh->next; hh->next = zz; } else { node *p = new node; p = zz->next; zz->next = zz->next->next; p->next = hh->next; hh->next = p; } } } else if (a == 3) { cin >> b >> c; node *zz = head; node *hh = head; int i, j; for (i = 1; i < n; i++) { if (zz->x == b)break; zz = zz->next; } for (j = 1; j < n; j++) { if (hh->x == c)break; hh = hh->next; } int temp; temp = zz->x; zz->x = hh->x; hh->x = temp; node * e = head; int sum = 0; } else if (a == 4) { node *mid = head; node *tail = head->next; for (int i = 1; i < n; i++) { node *pre = tail->next; tail->next = mid; mid = tail; tail = pre; } node *mm = mid; head = mid; } } node *mark = head; int sum = 0; for (int i = 1; i <= n; i = i + 2) { sum = sum + mark->x; mark = mark->next->next; } cout << "Case "<

    推荐阅读


    上一篇：相逢一笑

    下一篇：2020.6.9|2020.6.9 星期二 （207篇）