By yusijia

Updated:

Contents
  1. 1. 双向链表
  2. 2. 题目(UVa12657)大意：
  3. 3. 分析(转)：

双向链表

  • 转：《算法竞赛入门经典》(第2版) 作者：刘汝佳

题目(UVa12657)大意：

  • 开始有n个盒子按1到n的顺序排列 对这些盒子进行m次操作
  • 操作1，将x放到y前面一个位置；
  • 操作2将x放到y后面的一个位置；
  • 操作3交换x和y的位置；

  • 操作4反转整个序列。求经过m次操作后的所有奇数项的和。

  • 注意：这题如果直接用STL里的链表会超时

分析(转)：

可以先记录好操作之前的x和y两边的结点，然后用link函数按照某种顺序吧它们连接
起来，操作4比较特殊，为了避免一次修改所有元素的指针，此处增加一个标记flag，表
示有没有执行操作4，(如果flag=1时再执行一次操作4，则flag变为0)。这样，当op为
1和2且flag=1时，只需把op变成3-op(注意操作3不受flag的影响)即可，最终输出时要
根据flag的值进行不同处理

提示：
如果数据结构上的某一个操作很耗时，有时可以用加标记的方式处理，而不需要真
的执行那个操作。但同时，改数据结构的所有其他操作都要考虑这个标记

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <cstdio>
#define MAXN 1000
/*#define right ri
#define left le*/  //若不用这个会出现一个错误
using namespace std;

int right[MAXN], left[MAXN];

void link(int x, int y)//通过辅助函数来设置链接关系
{
    right[x] = y;
    left[y] = x;
}

int main()
{
    int n, m, kase = 0;
    while(scanf("%d%d", &n, &m) != EOF){
        for(int i = 1; i <= n; i++){
            left[i] = i - 1;         	//初始化两个链表
            right[i] = (i + 1) % (n + 1);//取模主要是为了让right[n] = 0
        }
        right[0] = 1;
        left[0] = n;   			 //让表循环起来
        int op, x, y, flag = 0;  	//flag作为判断是否翻转的标志

        while(m--){
            scanf("%d", &op);
            if(op == 4)
                flag = !flag;		//其实只是做了个标记，然后把相应操作翻转后的操作，并未翻转
            else{
                scanf("%d%d", &x, &y);
                if(op != 3 && flag)
                    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);
                }
                else if(op == 3){   	//下面x，y相邻的情况要单独考虑
                    if(right[x] == y) {link(lx, y); link(y, x); link(x, ry);}
                    else if(right[y] == x) {link(ly, x); link(x, y); link(y, rx);}
                    else{link(lx, y); link(y, rx); link(ly, x); link(x, ry);}
                }
            }
        }

        int b = 0;
        int ans = 0;
        for(int i = 1; i <= n; i++){//若n为奇数，则翻不翻转转对求奇数项无影响(若翻转，则操作都改成翻转后的相应操作了)
            b = right[b];    		//从0开始找，一直往右边找
            if(i % 2 == 1)		//如果是奇数就把奇数项加起来
                ans += b;
        }
        if(flag && n % 2 == 0)//如果n是偶数且翻转过，则只需改为求偶数项的和
            ans = (1 + n) * n / 2 - ans;//总和减去奇数项的和就是偶数项()
        printf("Case %d: %d\n", ++kase,ans);
    }

    return 0;
}
Contents
  1. 1. 双向链表
  2. 2. 题目(UVa12657)大意：
  3. 3. 分析(转)：