CodeForces 669D

链接: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 <bits/stdc++.h>
 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         else
29         {
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("
");
50     return 0;
51 }