首页 > 代码库 > UVA 12657 Boxes in a Line( 双向链表 )
UVA 12657 Boxes in a Line( 双向链表 )
12657 Boxes in a Line
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
模拟双向链表
逆转的时候记录次数
（逆转之后的操作1相当于2,2相当于1）
注意一下细节就可以过了~
#include<bits/stdc++.h>using namespace std;const int N = 100010;const double PI = acos(-1.0);const double eps = 1e-6;typedef long long LL;typedef pair<double,double> pii;#define X first#define Y secondint n , m , L[N] , R[N] , tag ;void init() { tag = 0 ; for( int i = 0 ; i <= n ; ++i ){ L[i] = i-1 , R[i] = i + 1 ; }}void test() { for( int i = 0 ; i <= n ; ++i ) cout << L[i] <<‘ ‘ << R[i] << endl ;}void changeNext( int x , int y ) { R[ L[x] ] = y ; L[ R[y] ] = x ; L[y] = L[x] ; R[x] = R[y] ; L[x] = y ; R[y] = x ;}void move_l( int x , int y ) { if( R[x] == y || x == y ) return ; R[ L[x] ] = R[x]; L[ R[x] ] = L[x]; L[x] = L[y]; R[ L[y] ] = x ; L[y] = x ; R[x] = y ;}void move_r( int x , int y ) { if( L[x] == y || x == y ) return ; R[ L[x] ] = R[x]; L[ R[x] ] = L[x]; R[x] = R[y]; L[ R[y] ] = x ; R[y] = x ; L[x] = y ;}void change( int x , int y ) { if( x == y ) return ; if( R[x] == y ){ changeNext(x,y); return ; } if( R[y] == x ) { changeNext(y,x); return ; } int tmp , l1 , r1 , l2 , r2 ; l1 = L[x] , r1 = R[x] , l2 = L[y] , r2 = R[y]; tmp = L[x] , L[x] = L[y] , L[y] = tmp ; tmp = R[x] , R[x] = R[y] , R[y] = tmp ; R[l1] = y , L[r1] = y ; R[l2] = x , L[r2] = x ;}LL cal( int tag ) { LL res = 0 ; int cnt = 1 ; if( tag && !(n&1) ) tag = 0 ; else tag = 1 ; for( int i = R[0] ; i <= n ; i = R[i] ){ if( tag && (cnt&1) ) res += i ; if( !tag && !(cnt&1) ) res += i ; cnt++; } return res;}void Run() { init(); while(m--){ int op , x , y ; scanf("%d",&op); if( op == 1 ) { scanf("%d%d",&x,&y); if( !tag ) move_l(x,y); else move_r(x,y); } else if( op == 2 ) { scanf("%d%d",&x,&y); if( !tag ) move_r(x,y); else move_l(x,y); } else if( op == 3 ) { scanf("%d%d",&x,&y); change(x,y); } else tag^=1;// test();cout << endl ; } printf("%lld\n",cal(tag));}int main() {// freopen("in.txt","r",stdin); int _ , cas = 1 ; while( scanf("%d%d",&n,&m) != EOF ) { printf("Case %d: ",cas++); Run(); }}
UVA 12657 Boxes in a Line( 双向链表 )