米哈游笔试 米哈游秋招 米哈游笔试题 0921
笔试时间：2025年9月21日
往年笔试合集：
第一题：数三元组
给定两个正整数 l 和 r，请统计满足以下条件的三元组 (a,b,c) 的个数：
- a < b < c
- l ≤ a,b,c ≤ r
- max(a,b,c) < lcm(a,b,c) < sum(a,b,c)
其中 max 表示最大值，lcm 表示最小公倍数，sum 表示和。
输入描述
第一行输入整数 t (1 ≤ t ≤ 100)，表示测试用例数； 接下来 t 行，每行输入两个整数 l 和 r (1 ≤ l < r ≤ 200)，表示区间端点。
输出描述
对于每个测试用例，在一行输出一个整数，表示满足条件的三元组个数。
样例输入
3
1 10
3 5
1 100
样例输出
1
0
22
样例说明
在第一个测试用例中，符合条件的三元组有 (2,3,4)，其 max(2,3,4)=4，lcm(2,3,4)=12，sum(2,3,4)=9，满足条件；
在第二个测试用例中，没有符合条件的三元组。
参考题解
解题思路：
- 遍历所有组合：使用三层嵌套循环，在给定的区间 [l,r] 内找出所有满足 a < b < c 的三元组 (a,b,c)
- 条件判断：对于每一个生成的三元组，计算其最大值 max(a,b,c)、最小公倍数 lcm(a,b,c) 和 sum(a,b,c)
- 计数：检查计算出的三个值是否满足 max < lcm < sum 的条件。如果满足，则将计数器加一
- 输出结果：遍历完所有可能的三元组后，输出最终的计数值
C++：
#include <iostream>
#include <algorithm>
using namespace std;
long long gcd(long long a, long long b) {
while (b != 0) {
long long temp = b;
b = a % b;
a = temp;
}
return a;
}
long long lcm(long long a, long long b) {
if (a == 0 || b == 0) return 0;
return (a / gcd(a, b)) * b;
}
int main() {
int t;
cin >> t;
while (t--) {
int l, r;
cin >> l >> r;
int count = 0;
for (long long a = l; a <= r; a++) {
for (long long b = a + 1; b <= r; b++) {
for (long long c = b + 1; c <= r; c++) {
long long maxVal = c;
long long sumVal = a + b + c;
long long lcmVal = lcm(lcm(a, b), c);
if (maxVal < lcmVal && lcmVal < sumVal) {
count++;
}
}
}
}
cout << count << endl;
}
return 0;
}
Java：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
while (t-- > 0) {
int l = in.nextInt();
int r = in.nextInt();
int count = 0;
for (long a = l; a <= r; a++) {
for (long b = a + 1; b <= r; b++) {
for (long c = b + 1; c <= r; c++) {
long maxVal = c;
long sumVal = a + b + c;
long lcmVal = lcm(lcm(a, b), c);
if (maxVal < lcmVal && lcmVal < sumVal) {
count++;
}
}
}
}
System.out.println(count);
}
in.close();
}
private static long gcd(long a, long b) {
while (b != 0) {
long temp = b;
b = a % b;
a = temp;
}
return a;
}
private static long lcm(long a, long b) {
if (a == 0 || b == 0) {
return 0;
}
return (a / gcd(a, b)) * b;
}
}
Python：
import math
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
def lcm(a, b):
if a == 0 or b == 0:
return 0
return (a // gcd(a, b)) * b
t = int(input())
for _ in range(t):
l, r = map(int, input().split())
count = 0
for a in range(l, r + 1):
for b in range(a + 1, r + 1):
for c in range(b + 1, r + 1):
max_val = c
sum_val = a + b + c
lcm_val = lcm(lcm(a, b), c)
if max_val < lcm_val < sum_val:
count += 1
print(count)
第二题：打击序列计数
在这个世界里，有左右两个大鼓。对左鼓的击打记为"L"，对右鼓的击打记为"R"。有趣的是，一次击打可能发出一次声音，也可能因为共鸣而发出两次相同的声音：
- 一次左鼓击打要么发出"L"，要么发出"LL"；
- 一次右鼓击打要么发出"R"，要么发出"RR"。
你只记录到了最终听到的声音序列(仅由字符'L'和'R'组成)。请问，有多少种原始的击打序列能产生该声音序列？
输入描述
第一行包含一个整数 t (1 ≤ t ≤ 100)，表示测试用例数。 接下来 t 行，每行包含一个非空字符串 s，由字符'L'和'R'组成，长度记为 n。 保证所有测试用例中 Σn ≤ 2×10^5。
输出描述
对于每个测试用例，输出一行，包含一个整数——能产生该声音序列的击打序列总数。 由于答案可能很大，请对 10^9+7 取模后输出。
样例输入
5
LR
LLRR
LRLR
L
RRR
样例输出
1
4
1
1
3
样例说明
- LR: 左鼓击打一次发出L，右鼓击打一次发出R；只有一种击打序列LR。
- LLRR: 左鼓击打一次发出LL，右鼓击打一次发出RR；左鼓击打两次各发出L，右鼓击打一次发出RR；左鼓击打一次发出LL，右鼓击打两次各发出R；左鼓击打两次各发出L，右鼓击打两次各发出R；共4种击打序列。
- RRR: 右鼓击打一次发出RR，右鼓击打一次发出R；右鼓击打一次发出R，右鼓击打一次发出RR；右鼓击打三次各发出R；共3种击打序列。
参考题解
解题思路：
- 问题分解：观察到对左鼓的敲击只影响'L'的序列，对右鼓的敲击只影响'R'的序列。因此，一个由'L'和'R'混合组成的声响序列，其产生方式的总数等于各个连续相同字符子串的产生方式数量的乘积
- 斐波那契关系：考虑一个长度为k的连续相同字符子串，要产生这个子串，最后一次敲击有两种可能： 产生了一个"K"，那么之前的k-1个字符需要有f(k-1)种产生方式产生了两个"KK"，那么之前的k-2个字符需要有f(k-2)种产生方式因此，f(k) = f(k-1) + f(k-2)，这正是斐波那契数列的递推关系
- 算法实现：预计算斐波那契数列，将字符串分块处理，累积乘积并取模
C++：
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int MOD = 1000000007;
const int MAX_LEN = 200005;
long long fib[MAX_LEN];
void precomputeFib() {
fib[0] = 1;
fib[1] = 1;
for (int i = 2; i < MAX_LEN; i++) {
fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
}
}
void solve(string s) {
long long ans = 1;
int n = s.length();
if (n == 0) {
cout << 1 << endl;
return;
}
int i = 0;
while (i < n) {
int j = i;
while (j < n && s[j] == s[i]) {
j++;
}
int blockLength = j - i;
ans = (ans * fib[blockLength]) % MOD;
i = j;
}
cout << ans << endl;
}
int main() {
precomputeFib();
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
solve(s);
}
return 0;
}
Java：
import java.util.Scanner;
public class Main {
static final int MOD = 1_000_000_007;
static final int MAX_LEN = 200005;
static long[] fib = new long[MAX_LEN];
public static void precomputeFib() {
fib[0] = 1;
if (MAX_LEN > 1) {
fib[1] = 1;
}
for (int i = 2; i < MAX_LEN; i++) {
fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
}
}
public static void main(String[] args) {
precomputeFib();
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
String s = sc.next();
solve(s);
}
sc.close();
}
public static void solve(String s) {
long ans = 1;
int n = s.length();
if (n == 0) {
System.out.println(1);
return;
}
int i = 0;
while (i < n) {
int j = i;
while (j < n && s.charAt(j) == s.charAt(i)) {
j++;
}
int blockLength = j - i;
ans = (ans * fib[blockLength]) % MOD;
i = j;
}
System.out.println(ans);
}
}
Python：
MOD = 1000000007
MAX_LEN = 200005
def precompute_fib():
fib = [0] * MAX_LEN
fib[0] = 1
fib[1] = 1
for i in range(2, MAX_LEN):
fib[i] = (fib[i - 1] + fib[i - 2]) % MOD
return fib
def solve(s, fib):
ans = 1
n = len(s)
if n == 0:
print(1)
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025 春招笔试合集 文章被收录于专栏
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
查看8道真题和解析