首页 > 代码库 > UVa12657 - Boxes in a Line(数组模拟链表)

UVa12657 - Boxes in a Line(数组模拟链表)

2024-07-13 18:39:42   223人阅读

题目大意

你有一行盒子，从左到右依次编号为1, 2, 3,…, n。你可以执行四种指令：

1 X Y表示把盒子X移动到盒子Y左边（如果X已经在Y的左边则忽略此指令）。
2 X Y表示把盒子X移动到盒子Y右边（如果X已经在Y的右边则忽略此指令）。
3 X Y表示交换盒子X和Y的位置。
4 表示反转整条链。

盒子个数n和指令条数m（1<=n,m<=100,000）

题解

用数组来模拟链表操作，对于每个节点设置一个前驱和后继。

1操作是把x的前驱节点和x的后继节点连接，y节点的前驱和x节点连接，x节点和y节点连接。

2，3，的做法和1差不多

4操作由于操作两次就等于没有操作，所以只要判断它最终是不是执行了奇数次，如果是就把n个节点的前驱和后继交换下。还有就是在执行1,2的时候如果之前4操作了奇数次，那么1,2两个执行的操作分别是2操作和1操作。

代码：

  1 #include <iostream>  2 #include <algorithm>  3 #include <cstdio>  4 #include <cstring>  5 #include <utility>  6 #include <vector>  7 #include <queue>  8 using namespace std;  9 #define INF 0x3f3f3f3f 10 #define maxn 111111 11 typedef long long LL; 12 int nxt[maxn], pre[maxn]; 13 void init(int n) 14 { 15     for (int i = 1; i <= n;i++) 16     { 17         pre[i] = i - 1; 18         nxt[i] = i + 1; 19     } 20     nxt[n] = 0; 21     nxt[0] = 1; pre[0] = n; 22 } 23 void link(int l, int r) 24 { 25     pre[r] = l; nxt[l] = r; 26 } 27 int main() 28 { 29     int n, m,kase=0; 30     while (scanf("%d%d", &n, &m) != EOF) 31     { 32         int rev = 0; 33         init(n); 34         while (m--) 35         { 36             int op, x, y; 37             scanf("%d", &op); 38             if (op == 4) rev = 1 - rev; 39             else 40             { 41                 scanf("%d%d", &x, &y); 42                 if ((op == 1 || op == 2) && rev) op = 3 - op; 43                 if (op == 3&&nxt[y] == x) swap(x, y); 44                 int lx, rx, ly, ry; 45                 lx = pre[x]; rx = nxt[x]; 46                 ly = pre[y]; ry = nxt[y]; 47                 if (op == 1) 48                 { 49                     if (nxt[x]==y) continue; 50                     link(lx, rx); 51                     link(ly, x); 52                     link(x, y); 53                                                              54                 } 55                 else if (op == 2) 56                 { 57                     if (nxt[y]==x) continue; 58                     link(lx, rx); 59                     link(x, ry); 60                     link(y, x); 61                 } 62                 else 63                 { 64                     if (nxt[x] == y) 65                     { 66                         link(lx, y); 67                         link(y, x); 68                         link(x, ry); 69                     } 70                     else 71                     { 72                         link(lx, y); 73                         link(y, rx); 74                         link(ly, x); 75                         link(x, ry); 76                     } 77                 } 78             } 79         } 80         if (rev) 81         { 82             for (int i = 1; i <= n; i++) swap(pre[i], nxt[i]); 83         } 84         int pos; 85         for (int i = 1; i <= n; i++) 86         { 87             if (pre[i] == 0) 88             { 89                 pos = i; 90                 break; 91             } 92         } 93         int cnt = 1; 94         LL ans = 0; 95         while (pos!=0) 96         { 97             if (cnt & 1) ans += pos; 98             pos = nxt[pos]; 99             cnt++;100         }101         printf("Case %d: %I64d\n", ++kase,ans);102     }103     return 0;104 }
View Code


联系
我们