2025秋招 | pdd 0825 笔试记录
Q1
题目大意
给定一个有n个节点的树，树中的每条边都有一个权值，同时给定一个长度为 n 的整数数组 ，删除树中的若干条边后（也可以不删），整棵树就会变成一个有
x 个连通块的图，我们定义这个图的得分为：剩余边的权重之和+ ，求可能获得的最大分值是多少
示例1： 1 3 1 3 4 1 2 1 2 3 2 输出： 5 示例2： 2 3 3 3 4 1 2 1 2 3 2 3 1 2 5 1 2 1 2 3 2 输出： 6 5
解题思路
容易知道，整棵树一开始就是一个连通块，我们每删除一条边，就可以多得到一个连通块。因此我们可以考虑枚举删除边的个数：i，当我们删除了图中的 i 条边后，图中一定会有 1+i 个连通块，而为了得到尽可能大的分治，我们应该去尽量删除前 i 个权重小的边。枚举 i:0~n-1，记录其中的最大权值即可。
代码实现——贪心
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
using LL = long long;
int maxValue(vector<int> &arr, vector<int> &edgeWight) {
int n = arr.size();
sort(edgeWight.begin(), edgeWight.end()); // 将边按照权值从小到大的顺序排列
edgeWight.insert(edgeWight.begin(), 0); // 为了方便计算前缀和，这里额外插入一个0
for (int i = 1; i <= n - 1; i++) {
edgeWight[i] += edgeWight[i - 1];
}
int res = 0;
for (int i = 0; i <= n - 1; i++) {
// 当我们删除 i 条边时，由于我们只删前i条权值最小的边
// 因此剩余边的权值之和为 edgeWight[n-1]-edgeWight[i]
res = max(res, arr[i] + edgeWight[n - 1] - edgeWight[i]);
}
return res;
}
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> edgeWight(n - 1);
for (int i = 0; i < n - 1; i++) {
int u, v, w;
cin >> u >> v >> w;
edgeWight[i] = w;
}
cout << maxValue(a, edgeWight) << endl;
}
return 0;
}
时间复杂度：
Q2
题目大意
给定一个正整数数组，我们可以执行两种操作：
- 选中一个偶数，并将其值减半
- 选中两个数，移除这两个数，并向数组中新增这两个数字之和
求把数组变为全是奇数时的最少操作次数
示例： 3 3 2 4 4 2 1 9 5 1 2 3 4 5 输出： 3 0 2
解题思路——贪心
由数学知识可知 奇数+偶数 = 奇数，因此我们可以考虑先对数组中的元素按照奇偶性进行划分
只要数组中存在奇数，那么我们可以连续采用操作2，将这个奇数依次和偶数进行相加，最后一定可以得到一个全为奇数的数组
而如果数组中的元素全部为偶数，我们依然可以考虑沿用这一策略——我们先考虑使用操作1，把其中一个偶数变成奇数，然后再不断执行操作2，消去所有的偶数。而为了得到最少的操作次数，我们可以考虑遍历所有的偶数，计算其变成奇数所需的操作1的次数。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
using LL = long long;
int minOpCount(vector<LL> arr) {
int n = arr.size();
int oddCnt = 0, evenCnt = 0;
int minEvenOpCount = INF; // 把某个偶数通过/2操作变成奇数的最少次数
for (LL x : arr) {
if (x & 1) {
oddCnt++;
} else {
evenCnt++;
// 找到x的最低位的1
int cnt = 0;
while (!((x >> cnt) & 1)) {
cnt++;
}
minEvenOpCount = min(minEvenOpCount, cnt);
}
}
if (oddCnt > 0) {
return evenCnt;
}
return evenCnt - 1 + minEvenOpCount;
}
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<LL> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << minOpCount(arr) << endl;
}
return 0;
}
时间复杂度：
Q3
题目大意
给定一个正整数数组 arr[] 和一个正整数 x，每次你可以用 x 和数组中一个比 x 小的元素进行交换，求经过最少多少次交换后，可以使得数组 arr[] 是单调不减的
示例： 5 5 2 1 3 2 4 输出： 3
解题思路——记忆化搜索
从后向前考虑，假设当前考虑 nums[i]：
- 若
nums[i]<nums[i-1]： 若 x >= nums[i-1]，此时我们可以把 nums[i] 和 x 进行交换，这样就能保证第 i 号位和第 i-1 号位之间的关系是符合要求的，我们接下来只要去求出从 i-1 开始考虑，且 x=nums[i] 的最少交换次数即可若 x<nums[i-1]，则交换了也没用，此时一定无法使得数组单调不减 - 若
nums[i] >= nums[i-1]： 若 x<=nums[i]，此时无法交换，因此我们接下来只要去求出从 i-1 开始考虑，且 x = x 的最少交换次数即可若 x > nums[i]：如果我们不交换，那么后续就有可能把 x 和 nums[0:i-1] 之中的某个数进行交换，这样就会使得 arr[] 不满足单调非递减的条件，因此，我们仍要进行分类讨论： 若 nums[0:i] 已经是非递减的情况，那么我们确实可以不用交换，且此时的最少交换次数是0否则，我们一定要把 x 和 nums[i] 进行交换（不然后面就会破坏非递减性），此我们接下来只要去求出从 i-1 开始考虑，且 x = nums[i] 的最少交换次数即可
不难看出，上述问题可以用递归的思路解决，我们可以设置递归函数 dfs(i,x) 来求解用 x替换，将 nums[0:i] 变成非递减时所需的最少操作次数。为了减少算法的时间开销，这里我们引入 vector<unordered_map<int, int>> dp 来缓存 dfs(i,x) 的结果
代码实现
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
using LL = long long;
int minChangeCnt(vector<int> &arr, int x) {
int n = arr.size();
vector<bool> isSorted(n, false); // 判断arr[0:i]是否已非递减
isSorted[0] = true;
for (int i = 1; i < n; i++) {
if (arr[i] >= arr[i - 1]) {
isSorted[i] = true;
} else {
break;
}
}
vector<unordered_map<int, int>> dp(n, unordered_map<int, int>());
function<int(int, int)> dfs = [&](int i, int x) -> int {
if (i == 0 || isSorted[i]) {
return 0;
}
if (dp[i].count(x)) {
return dp[i][x];
}
int res = INF;
if (arr[i] < arr[i - 1]) {
if (x >= arr[i - 1]) {
res = min(res, 1 + dfs(i - 1, arr[i]));
}
} else {
if (x <= arr[i]) {
res = min(res, dfs(i - 1, x));
} else {
res = min(res, 1 + dfs(i - 1, arr[i]));
}
}
return dp[i][x] = res;
};
int res = dfs(n - 1, x);
if (res >= INF)
res = -1;
return res;
}
int main() {
int n, x;
cin >> n >> x;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << minChangeCnt(arr, x) << endl;
return 0;
}
补充
本解法好像只能过 60%，希望有大佬看看为什么错
Q4
题目大意
给定长度为 n 的 01 串，定义一次操作为，将整个字符串按顺序分为两部分，将两部分各自翻转后再按原顺序拼接。
问进行任意次的操作后，可以得到的最长的连续的交替的子串有多长。
示例： 5 10010 输出： 5 解释： 可以将10010 拆分为10|010 -> 01010 -> 交替子串的最大长度为5
解题思路——贪心
如果我们把 01 串看成一个首尾相连的串：
1
0 0
1 0
tip:我们把s，从s[0]开始，按照顺时针旋转的方向进行排列
对于 10|010 -> 01|010 的拆分，反应在环上就是：
1
0 0
\
1 0
我们从断裂的地方（0）开始逆时针读取，就是操作后得到的数组。
也就是说，不论我们怎么操作，最后得到的字符串，实际上就是环上以不同起点，不同方向读取到的一个字符串
因此我们可以枚举起点+方向，计算每个情况的最大交替子串长度
进一步观察可以发现，我们以 s[1] 为起点，逆时针旋转得到的结果和以 s[2] 为起点，顺时针旋转得到的结果是一致的，因此这里我们实际上只要去计算所有以 nums[i] 为起点，顺时针旋转读取到的字符串中最长交替子串的长度即可
代码实现
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
using LL = long long;
int main() {
int n;
string s;
cin >> n >> s;
int res = 1;
// 为了方便计算，我们将字符串复制一遍
s += s;
// 枚举以nums[i]为起点，顺时针读取得到的字符串中最长的交替子串长度
for (int i = 0; i < n; i++) {
int len = 1;
for (int k = 1; k < n; k++) {
if (s[i + k] != s[i + k - 1]) {
len++;
} else {
res = max(res, len);
len = 1;
}
}
}
// 枚举以nums[i]为起点，逆时针读取得到的字符串中最长的交替子串长度
for (int i = n; i < 2 * n; i++) {
int len = 1;
for (int k = 1; k < n; k++) {
if(s[i - k] != s[i - k + 1]) {
len++;
} else {
res = max(res, len);
len = 1;
}
}
}
cout << res << endl;
return 0;
}
改进
实际上，对于最长交替子串，不论我们是通过顺时针旋转得到的，还是逆时针旋转得到的，其都不会改变交替性，因此这里实际上可以直接去计算 s+s 中的最长交替子串
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
using LL = long long;
int main() {
int n;
string s;
cin >> n >> s;
int res = 1;
s += s;
int len = 1;
for (int i = 1; i < 2 * n; i++) {
if (s[i] != s[i - 1]) {
len++;
} else {
res = max(res, len);
len = 1;
}
}
cout << min(res, n) << endl; // 交替子串的长度不会大于n
return 0;
}
时间复杂度：
