首页 > 代码库 > Uva 12657 移动盒子(双向链表)
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的右边。
1 #include <bits/stdc++.h> 2 const int maxn = 100000 + 7; 3 int n, left[maxn], right[maxn]; 4 void link(int L, int R){//第一个参数是 L,第二个是R, 5 right[L] = R; 6 left[R] = L; 7 } 8 int main() 9 { 10 int m, kase = 0; 11 while(scanf("%d %d", &n, &m) == 2){ 12 for(int i = 1; i <= n; i++){ 13 left[i] = i -1; 14 right[i] = (i+1) % (n+1); 15 } 16 right[0] = 1;//注意0右边是1 左边是 n 17 left[0] = n; 18 int op, X, Y, inv = 0; 19 while(m--){ 20 scanf("%d", &op); 21 if(op == 4) inv = !inv; 22 else { 23 scanf("%d%d",&X, &Y); 24 if(op == 3 && right[Y] == X) 25 std::swap(X,Y); 26 if(op != 3 && inv) op = 3 - op; 27 if(op == 1 && X == left[Y]) continue; 28 if(op == 2 && X == right[Y]) continue; 29 30 int LX = left[X], RX = right[X], LY = left[Y], RY = right[Y]; 31 if(op == 1){ 32 link(LX,RX); link(LY,X); link(X,Y); 33 } 34 else if(op == 2){ 35 link(LX,RX); link(Y,X); link(X,RY); 36 } 37 else if(op == 3){ 38 if(right[X] == Y){ 39 link(LX,Y); link(Y,X); 40 link(X,RY); 41 } 42 else { 43 link(LX,Y); 44 link(Y,RX); 45 link(LY,X); 46 link(X,RY); 47 } 48 } 49 } 50 } 51 int b = 0; 52 long long ans = 0; 53 for(int i = 1; i <= n; i++){ 54 b = right[b]; 55 if(i % 2 == 1) ans += b; 56 } 57 if(inv && n % 2 == 0) ans = (long long) n * (n+1)/2 - ans; 58 printf("Case %d: %lld\n", ++kase, ans); 59 } 60 }
Uva 12657 移动盒子(双向链表)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。