🔗刷题网址: bishipass.com

27届实习提前批秋招汇总，持续更新，建议收藏，欢迎分享https://docs.qq.com/smartsheet/DRHVEc05MbE5CYUZa?tab=sc_JGxFAj

360-2026.04.03

1. 环街采购

问题描述

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

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

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

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

一开始，LYA 手里没有餐包。

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

输入格式

第一行输入两个正整数 。

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

输出格式

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

样例输入

3 4
1 2 3

样例输出

6

数据范围

• >
• >
• >

题解

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

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

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

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

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()


defsolve():
    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] == -1and 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>
usingnamespacestd;

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

int n;
longlong m;
cin >> n >> m;

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

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

int cur = 0;
longlong step = 0;

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

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

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

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

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

cout << ans << '\n';
return0;
}

• >
  Java

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

publicclassMain{
publicstaticvoidmain(String[] args)throws Exception {
        FastScanner fs = new FastScanner(System.in);

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

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

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

privatestaticclassFastScanner{
privatefinal InputStream in;
privatefinalbyte[] buffer = newbyte[1 << 16];
privateint ptr = 0;
privateint len = 0;

        FastScanner(InputStream is) {
            in = is;
        }

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

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

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

long val = 0;
while (c > 32) {
                val = val * 10 + (c - '0');
                c = read();
            }
return val * sign;
        }

intnextInt()throws Exception {
return (int) nextLong();
        }
    }
}

2. 积分领奖台

问题描述

校运动会结束后，老师要根据所有比赛的前三名统计总积分。

一共有  个班级，编号为 。一共进行了  场比赛。对于每一场比赛：

• >
  第一名获得  分；
• >
  第二名获得  分；
• >
  第三名获得  分。

现在已经给出了每一场比赛的冠军、亚军、季军班级编号。请你按总积分统计整个运动会的冠、亚、季军班级。

排名规则采用“并列占位”：

• >
  如果多个班级积分相同，它们共享同一个名次；
• >
  下一个名次要跳过被并列占掉的位置。

例如：

• >
  如果有两个班级并列第一，
• >
  那么下一个名次直接是第三，没有第二。

输出时：

• >
  同一名次如果有多个班级，按班级编号从小到大输出；
• >
  如果某个名次不存在，输出 -1。

输入格式

第一行输入两个正整数 ，表示班级数和比赛场数。

第二行输入  个正整数，表示每场比赛的冠军班级编号。

第三行输入  个正整数，表示每场比赛的亚军班级编号。

第四行输入  个正整数，表示每场比赛的季军班级编号。

输入保证：

• >
  班级编号都在  到  之间；
• >
  每一场比赛的冠军、亚军、季军互不相同。

输出格式

共输出三行：

• >
  第一行输出冠军班级编号；
• >
  第二行输出亚军班级编号；
• >
  第三行输出季军班级编号。

若同一名次有多个班级，则按班级编号从小到大、用空格分隔输出。

若该名次不存在，则输出 -1。

样例输入

4 3
1 2 1
2 3 4
3 4 2

样例输出

1 2
-1
3 4

数据说明

• >
  班级编号在  到  内；
• >
  每场比赛的冠军、亚军、季军互不相同；
• >
  需要统计所有班级，包括没有拿到任何积分的班级。

题解

这道题分成两步：

1. 先把每个班级的总积分统计出来；
2. 再按照“并列占位”的规则找出第 、第 、第  名。

第一步很直接。

我们开一个 score 数组：

• >
  冠军加 ；
• >
  亚军加 ；
• >
  季军加 。

扫完全部比赛以后，每个班级的最终积分就都出来了。

真正容易写错的是第二步。

题目用的不是“稠密排名”，而是标准竞赛排名：

• >
  若有两个人并列第一，那么下一名是第三；
• >
  若有三个人并列第二，那么下一名是第五。

所以不能只按“第几个不同分数”去理解名次，必须按“前面一共站了多少个班级”来推进名次。

一个自然做法是：

1. 按积分把班级分组；
2. 分数高的组排在前面；
3. 设当前这一组的名次是 rank：
• >
  这一整组都属于 rank；
• >
  下一组的名次变成 rank + 当前组人数。

这样就正好符合题目的并列占位规则。

还有一个细节一定不能漏：

• >
  没拿到任何积分的班级，也仍然要参加排名。

否则当只有少数几个班级拿分时，你会把后面的名次算错。

例如只有一个班级得了  分、一个班级得了  分，剩下所有班级都是  分，那么这些  分班级其实共同排在第三名。

#复杂度分析

• >
  统计积分是 。
• >
  把  个班级按积分分组是 。
• >
  对不同积分从大到小排序，复杂度是 ，其中  是不同积分个数，且 。

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

参考代码

• >
  Python

import sys
from collections import defaultdict

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


defsolve():
    n, m = map(int, input().split())
    gold = list(map(int, input().split()))
    silver = list(map(int, input().split()))
    bronze = list(map(int, input().split()))

    score = [0] * (n + 1)

# 先把所有比赛的积分累加出来。
for x in gold:
        score[x] += 3
for x in silver:
        score[x] += 2
for x in bronze:
        score[x] += 1

    groups = defaultdict(list)
for cls in range(1, n + 1):
# 按班级编号顺序加入，同分组内天然就是升序。
        groups[score[cls]].append(cls)

    ans = {1: None, 2: None, 3: None}
    rank = 1

# 分数从高到低处理，同分的一整组共享同一个名次。
for s in sorted(groups.keys(), reverse=True):
        ids = groups[s]
if rank in ans:
            ans[rank] = ids
        rank += len(ids)
if rank > 3:
break

    out = []
for r in (1, 2, 3):
if ans[r]:
            out.append(" ".join(map(str, ans[r])))
else:
            out.append("-1")

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()

• >
  Cpp

#include<algorithm>
#include<iostream>
#include<unordered_map>
#include<vector>
usingnamespacestd;

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

int n, m;
cin >> n >> m;

vector<int> gold(m), silver(m), bronze(m);
for (int i = 0; i < m; ++i) {
cin >> gold[i];
    }
for (int i = 0; i < m; ++i) {
cin >> silver[i];
    }
for (int i = 0; i < m; ++i) {
cin >> bronze[i];
    }

vector<longlong> score(n + 1, 0);

for (int x : gold) {
        score[x] += 3;
    }
for (int x : silver) {
        score[x] += 2;
    }
for (int x : bronze) {
        score[x] += 1;
    }

unordered_map<longlong, vector<int>> groups;
    groups.reserve(n * 2);
vector<longlong> keys;
    keys.reserve(n);

for (int cls = 1; cls <= n; ++cls) {
longlong s = score[cls];
if (!groups.count(s)) {
            keys.push_back(s);
        }
// 按班级编号递增遍历，所以同分组内天然升序。
        groups[s].push_back(cls);
    }

    sort(keys.begin(), keys.end(), greater<longlong>());

vector<int> first, second, third;
int rank = 1;

for (longlong s : keys) {
constvector<int>& ids = groups[s];
if (rank == 1) {
            first = ids;
        } elseif (rank == 2) {
            second = ids;
        } elseif (rank == 3) {
            third = ids;
        }

        rank += static_cast<int>(ids.size());
if (rank > 3) {
break;
        }
    }

auto printLine = [](constvector<int>& ids) {
if (ids.empty()) {
cout << -1 << '\n';
return;
        }
for (int i = 0; i < static_cast<int>(ids.size()); ++i) {
if (i) {
cout << ' ';
            }
cout << ids[i];
        }
cout << '\n';
    };

    printLine(first);
    printLine(second);
    printLine(third);
return0;
}

• >
  Java

import java.io.InputStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;

publicclassMain{
publicstaticvoidmain(String[] args)throws Exception {
        FastScanner fs = new FastScanner(System.in);

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

int[] gold = newint[m];
int[] silver = newint[m];
int[] bronze = newint[m];

for (int i = 0; i < m; i++) {
            gold[i] = fs.nextInt();
        }
for (int i = 0; i < m; i++) {
            silver[i] = fs.nextInt();
        }
for (int i = 0; i < m; i++) {
            bronze[i] = fs.nextInt();
        }

long[] score = newlong[n + 1];

for (int x : gold) {
            score[x] += 3;
        }
for (int x : silver) {
            score[x] += 2;
        }
for (int x : bronze) {
            score[x] += 1;
        }

        HashMap<Long, ArrayList<Integer>> groups = new HashMap<>();
for (int cls = 1; cls <= n; cls++) {
long s = score[cls];
// 按班级编号递增插入，所以同分组内天然是升序。
            groups.computeIfAbsent(s, k -> new ArrayList<>()).add(cls);
        }

        List<Long> keys = new ArrayList<>(groups.keySet());
        keys.sort(Collections.reverseOrder());

        ArrayList<Integer> first = null;
        ArrayList<Integer> second = null;
        ArrayList<Integer> third = null;
int rank = 1;

for (long s : keys) {
            ArrayList<Integer> ids = groups.get(s);
if (rank == 1) {
                first = ids;
            } elseif (rank == 2) {
                second = ids;
            } elseif (rank == 3) {
                third = ids;
            }

            rank += ids.size();
if (rank > 3) {
break;
            }
        }

        StringBuilder sb = new StringBuilder();
        appendLine(sb, first);
        appendLine(sb, second);
        appendLine(sb, third);
        System.out.print(sb);
    }

privatestaticvoidappendLine(StringBuilder sb, List<Integer> ids){
if (ids == null || ids.isEmpty()) {
            sb.append("-1\n");
return;
        }
for (int i = 0; i < ids.size(); i++) {
if (i > 0) {
                sb.append(' ');
            }
            sb.append(ids.get(i));
        }
        sb.append('\n');
    }

privatestaticclassFastScanner{
privatefinal InputStream in;
privatefinalbyte[] buffer = newbyte[1 << 16];
privateint ptr = 0;
privateint len = 0;

        FastScanner(InputStream is) {
            in = is;
        }

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

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

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

long val = 0;
while (c > 32) {
                val = val * 10 + (c - '0');
                c = read();
            }
return val * sign;
        }

intnextInt()throws Exception {
return (int) nextLong();
        }
    }
}

✨ 写在最后：

网站最近上线了八股和选额的功能啦。

最近卡片刷题已经全员开放了，八股和选择题都能直接刷。 我自己还挺喜欢这种刷法的，先看题、自己想，再翻面看答案，会比一直往下看题库更有“在准备面试”的感觉一点。 如果你最近也在刷八股，准备面试、可以来bishipass试试看哦。