🔗刷题网址: bishipass.com
27届实习提前批秋招汇总，持续更新，建议收藏，欢迎分享https://docs.qq.com/smartsheet/DRHVEc05MbE5CYUZa?tab=sc_JGxFAj
华子-2026.04.08-研发岗
题目一：LYA 的追踪码回文筛选
1️⃣：先把十进制整数按混合进制拆成“符号位 + 余数位”。
2️⃣：再把数字映射成字符串，判断整串是否回文。
3️⃣：若不是整串回文，就用中心扩展找最长回文子串。
难度：中等
题目二：推理模块调优计划
1️⃣：把“最小总耗时”改写成“最大总收益”。
2️⃣：每次都选当前优化收益最大的模块继续操作。
3️⃣：用最大堆维护每个模块下一次优化的收益。
难度：中等
题目三：多机任务编排收益分析
1️⃣：先枚举任务子集，预处理单机可行性和子集收益。
2️⃣：再做状态压缩 DP，求每个任务集合最少需要多少台服务器。
3️⃣：最后按服务器数量统计最大收益，并做前缀最大得到全答案。
难度：中等偏难
1. LYA 的追踪码回文筛选
问题描述
LYA 在维护一套追踪码系统。每条追踪码先由一个十进制整数 生成，再按给定的混合进制序列逐层拆分。
编码规则如下：
先写入符号位。
若 ，符号位为 ；若 ，符号位为 。
再对 做混合进制拆分。
设第二行给出的进制序列为 。从左到右处理：
- >第一步取当前值对 的余数作为下一位，然后整除为新的当前值；
- >
- >
这样会得到共 个数字：符号位 + m 个余数位。
把每一位数字映射为字母：
，，……，，得到字符串 。
- >若 本身是回文串，输出
s(palindrome)； - >
- >
输入格式
第一行输入一个整数 （）。
第二行输入 个整数 ，表示混合进制序列（，）。
输出格式
输出一行字符串，表示最终结果。
样例输入
-21
5 7 3
0
5 7 3
样例输出
bb
aaaa(palindrome)
数据范围
| |
|---|
| |
| 时，编码为 ，映射后得到 aaaa，本身是回文串，所以追加 (palindrome)。 |
题解
先把问题拆成两步：
- 根据 是否整体回文，决定输出整串还是“最长回文子串”。
#一、构造编码字符串
先加入符号位：
然后令 ，对每个进制 ：
最后把每一位映射到字母（a + 数值）即可得到 。
#二、判断整串回文
如果 本身就是回文串，直接输出 s(palindrome)。
#三、找最长回文子串
如果整串不是回文，就要找最长回文子串。
这里用“中心扩展”：
扩展过程中维护当前最优答案 best：
#复杂度分析
设编码串长度为 ，最大为 。
- >
- >中心扩展最坏为 （包含子串构造与比较），在本题范围内非常小。
参考代码
import sys
input = lambda:sys.stdin.readline().strip()
defisp(s: str) -> bool:
return s == s[::-1]
defext(s: str, l: int, r: int, bst: str) -> str:
n = len(s)
while l >= 0and r < n and s[l] == s[r]:
cur = s[l:r + 1]
if len(cur) > len(bst) or (len(cur) == len(bst) and cur < bst):
bst = cur
l -= 1
r += 1
return bst
defsolve():
tok = sys.stdin.read().strip().split()
ifnot tok:
return
n = int(tok[0])
bs = list(map(int, tok[1:]))
# 构造编码位：符号位 + 混合进制余数位。
x = abs(n)
dig = [1if n < 0else0]
for b in bs:
dig.append(x % b)
x //= b
s = "".join(chr(ord("a") + v) for v in dig)
if isp(s):
print(f"{s}(palindrome)")
return
bst = s[0]
for i in range(len(s)):
bst = ext(s, i, i, bst)
bst = ext(s, i, i + 1, bst)
print(bst)
if __name__ == "__main__":
solve()
#include<bits/stdc++.h>
usingnamespacestd;
staticboolisp(conststring &s){
int l = 0, r = (int)s.size() - 1;
while (l < r) {
if (s[l] != s[r]) {
returnfalse;
}
++l;
--r;
}
returntrue;
}
staticvoidext(conststring &s, int l, int r, string &bst){
int n = (int)s.size();
while (l >= 0 && r < n && s[l] == s[r]) {
string cur = s.substr(l, r - l + 1);
if ((int)cur.size() > (int)bst.size() ||
((int)cur.size() == (int)bst.size() && cur < bst)) {
bst = cur;
}
--l;
++r;
}
}
intmain(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
longlong n;
if (!(cin >> n)) {
return0;
}
vector<int> bs;
int b;
while (cin >> b) {
bs.push_back(b);
}
// 构造编码位：符号位 + 每层余数位。
longlong x = llabs(n);
vector<int> dig;
dig.reserve(bs.size() + 1);
dig.push_back(n < 0 ? 1 : 0);
for (int v : bs) {
dig.push_back((int)(x % v));
x /= v;
}
string s;
s.reserve(dig.size());
for (int v : dig) {
s.push_back((char)('a' + v));
}
if (isp(s)) {
cout << s << "(palindrome)\n";
return0;
}
string bst = s.substr(0, 1);
for (int i = 0; i < (int)s.size(); ++i) {
ext(s, i, i, bst);
ext(s, i, i + 1, bst);
}
cout << bst << '\n';
return0;
}
import java.io.*;
import java.util.*;
publicclassMain{
staticbooleanisp(String s){
int l = 0, r = s.length() - 1;
while (l < r) {
if (s.charAt(l) != s.charAt(r)) {
returnfalse;
}
l++;
r--;
}
returntrue;
}
static String ext(String s, int l, int r, String bst){
int n = s.length();
while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
String cur = s.substring(l, r + 1);
if (cur.length() > bst.length() ||
(cur.length() == bst.length() && cur.compareTo(bst) < 0)) {
bst = cur;
}
l--;
r++;
}
return bst;
}
publicstaticvoidmain(String[] args)throws Exception {
FastScanner fs = new FastScanner(System.in);
Long fv = fs.nextLong();
if (fv == null) {
return;
}
long n = fv;
ArrayList<Integer> bs = new ArrayList<>();
Long tv;
while ((tv = fs.nextLong()) != null) {
bs.add(tv.intValue());
}
long x = Math.abs(n);
StringBuilder sb = new StringBuilder();
sb.append((char) ('a' + (n < 0 ? 1 : 0)));
for (int b : bs) {
int d = (int) (x % b);
sb.append((char) ('a' + d));
x /= b;
}
String s = sb.toString();
if (isp(s)) {
System.out.println(s + "(palindrome)");
return;
}
String bst = s.substring(0, 1);
for (int i = 0; i < s.length(); i++) {
bst = ext(s, i, i, bst);
bst = ext(s, i, i + 1, bst);
}
System.out.println(bst);
}
staticclassFastScanner{
privatefinal InputStream in;
privatefinalbyte[] buf = newbyte[1 << 16];
privateint len = 0;
privateint ptr = 0;
FastScanner(InputStream is) {
in = is;
}
privateintread()throws IOException {
if (ptr >= len) {
len = in.read(buf);
ptr = 0;
if (len <= 0) {
return -1;
}
}
return buf[ptr++];
}
Long nextLong()throws IOException {
int c;
do {
c = read();
if (c == -1) {
returnnull;
}
} while (c <= ' ');
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long val = 0;
while (c > ' ') {
val = val * 10 + (c - '0');
c = read();
}
return val * sgn;
}
}
}
2. 推理模块调优计划
问题描述
LYA 在整理一条推理服务链路。链路里有 个模块，按顺序串行执行，总耗时等于各模块耗时之和。
第 个模块当前耗时是 ，允许优化后的最低耗时是 ，且满足 。现在有 天优化窗口，每天只能选择一个模块做一次优化，同一个模块可以被多次选择。
一次优化会把当前耗时 更新为 。也就是说，先做“向上取整减半”，再受下限约束，不能低于 。如果某模块当前已经等于 ，它就不能再被优化。
请计算经过至多 次优化后，所有模块总耗时的最小值。
输入格式
第一行包含两个整数 ，分别表示模块数量和可执行优化的天数。
第二行包含 个整数 ，表示各模块初始耗时。
第三行包含 个整数 ，表示各模块耗时下限。
输出格式
输出一个整数，表示优化结束后的最小总耗时。
样例输入
2 0
50 100
10 10
2 3
100 80
40 10
2 10
6 8
3 4
样例输出
150
70
7
| |
|---|
| |
| 最优策略会优先挑“本次减少最多”的模块，3 次后可降到 。 |
| |
数据范围
题解
先看单个模块。若当前耗时为 ，下限为 ，一次优化后的新值是：
这次优化带来的收益是：
目标是做不超过 次操作，让总收益最大。因为总耗时初值固定，最大化收益就等价于最小化最终总耗时。
核心观察：
- 对同一个模块连续优化时，后续收益不会超过前一次收益。
- 所以每一天只要选择“当前收益最大”的模块就是最优的。
可用最大堆维护每个模块“下一次优化的收益”：
时间复杂度为 ，空间复杂度为 。
参考代码
import sys
import heapq
input = lambda: sys.stdin.readline().strip()
defnxt(x, lo):
y = (x + 1) // 2
return y if y > lo else lo
defsolve():
dat = list(map(int, sys.stdin.buffer.read().split()))
ifnot dat:
return
n, m = dat[0], dat[1]
a = dat[2:2 + n]
b = dat[2 + n:2 + 2 * n]
s = sum(a)
hp = []
# 初始化每个模块下一次优化的收益
for i in range(n):
if a[i] > b[i]:
na = nxt(a[i], b[i])
d = a[i] - na
if d > 0:
heapq.heappush(hp, (-d, i))
# 每天取当前收益最大的模块优化
for _ in range(m):
ifnot hp:
break
d, i = heapq.heappop(hp)
d = -d
if d <= 0:
break
s -= d
a[i] = nxt(a[i], b[i])
if a[i] > b[i]:
na = nxt(a[i], b[i])
nd = a[i] - na
if nd > 0:
heapq.heappush(hp, (-nd, i))
print(s)
if __name__ == "__main__":
solve()
#include<bits/stdc++.h>
usingnamespacestd;
staticinlineintnxt(int x, int lo){
int y = (x + 1) / 2;
return max(y, lo);
}
intmain(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(n), b(n);
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < n; ++i) cin >> b[i];
longlong s = 0;
for (int x : a) s += x;
// (收益, 下标) 的大根堆
priority_queue<pair<int, int>> pq;
for (int i = 0; i < n; ++i) {
if (a[i] > b[i]) {
int na = nxt(a[i], b[i]);
int d = a[i] - na;
if (d > 0) pq.push({d, i});
}
}
for (int day = 0; day < m && !pq.empty(); ++day) {
auto [d, i] = pq.top();
pq.pop();
if (d <= 0) break;
s -= d;
a[i] = nxt(a[i], b[i]);
if (a[i] > b[i]) {
int na = nxt(a[i], b[i]);
int nd = a[i] - na;
if (nd > 0) pq.push({nd, i});
}
}
cout << s << '\n';
return0;
}
import java.io.*;
import java.util.*;
publicclassMain{
staticclassFastIn{
privatefinal InputStream in = System.in;
privatefinalbyte[] buf = newbyte[1 << 16];
privateint ptr = 0, len = 0;
privateintread()throws IOException {
if (ptr >= len) {
len = in.read(buf);
ptr = 0;
if (len <= 0) return -1;
}
return buf[ptr++];
}
intnextInt()throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int v = 0;
while (c > ' ') {
v = v * 10 + (c - '0');
c = read();
}
return v * sgn;
}
}
staticintnxt(int x, int lo){
int y = (x + 1) / 2;
return Math.max(y, lo);
}
publicstaticvoidmain(String[] args)throws Exception {
FastIn fs = new FastIn();
int n = fs.nextInt();
int m = fs.nextInt();
int[] a = newint[n];
int[] b = newint[n];
for (int i = 0; i < n; i++) a[i] = fs.nextInt();
for (int i = 0; i < n; i++) b[i] = fs.nextInt();
long sum = 0;
for (int x : a) sum += x;
// [收益, 下标]，按收益降序
PriorityQueue<int[]> pq = new PriorityQueue<>((u, v) -> Integer.compare(v[0], u[0]));
for (int i = 0; i < n; i++) {
if (a[i] > b[i]) {
int na = nxt(a[i], b[i]);
int d = a[i] - na;
if (d > 0) pq.offer(newint[]{d, i});
}
}
for (int day = 0; day < m && !pq.isEmpty(); day++) {
int[] cur = pq.poll();
int d = cur[0], i = cur[1];
if (d <= 0) break;
sum -= d;
a[i] = nxt(a[i], b[i]);
if (a[i] > b[i]) {
int na = nxt(a[i], b[i]);
int nd = a[i] - na;
if (nd > 0) pq.offer(newint[]{nd, i});
}
}
System.out.println(sum);
}
}
3. 多机任务编排收益分析
问题描述
LYA 在做一套离线任务编排平台。每个任务都有三项属性：CPU 需求、内存需求和收益值。现在有若干台规格完全一致的服务器，每台服务器最多承载的 CPU 为 ，最多承载的内存为 。
给定 个任务，第 个任务的资源需求为 ，收益为 。同一台服务器可以放多个任务，但这台机器上任务的 CPU 需求和不能超过 ，内存需求和不能超过 。每个任务最多只能被放到一台服务器上。
对于服务器数量 ，请分别计算在有 台服务器时，最多能获得的总收益。
输入格式
第一行包含三个整数 ，分别表示任务数量、单台服务器的 CPU 上限、单台服务器的内存上限。
接下来 行，每行包含三个整数 ，表示第 个任务的 CPU 需求、内存需求和收益。
输出格式
输出 行。第 行输出当服务器数量为 时，能够获得的最大总收益。
样例输入
3 3 10
1 4 1
2 5 2
2 6 4
1 5 5
10 10 100
样例输出
5
7
7
0
| |
|---|
| 当 时，最优是选择任务 1 和任务 3，总收益为 。当 或 时，可以把三个任务都放下，总收益为 。 |
| 唯一任务的资源需求超过单机上限，任何 下都无法运行该任务，因此答案始终是 。 |
数据范围
题解
这题的难点在于：既要满足每台机器的双资源上限，又要同时给出 到 的全部答案。直接按 做多次背包，会重复很多工作。
因为 ，可以把每个任务集合压成一个二进制状态 mask。核心思路分三步：
预处理每个子集是否能放进一台服务器。
设 sumC[mask]、sumM[mask]、sumV[mask] 分别是该子集的 CPU 总和、内存总和、收益总和。若 sumC[mask] <= C 且 sumM[mask] <= M，就记为单机可行。
做“最少服务器数”状态 DP。
定义 dp[mask] 表示把 mask 这些任务全部安排掉所需的最少服务器数。
转移时枚举 mask 的子集 sub，如果 sub 单机可行，就可以让一台机器负责 sub，其余任务是 mask ^ sub：
dp[mask] = min(dp[mask], dp[mask ^ sub] + 1)。
由最少服务器数反推每个 的最大收益。
若某个状态 mask 的 dp[mask] = t，说明用 t 台能实现 sumV[mask]。
先统计“恰好用 台”的最大收益，再做前缀最大，就得到“最多用 台”的答案。
这样每个状态只处理一次，总复杂度是 ，在 时可以稳定通过。
参考代码
import sys
defsolve() -> None:
arr = list(map(int, sys.stdin.buffer.read().split()))
ifnot arr:
return
it = iter(arr)
n = next(it)
c0 = next(it)
m0 = next(it)
c = [0] * n
m = [0] * n
v = [0] * n
for i in range(n):
c[i] = next(it)
m[i] = next(it)
v[i] = next(it)
ms = 1 << n
sc = [0] * ms
sm = [0] * ms
sv = [0] * ms
ok = bytearray(ms)
ok[0] = 1
for s in range(1, ms):
lb = s & -s
i = lb.bit_length() - 1
p = s ^ lb
sc[s] = sc[p] + c[i]
sm[s] = sm[p] + m[i]
sv[s] = sv[p] + v[i]
if sc[s] <= c0 and sm[s] <= m0:
ok[s] = 1
inf = n + 1
dp = [inf] * ms
dp[0] = 0
for s in range(1, ms):
t = s
best = inf
while t:
if ok[t]:
now = dp[s ^ t] + 1
if now < best:
best = now
if best == 1:
break
t = (t - 1) & s
dp[s] = best
ex = [0] * (n + 1)
for s in range(ms):
k = dp[s]
if k <= n and sv[s] > ex[k]:
ex[k] = sv[s]
for k in range(1, n + 1):
if ex[k - 1] > ex[k]:
ex[k] = ex[k - 1]
print("\n".join(map(str, ex[1:])))
if __name__ == "__main__":
solve()
#include<bits/stdc++.h>
usingnamespacestd;
intmain(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
longlong c0, m0;
if (!(cin >> n >> c0 >> m0)) {
return0;
}
vector<longlong> c(n), m(n), v(n);
for (int i = 0; i < n; ++i) {
cin >> c[i] >> m[i] >> v[i];
}
int ms = 1 << n;
vector<longlong> sc(ms, 0), sm(ms, 0), sv(ms, 0);
vector<char> ok(ms, 0);
ok[0] = 1;
for (int s = 1; s < ms; ++s) {
int lb = s & -s;
int i = __builtin_ctz(lb);
int p = s ^ lb;
sc[s] = sc[p] + c[i];
sm[s] = sm[p] + m[i];
sv[s] = sv[p] + v[i];
if (sc[s] <= c0 && sm[s] <= m0) {
ok[s] = 1;
}
}
int inf = n + 1;
vector<int> dp(ms, inf);
dp[0] = 0;
for (int s = 1; s < ms; ++s) {
for (int t = s; t; t = (t - 1) & s) {
if (!ok[t]) {
continue;
}
int now = dp[s ^ t] + 1;
if (now < dp[s]) {
dp[s] = now;
if (dp[s] == 1) {
break;
}
}
}
}
vector<longlong> ex(n + 1, 0);
for (int s = 0; s < ms; ++s) {
int k = dp[s];
if (k <= n) {
ex[k] = max(ex[k], sv[s]);
}
}
for (int k = 1; k <= n; ++k) {
ex[k] = max(ex[k], ex[k - 1]);
cout << ex[k] << '\n';
}
return0;
}
import java.io.IOException;
import java.io.InputStream;
publicclassMain{
privatestaticfinalclassFastScanner{
privatefinal InputStream in = System.in;
privatefinalbyte[] buf = newbyte[1 << 16];
privateint len = 0;
privateint ptr = 0;
privateintread()throws IOException {
if (ptr >= len) {
len = in.read(buf);
ptr = 0;
if (len <= 0) {
return -1;
}
}
return buf[ptr++];
}
longnextLong()throws IOException {
int ch;
do {
ch = read();
} while (ch <= ' ' && ch != -1);
if (ch == -1) {
return Long.MIN_VALUE;
}
int sgn = 1;
if (ch == '-') {
sgn = -1;
ch = read();
}
long val = 0;
while (ch > ' ') {
val = val * 10 + (ch - '0');
ch = read();
}
return val * sgn;
}
}
publicstaticvoidmain(String[] args)throws Exception {
FastScanner fs = new FastScanner();
long first = fs.nextLong();
if (first == Long.MIN_VALUE) {
return;
}
int n = (int) first;
long c0 = fs.nextLong();
long m0 = fs.nextLong();
long[] c = newlong[n];
long[] m = newlong[n];
long[] v = newlong[n];
for (int i = 0; i < n; i++) {
c[i] = fs.nextLong();
m[i] = fs.nextLong();
v[i] = fs.nextLong();
}
int ms = 1 << n;
long[] sc = newlong[ms];
long[] sm = newlong[ms];
long[] sv = newlong[ms];
boolean[] ok = newboolean[ms];
ok[0] = true;
for (int s = 1; s < ms; s++) {
int lb = s & -s;
int i = Integer.numberOfTrailingZeros(lb);
int p = s ^ lb;
sc[s] = sc[p] + c[i];
sm[s] = sm[p] + m[i];
sv[s] = sv[p] + v[i];
if (sc[s] <= c0 && sm[s] <= m0) {
ok[s] = true;
}
}
int inf = n + 1;
int[] dp = newint[ms];
for (int i = 1; i < ms; i++) {
dp[i] = inf;
}
for (int s = 1; s < ms; s++) {
for (int t = s; t > 0; t = (t - 1) & s) {
if (!ok[t]) {
continue;
}
int now = dp[s ^ t] + 1;
if (now < dp[s]) {
dp[s] = now;
if (dp[s] == 1) {
break;
}
}
}
}
long[] ex = newlong[n + 1];
for (int s = 0; s < ms; s++) {
int k = dp[s];
if (k <= n && sv[s] > ex[k]) {
ex[k] = sv[s];
}
}
StringBuilder sb = new StringBuilder();
for (int k = 1; k <= n; k++) {
if (ex[k - 1] > ex[k]) {
ex[k] = ex[k - 1];
}
sb.append(ex[k]).append('\n');
}
System.out.print(sb.toString());
}
}
✨ 写在最后：
网站最近上线了八股和选额的功能啦。
最近卡片刷题已经全员开放了，八股和选择题都能直接刷。 我自己还挺喜欢这种刷法的，先看题、自己想，再翻面看答案，会比一直往下看题库更有“在准备面试”的感觉一点。 如果你最近也在刷八股，准备面试、可以来bishipass试试看哦。
10个月宝宝每天需要喝多少奶粉？
