当前位置: 代码迷 >> 综合 >> 例题6-5 UVa12657 双向链表
  详细解决方案

例题6-5 UVa12657 双向链表

热度:66   发布时间:2024-01-16 13:58:50.0

题意:

看白书吧,介绍的很清楚,P144

要点:

好难啊,用两个数组表示双向链表,里面还有很多小技巧,真难,讲不清楚,看书


代码如下:

#include<stdio.h>
#define maxn 100050
int left[maxn], right[maxn];void link(int l, int r)
{right[l] = r;left[r] = l;
}int main()
{int m,n, kase = 0;while (scanf("%d%d", &n, &m) == 2){int i;for (i = 1; i <= n; i++){left[i] = i - 1;right[i] = (i + 1) % (n + 1); //第n个结点的后继指向0}right[0] = 1;left[0] = n;int op, x, y, inv = 0;//inv记录调换次数while (m--){scanf("%d", &op);if (op == 4)  inv = !inv; //记录inv次数else {scanf("%d%d", &x, &y);if (inv&&op != 3)  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(x, y);link(ly, x);}else if (op == 2){link(lx, rx); link(y, x); link(x, ry);}else if (op == 3){if (right[x] == y) { link(lx, y); link(y, x); link(x, ry); }else if (left[x] == y) { link(ly, x); link(x, y); link(y,rx); }else{link(x, ry); link(ly, x);link(lx, y); link(y, rx);}}}}int b = 0;long long ans = 0;for (i = 1; i <= n; i++){b = right[b];if (i % 2 == 1)  ans += b; //奇数加起来}if (inv&&n % 2 == 0) //调转一次且个数为偶数时计入的奇数其实是偶数ans = (long long)n*(n + 1) / 2 - ans;  //总数-偶数和=奇数和printf("Case %d: %lld\n", ++kase, ans);}
}


  相关解决方案