P1563. 玩具谜题

发表于 分类于 阅读次数： Waline： 本文字数： 382 阅读时长 ≈ 1 分钟

考点

  • 模拟

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>

using namespace std;

const int LEN = 1e5 + 10;

struct Node
{
    string name_;
    int forward_;
} arr[LEN];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i].forward_ >> arr[i].name_;
    }
    int idx = 0, f, len;
    while (m--)
    {
        cin >> f >> len;
        if (arr[idx].forward_ ^ f)
        {
            idx = (idx + len) % n;
        }
        else
        {
            idx = (idx - len + n) % n;
        }
    }
    cout << arr[idx].name_;
    return 0;
}

思路

每个人都有朝向和名字，自然用结构体Node来保存

根据题意得知，结构体数组的下标从小到大遍历是为逆时针序，从大到小遍历是为顺时针序

朝内圈记为0，朝外圈记为1；向左走记为0，向右走记为1

接下来分析遍历走向：

  • 朝内圈的小人向左走，是为顺时针，有0 ^ 0 = 0
  • 朝内圈的小人向右走，是为逆时针，有0 ^ 1 = 1
  • 朝外圈的小人向左走，是为逆时针，有1 ^ 0 = 1
  • 朝外圈的小人向右走，是为顺时针，有1 ^ 1 = 0

所以每次判断遍历走向时，将当前所处的小人内外圈方向与左右方向异或即可；为0则从大到小遍历，为1则从小到大遍历

假设当前共n=6个数，下标idx范围为0~5，每次需要走len步；且题目规定len小于n

从小到大遍历可以得到公式：\(idx=\left( idx+len \right) \%n\)

从大到小遍历可以得到公式：\(idx=\left( idx-len+n \right) \%n\)，之所以加上n是处理负数时的情况