链接:http://codeforces.com/contest/669/problem/D

本文链接:http://www.cnblogs.com/Ash-ly/p/5443242.html

题意:

　　给一个数字N,代表有N个人,编号分别为1, 2, 3, ..., N, 围成一个环,有两种操作;

　　1 x 代表把每个人顺时针(x > 0)或者逆时针(x < 0)旋转|x|下.

　　2 代表把第 i 个人和第 i + 1 个人的顺序交换.(i= 1, 3, 5, 7.....)

　　问最后这个圈从第一个位置开始,每个人的编号.

思路:

　　先来看1 和 3, 无论是左移还是右移,还是交换,1 和 3 的相对位置是始终不变的,所以发现在交换的过程中,所有奇数的相对位置是不变的,偶数亦然,那么只需要知道1 和 2 最后的位置,就可以推出来其他数字的位置(1 后面 2 位 就是 3 的位置,以此类推).

代码:

1 #include 
     
       2 using namespace std; 3  4 const int MAXN = 1000000;  5 int arr[MAXN + 7]; 6 int n, q; 7  8 int main() 9 {10     freopen("input.txt", "r", stdin);11     scanf("%d%d", &n, &q);12     int pe1 = 1;13     int pe2 = 2;14     for(int i = 0; i < q; i++)15     {16         int order;17         scanf("%d", &order);18         if(order & 1)19         {20             int x;21             scanf("%d", &x);22             pe1 += x, pe2 += x;23             if(pe1 > n) pe1 %= n;24             if(pe2 > n) pe2 %= n;25             if(pe1 <= 0) pe1 = n - (-pe1) % n;26             if(pe2 <= 0) pe2 = n - (-pe2) % n;27         }28         else29         {30             if(pe1 & 1) pe1++;31             else pe1--;32             if(pe2 & 1) pe2++;33             else pe2--;34         }35     }36     int cnt = n / 2;37     arr[pe1] = 1, arr[pe2] = 2;38     int t1 = 3, t2 = 4;39     while(--cnt)40     {41         pe1 += 2, pe2 += 2;42         if(pe1 > n) pe1 %= n;43         if(pe2 > n) pe2 %= n;44         arr[pe1] = t1, arr[pe2] = t2;45         t2 += 2, t1 += 2;46     }47     for(int i = 1; i <= n; i++)48         printf(i == 1 ? "%d":" %d", arr[i]);49     printf("\n");50     return 0;51 }