首页 > itarticle > uva

uva

admin 1月 18, 2021 0

传送门：UVA-12657 Boxes in a Line
Description

You have n boxes in a line on the table numbered 1 . . . n from left to right. Your task is to simulate 4
kinds of commands:
• 1 X Y : move box X to the left to Y (ignore this if X is already the left of Y )
• 2 X Y : move box X to the right to Y (ignore this if X is already the right of Y )
• 3 X Y : swap box X and Y
• 4: reverse the whole line.
Commands are guaranteed to be valid, i.e. X will be not equal to Y. For example, if n = 6, after executing 1 1 4, the line becomes 2 3 1 4 5 6. Then after executing 2 3 5, the line becomes 2 1 4 5 3 6. Then after executing 3 1 6, the line becomes 2 6 4 5 3 1. Then after executing 4, then line becomes 1 3 5 4 6 2.

Input

There will be at most 10 test cases. Each test case begins with a line containing 2 integers n, m (1 ≤ n, m ≤ 100, 000). Each of the following m lines contain a command.

Output

For each test case, print the sum of numbers at odd-indexed positions. Positions are numbered 1 to n from left to right.

Sample Input

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
Sample Output
Case 1: 12
Case 2: 9
Case 3: 2500050000

Thinking
用数组模拟双向链表，要注意当X、Y相邻的时候的处理

Code

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
 

int pre[100010],next[100010],head,last;
void (int n)
{
  next[0] = 1;
 for (int i = 1;i <= n; ++i){

       next[i] = i+1;
       pre[i] = i-1;
    }
    pre[n+1] = n;
    head = 0;
    last = n+1;
}
void move(int a,int b,int com,int n)
{
 int x = a,y = b;

   if (com == 1){
      next[pre[x]] = next[x];
      pre[next[x]] = pre[x];
       next[x] = y;
     pre[x] = pre[y];
     next[pre[y]] = x;
        pre[y] = x;
  }
    else if (com == 3){
        int p = pre[x],n = next[x];
     if (p == y){
            pre[next[x]] = y;
            next[y] = next[x];
           next[x] = y;
         next[pre[y]] = x;
            pre[x] = pre[y];
         pre[y] = x;
          return ;
        }
        if (n == y){
            pre[next[y]] = x;
            next[x] = next[y];
           next[y] = x;
         next[pre[x]] = y;
            pre[y] = pre[x];
         pre[x] = y;
          return ;
        }
        next[pre[x]] = y;
        pre[next[x]] = y;
        pre[next[y]] = x;
        next[pre[y]] = x;
        next[x] = next[y];
       pre[x] = pre[y];
     next[y] = n;
     pre[y] = p;
  }
    else if (com == 2){
        next[pre[x]] = next[x];
      pre[next[x]] = pre[x];
       next[x] = next[y];
       pre[x] = y;
      pre[next[y]] = x;
        next[y] = x;
 }
}
long long get_ans(bool com,int n)
{
   long long ans = 0;
 if (com == true){
      int inter = head;
       for (int i = 1;i <= n; ++i){
            inter = next[inter];
         if (i%2 == 1)  ans += inter;
        }
    }
    else{
       int inter = last;
       for (int i = 1;i <= n; ++i){
            inter = pre[inter];
          if (i%2 == 1)  ans += inter;
        }
    }
    return ans;
}
int main ()
{
 int m,n,cut = 1;
    while (~scanf ("%d%d",&n,&m)){
        int mod,a,b,cnt = 0;
        init(n);
     for (int i = 1;i <= m; ++i){
            scanf ("%d",&mod);
         if (mod == 4){
              cnt++;
           }
            else{
               scanf ("%d %d",&a,&b);
             if (cnt%2 == 1){
                    if (mod == 1) mod = 2;
                  else if (mod == 2) mod = 1;
                    move(a,b,mod,n);
             }
                else   move(a,b,mod,n);
         }
        }
        printf ("Case %d: ",cut++);
        printf ("%lldn",get_ans((cnt+1)%2,n));
 }
    return 0;
}

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能