[noip2016-提高] 玩具谜题

GitHub跳转原题关系图返回列表

把朝向与左右折算成下标 ±1，每条指令模 n 直接跳 s 步，O(n+m) 环形模拟。

OJ: roj

题目 ID: 3638

难度:普及-

标签:模拟python

创建: 2026-10-02 12:08

更新: 2026-10-06 15:51

目录

  1. 题目描述
  2. 思路
  3. 参考代码

题目描述

n 个玩具小人围成一圈，逆时针顺序给出朝向（0 朝内、1 朝外）和职业。从第 1 个小人出发，依次执行 m 条指令：a=0 向左数 s 个，a=1 向右数 s 个，求到达的小人职业。1≤n,m≤1e5，1≤s<n。

思路

朝向与左右共同决定移动方向：a 与当前朝向相异则沿逆时针（下标 +1），相同则顺时针（下标 -1）。环上移动 s 步等价于 (pos ± s) mod n，每条指令 O(1)。

参考代码

Python 版：

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 12:08
# update_at: 2026-10-02 12:12

import sys


def solve() -> None:
    lines = iter(sys.stdin.buffer)
    n, m = map(int, next(lines).split())

    # 朝向与职业按输入顺序读入：下标增大方向就是逆时针方向
    facing = [0] * n
    name = [b""] * n
    for i in range(n):
        f, job = next(lines).split()
        facing[i] = int(f)  # 0 = 朝圈内，1 = 朝圈外
        name[i] = job       # 职业两两不同，按位置存即可

    pos = 0  # 当前所在小人，从第 1 个（下标 0）开始
    for _ in range(m):
        a, s = map(int, next(lines).split())
        # 四种组合合并成一句：朝内时"左"使序号 -1、朝外时 +1，"右"相反，
        # 于是方向只取决于 a（0 左 / 1 右）与朝向是否相同——相异 +1，相同 -1。
        step = 1 if a != facing[pos] else -1
        pos = (pos + step * s) % n  # 环上直走 s 步 = 下标加减后取模

    print(name[pos].decode())


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 15:50
 * update_at: 2026-10-06 15:50
 */

#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 100000 + 10;

int n, m;
int f[MAXN];              // 第 i 个小人的朝向，0 朝圈内，1 朝圈外
char name[MAXN][15];      // 每个小人的职业名

// 把方向折算成下标增减：a 与 f 相异则 +1，相同则 -1
inline int step_dir(int a, int fc) {
    return (a != fc) ? 1 : -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> f[i] >> name[i];
    }

    int pos = 0;  // 从第 1 个读入的小人（下标 0）出发
    for (int i = 0; i < m; ++i) {
        int a, s;
        cin >> a >> s;
        int step = step_dir(a, f[pos]);
        // 环上走 s 步，负数取模后归到 [0, n)
        pos = (pos + step * (s % n) + n) % n;
    }

    cout << name[pos] << '\n';
    return 0;
}