csuoj 1329: 一行盒子

http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1329

1329: 一行盒子

Time Limit: 1 Sec Memory Limit: 128 MB

Description

你有一行盒子，从左到右依次编号为1, 2, 3,…, n。你可以执行四种指令：
1 X Y表示把盒子X移动到盒子Y左边（如果X已经在Y的左边则忽略此指令）。 2 X Y表示把盒子X移动到盒子Y右边（如果X已经在Y的右边则忽略此指令）。 3 X Y表示交换盒子X和Y的位置。 4 表示反转整条链。
指令保证合法，即X不等于Y。例如，当n=6时在初始状态下执行1 1 4后，盒子序列为2 3 1 4 5 6。接下来执行2 3 5，盒子序列变成2 1 4 5 3 6。再执行3 1 6，得到2 6 4 5 3 1。最终执行4，得到1 3 5 4 6 2。

Input

输入包含不超过10组数据，每组数据第一行为盒子个数n和指令条数m（1<=n,m<=100,000），以下m行每行包含一条指令。

Output

每组数据输出一行，即所有奇数位置的盒子编号之和。位置从左到右编号为1~n。

Sample Input

Sample Output

Case 1: 12
Case 2: 9
Case 3: 2500050000

HINT

Source

湖南省第九届大学生计算机程序设计竞赛

分析：

这道题可以用链表实现，也可以用两个数组模拟。

　　难点在于第四种操作，第四种操作是反转，效果是前后交换了，其实根本不需要操作，只需记录反转的次数就行了。

反转次数为奇数时，flag=1的操作变成flag=2的操作，flag=2的操作变成flag=1的操作，其他的不变。

AC代码：

  1 #include"stdio.h"
  2 #include"string.h"
  3 const int ms=100004;
  4 int left[100004];
  5 int right[100004];
  6 int *tmp1,*tmp2;
  7 inline void link(int a,int b)
  8 {
  9     right[a]=b;
 10     left[b]=a;
 11 }
 12 int main()
 13 {
 14     int n,m,i,j,k,flag,x,y,p=1,cnt,next;
 15     while(scanf("%d%d",&n,&m)!=EOF)
 16     {
 17         for(i=1;i<=n;i++)
 18         {
 19             left[i]=i-1;
 20             right[i]=i+1;
 21         }
 22         right[n]=0;//构成环，方便寻找开始节点和结束节点 
 23         cnt=0;
 24         while(m--)
 25         {
 26             scanf("%d",&flag);
 27             if(flag!=4)
 28                 scanf("%d%d",&x,&y);
 29             else
 30                 cnt++;
 31             if((cnt&1)&&flag<3)
 32                 flag=3-flag;
 33             if(flag==1&&(right[x]!=y))
 34             {
 35                 if(right[y]==x)
 36                 {
 37                     int t1=left[x],t2=right[x],t3=left[y],t4=right[y];
 38                     link(t3,x);
 39                     link(x,y);
 40                     link(y,t2);
 41                 }
 42                 else
 43                 {
 44                     link(left[x],right[x]);
 45                     link(left[y],x);
 46                     link(x,y);
 47                 }
 48             }
 49             else if(flag==2&&right[y]!=x)
 50             {
 51                 if(right[x]==y)
 52                 {
 53                     int t1=left[x],t2=right[x],t3=left[y],t4=right[y];
 54                     link(t1,y);
 55                     link(y,x);
 56                     link(x,t4);    
 57                 }
 58                 else
 59                 {
 60                     link(left[x],right[x]);
 61                     link(x,right[y]);
 62                     link(y,x);
 63                 }
 64             }
 65             else if(flag==3)
 66             {
 67                 if(right[x]==y)
 68                 {
 69                     int t1=left[x],t2=right[x],t3=left[y],t4=right[y];
 70                     link(t1,y);
 71                     link(y,x);
 72                     link(x,t4);
 73                 }
 74                 else if(right[y]==x)
 75                 {
 76                     int t1=left[x],t2=right[x],t3=left[y],t4=right[y];
 77                     link(t3,x);
 78                     link(x,y);
 79                     link(y,t2);
 80                 }
 81                 else{
 82                     int t1=left[x],t2=right[x],t3=left[y],t4=right[y];
 83                     link(t1,y);
 84                     link(y,t2);
 85                     link(t3,x);
 86                     link(x,t4);
 87                 }
 88             }
 89         }
 90         long long ans=0;
 91         if(cnt&1)
 92         {
 93             tmp2=right;
 94             tmp1=left;
 95         }
 96         else
 97         {
 98             tmp2=left;
 99             tmp1=right;
100         }
101         for(i=1;i<=n;i++)
102         {
103             if(tmp2[i]==0)
104             {
105                 for(k=1;i;i=tmp1[i],k++)
106                     if(k&1)
107                         ans+=i;
108                 printf("Case %d: %lld
",p++,ans);
109                 break;
110             }
111         }
112     }
113     return 0;
114 }

View Code

因为反转后，一个数的前面变成后面，后面变成前面。还有就是构成环，方便找到起点和终点。