🔗刷题网址: bishipass.com
27届实习提前批秋招汇总，持续更新，建议收藏，欢迎分享
https://docs.qq.com/smartsheet/DRHVEc05MbE5CYUZa?tab=sc_JGxFAj
科大讯飞
题目一：图书馆书籍整理
1️⃣：分析装帧转换操作的奇偶性特征
2️⃣：根据操作次数与平装本数量的关系分情况讨论
3️⃣：利用贪心策略最大化精装本数量
难度：中等
这道题目的关键在于理解操作的奇偶性影响，通过数学分析可以发现对每本书进行奇数次操作会改变装帧类型，偶数次操作保持不变。运用贪心思想，优先转换平装本为精装本，当操作次数有余时考虑剩余操作的奇偶性。
题目二：音符序列调整
1️⃣：理解音高提升操作对相邻音符差值的影响
2️⃣：分析打破单调递增的必要条件
3️⃣：寻找最小操作区间长度的贪心策略
难度：中等
这道题目需要深入理解操作机制，发现区间操作本质上是让某个位置的音符相对于后继音符增加固定的音高差。通过数学推导可以得出，只有当存在相邻音符的音高差小于增量时才能打破单调性，且最优策略是选择长度为1的区间。
题目三：智能照明系统
1️⃣：利用异或运算的性质分析LED状态变化
2️⃣：采用数学公式化简大规模矩阵的二进制转换
3️⃣：运用快速幂和模运算优化大数计算
难度：中等偏难
这道题目结合了位运算、组合数学和模运算。关键在于发现每个LED的最终状态只依赖于所在行列的操作奇偶性，然后通过数学公式将大规模矩阵的计算转化为高效的数值运算，避免了直接模拟的时间复杂度问题。
01. 图书馆书籍整理
问题描述
LYA 在图书馆工作，她需要整理一排书架上的书籍。书架上有 本书，每本书要么是精装本（用大写字母 H 表示），要么是平装本（用小写字母 s 表示）。
图书馆的规定是：为了美观，希望书架上精装本的数量尽可能多。LYA 可以对书籍进行"装帧转换"操作：将一本精装本改为平装本，或将一本平装本改为精装本。
现在 LYA 必须恰好进行 次装帧转换操作，请问最终书架上最多能有多少本精装本？
输入格式
第一行包含两个正整数 和 （，），分别表示书籍总数和必须进行的操作次数。
第二行包含一个长度为 的字符串 ，由大写字母和小写字母组成，表示每本书的初始装帧类型。
输出格式
输出一个整数，表示恰好进行 次装帧转换操作后，书架上精装本的最大数量。
样例输入
1 3
A
样例输出
0
数据范围
- >
- >
- >
字符串只包含大写和小写英文字母
题解
首先分析问题：我们要在恰好 次操作后最大化精装本数量。对于任意一本书，如果对它进行奇数次操作，它的装帧会改变；如果进行偶数次操作，装帧保持不变。
设初始时精装本数量为 ，平装本数量为 。假设我们对 本平装本各进行奇数次操作（它们变成精装本），对 本精装本各进行奇数次操作（它们变成平装本），剩余的操作可以配对进行偶数次操作，不影响最终状态。
约束条件：
， ，且
最终精装本数量为 ，为了最大化这个值，我们希望 尽可能大， 尽可能小。
分两种情况讨论：
情况1：直接对 本平装本进行操作，令 ，，答案为 。
情况2：先将所有平装本都转换为精装本（），此时还剩 次操作。
- >
如果 为偶数，可以全部用于配对操作，答案为 - >
如果 为奇数，必须再将一本精装本转换为平装本，答案为
时间复杂度为 。
参考代码
- >
Python
import sys
input = lambda: sys.stdin.readline().strip()
n, k = map(int, input().split())
s = input()
# 统计初始精装本数量
up_cnt = sum(1for c in s if c.isupper())
low_cnt = n - up_cnt
if k <= low_cnt:
# 直接转换k本平装本
ans = up_cnt + k
else:
# 先转换所有平装本，再考虑剩余操作
rem = k - low_cnt
ans = n - (rem % 2)
print(ans)
- >
Cpp
#include<iostream>
#include<string>
usingnamespacestd;
intmain(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
longlong n, k;
cin >> n >> k;
string s;
cin >> s;
// 统计初始精装本数量
longlong up = 0;
for (char c : s) {
if (c >= 'A' && c <= 'Z') up++;
}
longlong low = n - up;
longlong ans;
if (k <= low) {
// 直接转换k本平装本
ans = up + k;
} else {
// 先转换所有平装本，再考虑剩余操作
longlong rem = k - low;
ans = n - (rem & 1);
}
cout << ans << endl;
return0;
}
- >
Java
import java.util.Scanner;
publicclassMain{
publicstaticvoidmain(String[] args){
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
long k = sc.nextLong();
String s = sc.next();
// 统计初始精装本数量
long upCnt = 0;
for (int i = 0; i < s.length(); i++) {
if (Character.isUpperCase(s.charAt(i))) {
upCnt++;
}
}
long lowCnt = n - upCnt;
long ans;
if (k <= lowCnt) {
// 直接转换k本平装本
ans = upCnt + k;
} else {
// 先转换所有平装本，再考虑剩余操作
long rem = k - lowCnt;
ans = n - (rem % 2);
}
System.out.println(ans);
sc.close();
}
}
02. 音符序列调整
问题描述
K小姐是一名音乐编辑，她正在处理一段音乐的音符序列。这段音乐包含 个音符，音符的音高分别为 ，且满足 （音高呈非严格递增）。
为了让音乐更有层次感，K小姐希望通过一次特殊的"音高提升"操作来打破这种单调的递增关系。具体来说，她可以选择一个连续的音符区间 （），然后对区间内的每个音符 （），将其音高调整为 ，其中 是一个固定的音高增量。
注意到这种操作的特点是：区间内靠前的音符会得到更大的音高提升。
K小姐想知道，为了让调整后的音符序列存在某个位置 使得 （即打破单调递增），她需要选择的区间长度 的最小值是多少？如果无法通过一次操作达到目标，则输出 。
输入格式
每个测试文件包含多组测试数据。
第一行包含一个正整数 （），表示测试数据组数。
对于每组测试数据：
- >
第一行包含两个正整数 和 （，），分别表示音符数量和音高增量。 - >
第二行包含 个正整数 （），表示音符的初始音高。
保证所有测试数据中 。
输出格式
对于每组测试数据，输出一个整数，表示所需的最小区间长度；如果无法通过一次操作打破单调递增关系，输出 。
样例输入
2
4 2
1 2 3 3
3 1
2 6 8
样例输出
1
-1
数据范围
- >
- >
- >
- >
- >
题解
首先分析操作的本质：选择区间 后，区间内相邻音符的音高差会发生变化。具体来说，对于区间内的相邻音符 和 ，操作后 会比 多增加 的音高。
要让 成立，有两种可能的情况：
和 都在操作区间内：此时 比 多增加 在区间末尾且 在区间外：此时 增加 而 不变
无论哪种情况，本质上都是让 相对于 增加了 的音高。
因此，要想打破原来的 关系，必须满足：
一旦存在这样的相邻位置，我们只需要选择长度为1的区间 即可：让 增加 而 保持不变，从而实现 。
如果所有相邻音符的音高差都不小于 ，那么无论如何操作，最多只能将差值减少 ，仍然保持非严格递增关系，此时答案为 。
算法步骤：
遍历所有相邻的音符对 检查是否存在 如果存在，答案为1；否则答案为-1
时间复杂度为 ，总复杂度为 。
参考代码
- >
Python
import sys
input = lambda: sys.stdin.readline().strip()
t = int(input())
for _ in range(t):
n, m = map(int, input().split())
a = list(map(int, input().split()))
# 检查是否存在可以打破的位置
found = False
for i in range(n - 1):
if a[i + 1] - a[i] < m:
found = True
break
print(1if found else-1)
- >
Cpp
#include<iostream>
#include<vector>
usingnamespacestd;
intmain(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
longlong m;
cin >> n >> m;
vector<longlong> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
// 检查是否存在可以打破的位置
bool found = false;
for (int i = 0; i < n - 1; i++) {
if (a[i + 1] - a[i] < m) {
found = true;
break;
}
}
cout << (found ? 1 : -1) << "\n";
}
return0;
}
- >
Java
import java.util.Scanner;
publicclassMain{
publicstaticvoidmain(String[] args){
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
int n = sc.nextInt();
long m = sc.nextLong();
long[] a = newlong[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextLong();
}
// 检查是否存在可以打破的位置
boolean found = false;
for (int i = 0; i < n - 1; i++) {
if (a[i + 1] - a[i] < m) {
found = true;
break;
}
}
System.out.println(found ? 1 : -1);
}
sc.close();
}
}
03. 智能照明系统
问题描述
A先生在自己的智能家居系统中安装了一个 行 列的LED灯阵列。我们用 表示第 行第 列的LED灯，初始时所有LED灯都是关闭状态（用数字 表示）。
这个智能照明系统有两种控制模式，A先生将进行 次操作，每次操作输入两个参数 和 ：
- >
当 时，切换第 列所有LED灯的状态（开变关，关变开） - >
当 时，切换第 行所有LED灯的状态（开变关，关变开）
所有操作完成后，A先生需要记录整个LED阵列的状态。他将按照从左到右、从上到下的顺序（即 ）将每个LED灯的状态（ 或 ）连接起来，形成一个二进制数。
请计算这个二进制数对应的十进制值，并对 取模后输出结果。
输入格式
第一行包含三个正整数 、 和 （，），分别表示LED阵列的行数、列数和操作次数。
接下来 行，每行包含两个正整数 和 （；当 时，；当 时，），表示一次LED状态切换操作。
输出格式
输出一个整数，表示最终LED阵列状态形成的二进制数对应的十进制值对 取模的结果。
样例输入
5 5 4
1 2
2 5
1 3
2 2
样例输出
13218195
数据范围
- >
- >
- >
- >
当 时， - >
当 时，
题解
首先分析LED灯的最终状态：每个位置 的LED灯状态取决于第 行和第 列被切换的总次数。由于初始状态为0，每次切换相当于异或1操作。因此，位置 的最终状态为：
设被操作奇数次的行集合为 ，列集合为 ，则：
接下来分析每行的贡献：对于第 行，定义：
- >
（被操作列在该行的贡献） - >
（全部列都为1时的值）
如果第 行没有被操作奇数次，该行的数值为 ； 如果第 行被操作奇数次，该行的数值为 。
然后计算行间权重：将阵列按行拼接后，第 行在整个二进制数中的权重为 ，其中 。
定义：
- >
- >
最终答案为：
算法步骤：
统计被操作奇数次的行和列 使用快速幂计算所需的幂次 计算 和 应用公式得到最终答案
时间复杂度为 。
参考代码
- >
Python
import sys
input = lambda: sys.stdin.readline().strip()
MOD = 10**9 + 7
defpow_mod(base, exp, mod):
"""快速幂取模"""
result = 1
base %= mod
while exp > 0:
if exp & 1:
result = (result * base) % mod
base = (base * base) % mod
exp >>= 1
return result
defmod_inv(x, mod):
"""计算模逆元"""
return pow_mod(x, mod - 2, mod)
n, m, k = map(int, input().split())
# 统计被操作奇数次的行和列
rows = set()
cols = set()
for _ in range(k):
x, y = map(int, input().split())
if x == 1: # 操作列
if y in cols:
cols.remove(y)
else:
cols.add(y)
else: # 操作行
if y in rows:
rows.remove(y)
else:
rows.add(y)
# 计算相关值
q = pow_mod(2, m, MOD) # 2^m mod MOD
qn = pow_mod(q, n, MOD) # q^n mod MOD
inv = mod_inv((q - 1 + MOD) % MOD, MOD) # (q-1)^(-1)
sum_all = (qn - 1 + MOD) % MOD * inv % MOD # (q^n-1)/(q-1)
# 计算 S_C
s_c = 0
for col in cols:
exp = m - col
val = pow_mod(2, exp, MOD)
s_c = (s_c + val) % MOD
s_all = (pow_mod(2, m, MOD) - 1 + MOD) % MOD
# 计算 sum_R
sum_r = 0
for row in rows:
exp = n - row
val = pow_mod(q, exp, MOD)
sum_r = (sum_r + val) % MOD
# 计算最终答案
part1 = s_c * ((sum_all - sum_r + MOD) % MOD) % MOD
delta = (s_all - 2 * s_c % MOD + MOD) % MOD
part2 = delta * sum_r % MOD
ans = (part1 + part2) % MOD
print(ans)
- >
Cpp
#include<iostream>
#include<unordered_set>
usingnamespacestd;
constlonglong MOD = 1000000007LL;
longlongpow_mod(longlong base, longlongexp, longlong mod){
longlong result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp >>= 1;
}
return result;
}
intmain(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
longlong n, m, k;
cin >> n >> m >> k;
unordered_set<longlong> rows, cols;
for (int i = 0; i < k; i++) {
int x;
longlong y;
cin >> x >> y;
if (x == 1) { // 操作列
if (cols.count(y)) {
cols.erase(y);
} else {
cols.insert(y);
}
} else { // 操作行
if (rows.count(y)) {
rows.erase(y);
} else {
rows.insert(y);
}
}
}
// 计算相关值
longlong q = pow_mod(2, m, MOD);
longlong qn = pow_mod(q, n, MOD);
longlong inv = pow_mod((q - 1 + MOD) % MOD, MOD - 2, MOD);
longlong sum_all = (qn - 1 + MOD) % MOD * inv % MOD;
// 计算 S_C
longlong s_c = 0;
for (longlong col : cols) {
longlongexp = m - col;
longlong val = pow_mod(2, exp, MOD);
s_c = (s_c + val) % MOD;
}
longlong s_all = (pow_mod(2, m, MOD) - 1 + MOD) % MOD;
// 计算 sum_R
longlong sum_r = 0;
for (longlong row : rows) {
longlongexp = n - row;
longlong val = pow_mod(q, exp, MOD);
sum_r = (sum_r + val) % MOD;
}
// 计算最终答案
longlong part1 = s_c * ((sum_all - sum_r + MOD) % MOD) % MOD;
longlong delta = (s_all - 2 * s_c % MOD + MOD) % MOD;
longlong part2 = delta * sum_r % MOD;
longlong ans = (part1 + part2) % MOD;
cout << ans << endl;
return0;
}
- >
Java
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
publicclassMain{
privatestaticfinallong MOD = 1000000007L;
publicstaticlongpowMod(long base, long exp, long mod){
long result = 1;
base %= mod;
while (exp > 0) {
if ((exp & 1) == 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp >>= 1;
}
return result;
}
publicstaticvoidmain(String[] args){
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
long m = sc.nextLong();
int k = sc.nextInt();
Set<Long> rows = new HashSet<>();
Set<Long> cols = new HashSet<>();
for (int i = 0; i < k; i++) {
int x = sc.nextInt();
long y = sc.nextLong();
if (x == 1) { // 操作列
if (cols.contains(y)) {
cols.remove(y);
} else {
cols.add(y);
}
} else { // 操作行
if (rows.contains(y)) {
rows.remove(y);
} else {
rows.add(y);
}
}
}
// 计算相关值
long q = powMod(2, m, MOD);
long qn = powMod(q, n, MOD);
long inv = powMod((q - 1 + MOD) % MOD, MOD - 2, MOD);
long sumAll = (qn - 1 + MOD) % MOD * inv % MOD;
// 计算 S_C
long sC = 0;
for (long col : cols) {
long exp = m - col;
long val = powMod(2, exp, MOD);
sC = (sC + val) % MOD;
}
long sAll = (powMod(2, m, MOD) - 1 + MOD) % MOD;
// 计算 sum_R
long sumR = 0;
for (long row : rows) {
long exp = n - row;
long val = powMod(q, exp, MOD);
sumR = (sumR + val) % MOD;
}
// 计算最终答案
long part1 = sC * ((sumAll - sumR + MOD) % MOD) % MOD;
long delta = (sAll - 2 * sC % MOD + MOD) % MOD;
long part2 = delta * sumR % MOD;
long ans = (part1 + part2) % MOD;
System.out.println(ans);
sc.close();
}
}
✨ 写在最后：
网站最近上线了八股和选额的功能啦。
最近卡片刷题已经全员开放了，八股和选择题都能直接刷。 我自己还挺喜欢这种刷法的，先看题、自己想，再翻面看答案，会比一直往下看题库更有“在准备面试”的感觉一点。 如果你最近也在刷八股，准备面试、可以来bishipass试试看哦。
