夜雨聆风
拼多多2026暑假实习算法方向笔试题
第一题签到题，第二题普通题，第三题简单DP（需优化），第四题状压DP+矩阵快速幂（有一点难度）
第1题-多多的Boss挑战
题目内容
多多鸡在挑战强大的 BOSS，他有 个技能，每个技能具有：
伤害值： 释放一次造成的伤害 冷却时间： 释放后必须等待的时间（从释放开始计算）
注意：一旦释放某个技能，就必须周期性地持续释放它！
具体规则如下：
你可以在 秒内使用 1 次初始释放一个技能； 每次释放耗时 1 秒，期间不能释放其他技能 之后必须在 持续释放该技能（只要不超时），其中 为冷却时间。如果 小于 1s，因为有释放时间，则两次释放之间仍然必须大于等于 1s。 不能中途切换技能，也不能组合多个技能 同一时间只能释放一个技能（所以不同技能的时间方案互斥）
战斗从时刻 0 开始，持续了 秒，你只能选择一个技能和一个起始时间（起始时间为 0 到 之间的正整数），进行周期性释放。
目标：选择一个技能和一个起始时间，使得在 时间内造成的总伤害最大。
输入描述
第一行：一个整数 ，表示总战斗时长 ()
第二行： 个整数，表示每个技能的伤害值 (, )
第三行： 个整数表示每个技能的冷却时间 (, )
其中，第二第三行的数据个数一定是相等的。
输出描述
总伤害最大值。
样例1
输入
10503输出
200说明技能只有 1 个，伤害 50，冷却时间 3。
起始时间 ：可在 0, 3, 6, 9 释放 4 次 总伤害 其他起始时间不会更多 输出 200
样例2
输入
5302输出
90说明
: 0, 2, 4 3 次 : 1, 3 2 次 最大是 90
分析
难度：签到题
1）依次枚举每个技能能达到的最大伤害，取最大值即可
2）每个技能的最大伤害
参考c++代码
#include<iostream>#include<vector>#include<algorithm>#include<cmath>using namespace std;intmain(){int n;vector<longlong> damages;vector<int> cooldowns;longlong val;string line;// 读取伤害值行if (getline(cin, line)) {if (!line.empty()) {stringstreamss(line);while (ss >> val) damages.push_back(val); } }// 读取冷却时间行if (getline(cin, line)) {if (!line.empty()) {stringstreamss(line);int cd_val;while (ss >> cd_val) cooldowns.push_back(cd_val); } }longlong max_damage = 0; n = damages.size();for (int i = 0; i < n; ++i) {longlong d = damages[i];int c = cooldowns[i];int gap = max(1, c);longlong count = 0; count = (longlong)(T - 1) / gap + 1;longlong total_dmg = count * d;if (total_dmg > max_damage) { max_damage = total_dmg; } }cout << max_damage << endl;return 0;}第2题-多多的特殊三元组
题目内容
在多多王国的数字世界里，多多和我们遇到了一个有趣的数值问题。给定一个整数数组 ，需要找出所有满足特定条件的特殊三元组。
问题描述
特殊三元组定义为满足以下条件的三元组 :
，其中 ，
满足：
由于答案可能非常大，请返回结果对 取余数后的值。
输入描述
第一行：包含一个整数 ，表示测试用例的数量。每个测试用例的输入如下：
第一行：一个整数 ，表示数组 的长度 () 第二行：包含 个整数，表示数组 的元素 ()
输出描述
对于每个测试用例，输出一个整数，表示满足条件的特殊三元组的数量（对 取模）。
样例1
输入
40 1 0 0输出
0样例2
输入
36 3 6输出
1样例3
输入
58 4 2 8 4输出
2这是一个经典的数组计数问题。我们需要在满足下标顺序 的前提下，统计满足特定数值关系的三元组数量。
解题思路
对于每一个固定的中间位置 ，我们需要知道：
在它左边（）有多少个数字等于 。 在它右边（）有多少个数字等于 。 根据乘法原理，以当前 为中间点的特殊三元组数量 = **(左侧满足条件的个数) (右侧满足条件的个数)**。
算法优化
暴力法：对每个 遍历左右两边，时间复杂度为 。考虑到 高达 300,000，这会超时。 优化法（后缀计数）：我们可以先预处理出整个数组中每个数字出现的次数（作为初始的“右侧集合”）。然后从左向右遍历数组，动态维护“左侧集合”和“右侧集合”。 当遍历到 时，先将 从右侧计数的哈希表中移除（因为它现在既不是左也不是右，而是中间点）。 查询左侧哈希表中 的数量。 查询右侧哈希表中 的数量。 计算乘积并累加到答案中。 最后将 加入左侧哈希表，供后续元素使用。 使用哈希表 unordered_map，时间复杂度降为 ，空间复杂度 ，满足要求。
C++ 代码实现
#include<iostream>#include<vector>#include<unordered_map>using namespace std;constint MOD = 1e9 + 7;voidsolve(){int n;if (!(cin >> n)) return;vector<longlong> nums(n);for (int i = 0; i < n; ++i) {cin >> nums[i]; }// right_count 存储当前位置右侧所有数字的出现次数unordered_map<longlong, longlong> right_count;for (longlong num : nums) { right_count[num]++; }// left_count 存储当前位置左侧所有数字的出现次数unordered_map<longlong, longlong> left_count;longlong total_ways = 0;for (int j = 0; j < n; ++j) {longlong val_j = nums[j];// 将当前元素从右侧集合中移除，因为它现在是中间点 j right_count[val_j]--;// 目标值：nums[i] 和 nums[k] 必须等于 2 * nums[j]longlong target = 2 * val_j;// 获取左侧满足 nums[i] == target 的数量longlong left_cnt = 0;if (left_count.find(target) != left_count.end()) { left_cnt = left_count[target]; }// 获取右侧满足 nums[k] == target 的数量longlong right_cnt = 0;if (right_count.find(target) != right_count.end()) { right_cnt = right_count[target]; }// 累加方案数 total_ways = (total_ways + (left_cnt % MOD) * (right_cnt % MOD)) % MOD;//将当前元素加入左侧集合，供未来的 j 使用 left_count[val_j]++; }cout << total_ways << endl;}intmain(){ ios_base::sync_with_stdio(false);cin.tie(NULL);int t;if (cin >> t) {while (t--) { solve(); } }return 0;}第3题-多多爱学习
题目内容
多多是个爱学习的人，但不巧的是最近家里在装修，他只能去附近的自习室学习，自习室有很多房间，每个房间只有一段时间是空的（不必从最早空闲的自习室开始自习）。
为了不让其他人占用，多多必须在空闲开始时就到达，也不必等到空闲结束就能离开。
多多从不同的房间转移，至少需要 2 分钟时间，他想知道给定条件下，他最长能学习多长时间。
输入描述
第一行：输入一个数字，表示自习室的个数 ；
后面输入 行，每行两个数字 ，代表自习室第 分钟起空闲，空闲持续 分钟。（ 都是大于 0 的正整数，, , ）
输出描述
小多最长能学习的分钟数 。
样例1
输入
20 55 2输出
5说明小多在第一个房间学习 5 分钟
样例2
输入
20 50100 50输出
100说明小多在第一个房间学习 50 分钟，转移到第二个房间学习 50 分钟，一共可以学习 100 分钟。
问题分析
这是一个经典的线性DP问题。需要在多个时间段中进行选择，使得在满足转移时间约束的前提下，总的学习时间最长。
状态定义： 对于每一个自习室 ，定义 为：以自习室 作为最后（或当前）一个自习室时，多多能够获得的最大学习时间。
状态转移： 对于当前的自习室 （空闲开始时间为 ，持续时间为 ），我们有两种选择：
因此，状态转移方程为：
如果没有任何之前的自习室 满足条件，那么 为 0。
只在这个自习室学习：那么学习时间为 。 从之前的某个自习室 转移过来：必须满足转移时间至少为 2 分钟，即 。此时，总学习时间为 。 优化： 由于 最大可达 ，如果采用双重循环枚举所有的 和 ，时间复杂度为 ，会超时。 我们需要将时间复杂度优化到 。
首先，将所有自习室按照空闲开始时间 从小到大排序。 排序后，对于当前的自习室 ，所有合法的 一定在 的前面。我们需要快速找到前面所有满足 的 中， 的最大值。 我们可以使用二分查找来定位这个边界，并使用前缀最大值数组来在 时间内获取该边界之前的最大 值。
具体步骤
读入数据，将每个自习室表示为 (start, end)，其中start = X，end = X + Y。按照 start对所有自习室进行升序排序。初始化一个数组 max_dp，max_dp[i]表示前 个自习室中最大的 值。遍历排序后的自习室： 当前自习室的开始时间为 cur_start。我们需要在前面找到最大的 end_j <= cur_start - 2。使用 std::upper_bound在ends数组（记录每个自习室的结束时间）中查找cur_start - 2的位置。根据找到的位置，从 max_dp数组中获取之前的最大学习时长prev_max。当前自习室的最大学习时长 dp[i] = prev_max + Y_i。更新 max_dp[i] = max(max_dp[i-1], dp[i])。最终的答案就是 max_dp[N-1]。
注：这个假设（即“按照自习室空闲开始时间 X 排序后，最优解的转移路径一定是从前往后”）能够成立，其核心在于时间的单向性（不可逆）。有兴趣的可以进一步分析。
C++ 代码实现
#include<iostream>#include<vector>#include<algorithm>using namespace std;intmain(){ ios_base::sync_with_stdio(false);cin.tie(nullptr);int N;if (!(cin >> N)) return0;vector<pair<longlong, longlong>> rooms(N);for (int i = 0; i < N; ++i) {longlong X, Y;cin >> X >> Y; rooms[i] = {X, X + Y}; }// 按照开始时间排序 sort(rooms.begin(), rooms.end());vector<longlong> ends(N);// dp[i] 记录以第 i 个自习室结尾的最大学习时间vector<longlong> dp(N);// max_dp[i] 记录前 i 个自习室中 dp 的最大值vector<longlong> max_dp(N);for (int i = 0; i < N; ++i) {longlong cur_start = rooms[i].first;longlong duration = rooms[i].second - rooms[i].first; ends[i] = rooms[i].second;// 寻找前面结束时间 <= cur_start - 2 的自习室// upper_bound 找到第一个 > cur_start - 2 的位置，减 1 即为最后一个 <= cur_start - 2 的位置longlong target = cur_start - 2;auto it = upper_bound(ends.begin(), ends.begin() + i, target);longlong prev_max = 0;if (it != ends.begin()) {int idx = (it - ends.begin()) - 1; prev_max = max_dp[idx]; } dp[i] = prev_max + duration;// 更新前缀最大值if (i == 0) { max_dp[i] = dp[i]; } else { max_dp[i] = max(max_dp[i - 1], dp[i]); } }cout << max_dp[N - 1] << endl;return 0;}第4题-多多的道路修建II
题目内容
多多现在在负责多多乡村的修建。
道路修建问题可以看作是在一条直线上，有 个单位。
经过认真分析，他发现每一段路有两种修建的方案："修1"和"修2"，分别为用 的石砖和用 的石砖进行铺设。
多多规定，一段有两种方案的路，可以把道路的空间给完全铺掉。
石块不能拆分（会影响美观），以及石块之间不可重叠（道路会凹凸不平）。
注： 也就是道路是一个长为 、宽为 的矩形，需要用 和 的砖铺满。
输入描述
共一行，两个正整数 和 ，分别表示要修建的道路的长度。 ()
输出描述
输出一个整数，表示不同修建方案的数量。由于答案可能会很大，只需要输出答案对 取模后的值即可。
补充说明
对于80%的数据，；对于100%的数据，有
样例1
输入
4 2输出
5说明以字符 表示 的石砖，字符 表示 的石砖的 ，满足修建的方案有：
(1)OOOOOOOO(2)XXOOXXOO(3)OXXOOXXO(4)OOXXOOXX(5)XXXXXXXX
样例2
输入
3 3输出
5样例3
输入
2 5输出
8思路分析
这里道路是一个长为 、宽为 的矩形，需要用 和 的砖铺满。
因为 很小，而 很大，所以不能直接按 做普通动态规划。可以使用状态压缩动态规划 + 矩阵快速幂。
按列从左到右铺路。
用一个 位二进制状态 mask 表示当前列中哪些位置已经被上一列放出的 砖占用。
对于每一列，从当前状态 mask 出发，用深度优先搜索枚举当前列的所有铺法，得到下一列状态 nextMask。
转移方式有两种：
如果当前位置已经被占用，跳过。 如果当前位置没被占用： 放一个 砖。 如果当前位置和下一行都空，可以放一个 砖，它会占用下一列对应的两个格子，所以要在 nextMask 中标记。
这样可以得到一个大小为 的转移矩阵 。
最终答案就是从初始状态 0 经过 列后回到状态 0 的方案数，即矩阵 中对应的值。
复杂度分析
设 。
构造转移矩阵的复杂度为 。
矩阵快速幂的时间复杂度为 。
由于 ，所以 ，复杂度完全可以通过。
空间复杂度为 。
参考代码
#include<iostream>#include<vector>#include<cstring>using namespace std;constint MOD = 1000000007;constint MAX_M = 5;constint MAX_STATE = 1 << MAX_M; // 32structMatrix {longlong mat[MAX_STATE][MAX_STATE];int size; Matrix(int sz = 0) : size(sz) { memset(mat, 0, sizeof(mat)); }};Matrix multiply(const Matrix& A, const Matrix& B){Matrix C(A.size);for (int i = 0; i < A.size; ++i) {for (int k = 0; k < A.size; ++k) {if (A.mat[i][k] == 0) continue;for (int j = 0; j < A.size; ++j) { C.mat[i][j] = (C.mat[i][j] + A.mat[i][k] * B.mat[k][j]) % MOD; } } }return C;}Matrix power(Matrix base, longlongexp){Matrix result(base.size);for (int i = 0; i < base.size; ++i) result.mat[i][i] = 1;while (exp > 0) {if (exp & 1) result = multiply(result, base); base = multiply(base, base);exp >>= 1; }return result;}boolisValidRightHalf(int mask, int M){int i = 0;while (i < M) {if (mask & (1 << i)) {if (i + 1 >= M || !(mask & (1 << (i + 1)))) returnfalse; i += 2; } else { i++; } }returntrue;}intmain(){longlong N;int M;if (!(cin >> N >> M)) return0;int STATE = 1 << M;Matrix T(STATE);for (int prev = 0; prev < STATE; ++prev) {int need = (~prev) & (STATE - 1);for (int cur = 0; cur < STATE; ++cur) {if ((cur & ~need) != 0) continue;if (!isValidRightHalf(cur, M)) continue; T.mat[prev][cur] = 1; } } Matrix TN = power(T, N);cout << TN.mat[0][0] << endl;return 0;}
