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 表示反转整条链。

分析：

从操作1，2来看，需要有一个数据结构，记录每个盒子左边和右边是什么。

操作4如果真的模拟复杂度较高也比较麻烦，可以考虑建一个标记，表示有没执行过操作4

但是注意了如果执行了操作4后，如果操作1 2操作不变的话，那么操作1就是2，2 就是1（放在左边 + 反转 = 放在右边）

双向链表有一个比较实用的函数

意思就是将L,R两个元素相连， L在R的左边， R在L的右边。

 #include <bits/stdc++.h>

 const int maxn =   + ;

 int n, left[maxn], right[maxn];

 void link(int L, int R){//第一个参数是 L，第二个是R，

     right[L] = R;

     left[R] = L;

 }

 int main()

 {

     int m, kase = ;

     while(scanf("%d %d", &n, &m) == ){

         for(int i = ; i <= n; i++){

             left[i] = i -;

             right[i] = (i+) % (n+);

         }

         right[] = ;//注意0右边是1 左边是 n

         left[] = n;

         int op, X, Y, inv = ;

         while(m--){

             scanf("%d", &op);

             if(op == ) inv = !inv;

             else {

                 scanf("%d%d",&X, &Y);

                 if(op ==  && right[Y] == X)

                    std::swap(X,Y);

                 if(op !=  && inv) op =  - op;

                 if(op ==  && X == left[Y]) continue;

                 if(op ==  && X == right[Y]) continue;

                 int LX = left[X], RX = right[X], LY = left[Y], RY = right[Y];

                 if(op == ){

                     link(LX,RX); link(LY,X); link(X,Y);

                 }

                 else if(op == ){

                     link(LX,RX); link(Y,X); link(X,RY);

                 }

                 else if(op == ){

                     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 = ;

         long long ans = ;

         for(int i = ; i <= n; i++){

             b = right[b];

             if(i %  == ) ans += b;

         }

         if(inv && n %  == ) ans = (long long) n * (n+)/ - ans;

         printf("Case %d: %lld\n", ++kase, ans);

     }

 }

巴特西

Uva 12657 移动盒子（双向链表）

题意：

分析：

最新文章

热门文章