Link

传送门

Problem

Little Artem is fond of dancing. Most of all dances Artem likes rueda — Cuban dance that is danced by pairs of boys and girls forming a circle and dancing together.

More detailed, there are n pairs of boys and girls standing in a circle. Initially, boy number 1 dances with a girl number 1, boy number 2 dances with a girl number 2 and so on. Girls are numbered in the clockwise order. During the dance different moves are announced and all pairs perform this moves. While performing moves boys move along the circle, while girls always stay at their initial position. For the purpose of this problem we consider two different types of moves:

  1. Value x and some direction are announced, and all boys move x positions in the corresponding direction.
  2. Boys dancing with even-indexed girls swap positions with boys who are dancing with odd-indexed girls. That is the one who was dancing with the girl 1 swaps with the one who was dancing with the girl number 2, while the one who was dancing with girl number 3 swaps with the one who was dancing with the girl number 4 and so one. It’s guaranteed that n is even.

Your task is to determine the final position of each boy.

Mean

一个数组,长度为N,初始化为1~N。有Q次操作,操作有两种类型,一种是交换奇偶位置上的数,另一种是所有数循环往右位移x个。

Analysis

分析发现所有奇数的变化是相同的,所有偶数的变化时相同的,这样只要求一个偶数一个奇数最终的位置,其他的都可以知道了。具体看代码吧。

Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1024000;
int N, Q;
int ans[maxn];

int main() {
    scanf("%d%d", &N, &Q);
    int pos1 = 0, pos2 = 1;
    for(int i = 1; i <= Q; ++i) {
        int type, d;
        scanf("%d", &type);
        if(type == 1) {
            scanf("%d", &d);
            pos1 = (pos1 + d + N) % N;
            pos2 = (pos2 + d + N) % N;
        } else {
            pos1 ^= 1;
            pos2 ^= 1;
        }
    }
    for(int i = 1; i <= N; ++i) {
        if(i % 2) ans[(pos1+i-1)%N] = i;
        else ans[(pos2+i-2)%N] = i;
    }
    for(int i = 0; i < N; ++i)
        printf("%d ", ans[i]);
    return 0;
}

欢迎留言