回旋迷宫

题目描述

$n$ 个门 $0,1,\dots,n-1$ 顺时针围成一圈，相邻门距离为 $1$ ，从门 $now$ 出发，行走 $p$ 次。第 $i$ 次沿当前方向走到与当前门距离恰为 $a_i$ 的门停下；方向每 $k$ 次行走翻转一次——第 $1\sim k$ 次顺时针、第 $k+1\sim 2k$ 次逆时针，依次递推，第一次必为顺时针。沿指定方向走距离 $d$ 的落点为 $(x\pm d)\bmod n$ （ $+$ 顺时针、 $-$ 逆时针）， $a_i\ge n$ 时多绕圈不影响落点，求终点门编号。

输入第一行 $n,p,k,now$ ，第二行 $p$ 个整数 $a_i$ ；输出一个整数表示终点门编号。所有数都是 $[0,10000)$ 内的整数。样例输入 1000 3 2 10 / 1 3 2，样例输出 12。

思路

第 $i$ 次行走的方向只由方向块编号 i/k（0 起）的奇偶决定：偶数顺时针、奇数逆时针，与位置无关。环上行走就是模 $n$ 加法，所以给每个 $a_i$ 按方向附上 $\pm$ 号求和得到总位移，输出 $(now + \text{drift}) \bmod n$ 即可，一趟 $O(p)$ 。

参考代码

Python 版：

python

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#!/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 19:41
# update_at: 2026-10-02 19:41

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)      # 门数：门围成一圈，相邻门距离 1
    rounds = next(data)  # 行走次数 p
    k = next(data)      # 每行走 k 次翻转一次前进方向
    now = next(data)    # 起始门
    steps = [next(data) for _ in range(rounds)]  # 每次行走的距离 a_i

    # 第 i 次行走（0 起）落在第 i//k 个方向块：偶数块顺时针 +a，奇数块逆时针 -a。
    # 环上每步只贡献有符号位移，总位移的模就是答案，不必逐步模拟位置。
    drift = sum(a if (i // k) % 2 == 0 else -a for i, a in enumerate(steps))
    print((now + drift) % n)  # Python 的 % 对正除数恒落在 [0, n)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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/**
 * 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 02:11
 * update_at: 2026-10-06 02:11
 */
#include <iostream>
using namespace std;

typedef long long ll;

int main() {
    ll n, p, k, now;
    cin >> n >> p >> k >> now;

    // 环上行走就是模 n 加法：第 i 次行走落在第 (i-1)/k 个方向块，
    // 偶数块顺时针记 +a_i、奇数块逆时针记 -a_i，累加得到带符号总位移。
    ll drift = 0; // 带符号总位移
    for (ll i = 1; i <= p; i++) {
        ll a;
        cin >> a;
        ll block = (i - 1) / k; // 方向块编号，从 0 开始
        if (block % 2 == 0) {
            drift += a; // 顺时针
        } else {
            drift -= a; // 逆时针
        }
    }

    // 总位移可能为负，先加 n 再取模归一到 [0, n)。
    ll ans = ((now + drift) % n + n) % n;
    cout << ans << endl;
    return 0;
}

目录

题目描述

思路

参考代码