✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线200+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

360-2026.04.03

1. 环街采购

问题描述

商业街上有 个补给点，编号为 。

如果 小基 去第 个补给点采购一次，就会拿到 个餐包。

她下一次去哪里，不是自己随便选，而是由当前手里的餐包总数决定：

• 如果此时手里有 个餐包，
• 那么下一次就会去编号为 的补给点继续采购。

一开始，小基 手里没有餐包。

请你计算，在连续采购 次之后，她一共会拿到多少个餐包。

输入格式

第一行输入两个正整数 。

第二行输入 个正整数 ，表示每个补给点一次能拿到的餐包数量。

输出格式

输出一个整数，表示连续采购 次后的餐包总数。

样例输入

3 4
1 2 3

样例输出

6

数据范围

样例	解释说明
样例 1	初始有 个餐包，先去 号点拿到 个；之后去 号点拿到 个，总数变成 ；再去 号点拿到 个；最后去 号点拿到 个，所以答案是 。

题解

这道题表面在问“买了多少个餐包”，真正决定过程的却只有一件事：

• 当前餐包总数对 取模以后是多少。

因为下一次去的补给点是：

如果当前会去第 个补给点，那么这一步会发生两件事：

1. 总数增加 。
2. 下一次会去的新补给点变成：

于是我们可以把每个补给点编号 看成一个状态，得到一张只有 个点的函数图：

• 从 出发，一定会走到 。
• 走这条边时，贡献的权值就是 。

初始状态是 ，题目要的就是：

• 从状态 出发，沿着这张图走 步，边权和是多少。

函数图的路径有一个标准性质：

• 先走一段不重复的前缀；
• 然后进入一个环；
• 之后就一直在环里循环。

所以我们只要把“前缀”和“环”拆出来，就能在 时间内算完。

具体做法是：

1. 用 first[i] 记录状态 第一次出现是在第几步。
2. 用 prefix[k] 记录前 次采购后的餐包总数。
3. 从状态 开始不断模拟：
   • 如果当前状态没见过，就继续走；
   • 如果当前状态已经见过，说明找到了环；
   • 如果还没进环就已经走满了 步，直接输出答案。

假设我们在第 step 步再次来到状态 cur，并且它第一次出现是在第 start 步，那么：

• 前缀长度是 start
• 环长是 step - start
• 一整个环的贡献是：

此时还剩下 m - start 步没有处理：

• 先整环跳若干次；
• 再处理最后不足一个整环的那一小段。

这样就不用真的模拟到 次了。

复杂度分析

• 每个状态最多第一次访问一次，所以找前缀和找环总共只会处理 个状态。
• 后面的整环跳转只需要几次算术运算。

总时间复杂度是 ，空间复杂度是 。

参考代码

• Python

import sys

input = lambda: sys.stdin.readline().strip()


def solve():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))

    # first[i] 记录状态 i 第一次在第几步出现，-1 表示还没有出现过。
    first = [-1] * n
    # prefix[k] 表示前 k 次采购后的总餐包数。
    prefix = [0]

    cur = 0
    step = 0

    # 最多只会在进入环之前访问每个状态一次。
    while first[cur] == -1 and step < m:
        first[cur] = step
        gain = a[cur]
        prefix.append(prefix[-1] + gain)
        cur = (cur + gain) % n
        step += 1

    # 如果在进入环之前就已经走满了 m 步，答案就是当前前缀和。
    if step == m:
        print(prefix[step])
        return

    start = first[cur]
    cycle_len = step - start
    cycle_sum = prefix[step] - prefix[start]

    remain = m - start
    whole = remain // cycle_len
    extra = remain % cycle_len

    ans = prefix[start] + whole * cycle_sum
    ans += prefix[start + extra] - prefix[start]
    print(ans)


if __name__ == "__main__":
    solve()

• Cpp

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

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

    int n;
    long long m;
    cin >> n >> m;

    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // first[i] 记录状态 i 第一次出现的步数。
    vector<long long> first(n, -1);
    // prefix[k] 记录前 k 次采购后的总餐包数。
    vector<long long> prefix(1, 0);

    int cur = 0;
    long long step = 0;

    while (first[cur] == -1 && step < m) {
        first[cur] = step;
        long long gain = a[cur];
        prefix.push_back(prefix.back() + gain);
        cur = static_cast<int>((cur + gain) % n);
        ++step;
    }

    if (step == m) {
        cout << prefix[step] << '\n';
        return 0;
    }

    long long start = first[cur];
    long long cycleLen = step - start;
    long long cycleSum = prefix[step] - prefix[start];

    long long remain = m - start;
    long long whole = remain / cycleLen;
    long long extra = remain % cycleLen;

    long long ans = prefix[start] + whole * cycleSum;
    ans += prefix[start + extra] - prefix[start];

    cout << ans << '\n';
    return 0;
}

• Java

import java.io.InputStream;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);

        int n = fs.nextInt();
        long m = fs.nextLong();

        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = fs.nextLong();
        }

        // first[i] 记录状态 i 第一次出现在哪一步。
        int[] first = new int[n];
        Arrays.fill(first, -1);
        // 在进入环之前最多访问 n 个状态，所以开到 n + 1 就够了。
        long[] prefix = new long[n + 1];

        int cur = 0;
        int step = 0;

        while (first[cur] == -1 && step < m) {
            first[cur] = step;
            long gain = a[cur];
            prefix[step + 1] = prefix[step] + gain;
            cur = (int) ((cur + gain) % n);
            step++;
        }

        if (step == m) {
            System.out.println(prefix[step]);
            return;
        }

        int start = first[cur];
        long cycleLen = step - start;
        long cycleSum = prefix[step] - prefix[start];

        long remain = m - start;
        long whole = remain / cycleLen;
        int extra = (int) (remain % cycleLen);

        long ans = prefix[start] + whole * cycleSum;
        ans += prefix[start + extra] - prefix[start];

        System.out.println(ans);
    }

    private static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0;
        private int len = 0;

        FastScanner(InputStream is) {
            in = is;
        }

        private int read() throws Exception {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) {
                    return -1;
                }
            }
            return buffer[ptr++];
        }

        long nextLong() throws Exception {
            int c;
            do {
                c = read();
            } while (c <= 32);

            long sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }

            long val = 0;
            while (c