⏰ 时间：2024/08/17
🔄 输入输出：ACM格式
⏳ 时长：100min

本试卷还有单选和多选部分，但这部分比较简单就不再展示。

最近终于有时间继续整理之前的笔试题了，因为时间仓促，难免有错误的地方，如有遇到欢迎在评论区指出。

饿了么这次笔试的时间还是比较仓促的，完成选择题后，留给三道编程题的时间就不多了。

1. 第一题

给定一个长度为 $n$ 且仅由 $0$、$1$ 两种字符构成的字符串 $s$。每次操作你都可以选择字符串 $s$ 的任意一个字符，并将其反置。
询问经过恰好 $k$ 次操作后，字符串 $s$ 是否为一个回文字符串。
若当前字符为 $0$，反置后为 $1$。若当前字符为 $1$，反置后为 $0$。
一个字符串被称作回文字符串，当且仅当这个字符串从左往右读和从右往左读都是相同的。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1\le T\le 100)$ 代表数据组数，每组测试数据描述如下:
第一行输入两个整数 $n,k(1\le n\le 1000,0\le k\le n)$。
第二行输入一个长度为 $n$ 且仅由 $0$、$1$ 两种字符构成的字符串 $s$。

输出描述

对于每一组测试数据，如果经过怡好 $k$ 次操作后，字符串 $s$ 可以成为一个回文字符串，在一行上输出 YES；否则，直接输出 NO。

题解

首先我们需要统计将字符串 $s$ 转化为回文串所需的最少操作次数，记为 $c$。具体来说，可以通过双指针遍历，计算出对应位置的字符不同的次数，这就是需要改变的字符对数。

然后我们考虑以下两种情况：

1. 当 $k<c$：显然无法在给定的操作次数内将字符串变为回文串，输出 “NO”。
2. 当 $k\ge c$：此时，我们需要考虑多余的操作次数 $k-c$：
   • 字符串长度为奇数：由于中间字符不影响回文性，因此我们可以通过多余的操作次数调整中间字符，从而总是能变成回文串，输出 “YES”。
   • 字符串长度为偶数：为了保证能够最终形成回文串，剩余操作次数 $k-c$ 必须为偶数（每次操作可以对称改变两边的字符），否则输出 “NO”。

#include <bits/stdc++.h>using namespace std;int ops(const string &s) {int left = 0, right = s.size() - 1;int changes = 0;while (left < right) {if (s[left] != s[right]) {changes++;}left++;right--;}return changes;
}void solve() {int n, k;cin >> n >> k;string s;cin >> s;int changes = ops(s);if (changes > k) {cout << "NO" << endl;} else if ((k - changes) % 2 == 0 || n % 2 == 1) {cout << "YES" << endl;} else {cout << "NO" << endl;}
}int main() {int t;cin >> t;while (t--) {solve();}return 0;
}

2. 第二题

有一个 $n$ 行 $n$ 列的棋盘，每个格子上写着数字 $0$ 或 $1$。有一个小球从某个格子出发，移动到写着 $0$ 的格子时会向下移动一格，移动到写着 $1$ 的格子时会向右移动一格，直到滚出棋盘边界。

现在有 $9$ 个询问，每次询问在子矩阵 $(x_1,y_1)\sim (x_2,y_2)$ 中，小球从 $(x_1,y_1)$ 出发开始滚动，最后会从哪个格子滚出子矩阵 $(x_1,y_1)\sim (x_2,y_2)$。

从某个格子滚出子矩阵 $(x_1,y_1)\sim (x_2,y_2)$，意思是当前所在的格子在子矩阵内，但是小球滚动路径的下一个格子不在子矩阵内，视为滚出。

从棋盘 $(x,y)$ 向右滚动一格即抵达 $(x,y+1)$，从棋盘 $(x,y)$ 向下滚动一格即抵达 $(x+1,y)$。

输入描述

第一行输入一个整数 $n(1\le n\le 500)$ 代表棋盘大小。
此后 $n$ 行，每行输入 $n$ 个整数 $a_1,a_2,...,a_n(0\le a_i\le 1)$ 代表棋盘上每个格子上写的数字。
第 $n+2$ 行输入一个整数 $q(1\le q\le 2\cdot 10^5)$ 代表询问次数。
随后 $q$ 行，每行输入四个整数 $x_1,y_1,x_2,y_2(1\le x_1,x_2,y_1,y_2\le n,x_1\le x_2,y_1\le y_2)$ 代表子矩阵范围。

输出描述

对于每一次询问，在一行上输出两个整数，代表小球滚出的位置。

题解

直接模拟的时间复杂度为 $O(qn)$，看似会超时，但实际并不会。

#include <bits/stdc++.h>using namespace std;void query(const vector<vector<int>>& board) {int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;int cx = x1, cy = y1, last_cx = cx, last_cy = cy;while (cx >= x1 && cx <= x2 && cy >= y1 && cy <= y2) {last_cx = cx;last_cy = cy;if (board[cx][cy]) cy++;else cx++;}cout << last_cx << ' ' << last_cy << endl;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<vector<int>> board(n + 1, vector<int>(n + 1));for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {cin >> board[i][j];}}int q;cin >> q;while (q--) {query(board);}return 0;
}

3. 第三题

给出一张由几个点 $m$ 条带边权的边构成的无向连通图，你有恰好 $k$ 次机会，选择一条边使得其边权 $+1$。在 $k$ 次操作全部完成后，你要选出一个合法的生成树，使得这棵生成树中：边权最小的边最大。

输出这个边权。

对于一张图，选择其中 $n-1$ 条边，使得所有顶点联通，这些边一定会组成一棵树，即为这张图的一棵生成树。可以证明，图中存在至少一棵生成树。

输入描述

第一行输入三个整数 $n,m,k(1\le n,m\le 10^5,1\le k\le 10^{14})$ 代表给定图的点数、边数和你的操作次数。
此后 $m$ 行，第 $i$ 行输入三个整数 $a_i,b_i,c_i(1\le a_i,b_i\le n;1\le c_i\le 10^{14})$ 代表图上第 $i$ 条边连接节点 $a_i$ 和 $b_i$，且边权为 $c_i$。保证图联通，没有重边。

输出描述

在一行上输出一个整数，代表全部生成树中、边权最小的边最大的那棵树，它的边权最小的边。

题解

先通过 Kruskal 算法求解最大生成树。为此，我们将图中的边按权值从大到小排序，然后依次选择不形成环的边加入生成树。得到最大生成树后，我们面临的问题是如何通过最多 k 次操作，将这些边中的最小边权尽量提高。考虑使用二分查找。二分查找的对象是最小边权的下界，假设当前下界为 mid，我们计算将所有生成树边的权值提升到至少 mid 所需的操作次数。如果这些操作次数不超过 k，说明 mid 是可行的，我们可以尝试更大的下界；否则，需要降低下界。最终，二分查找得到的值就是所有生成树中边权最小的最大值。

#include <bits/stdc++.h>using namespace std;using i64 = long long;struct UnionFind {vector<int> p;UnionFind(int n) : p(n) {iota(p.begin(), p.end(), 0);}int find(int x) {return p[x] == x ? x : (p[x] = find(p[x]));}bool unite(int x, int y) {int root_x = find(x);int root_y = find(y);if (root_x != root_y) {p[root_x] = root_y;return true;}return false;}
};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;i64 k;cin >> n >> m >> k;vector<array<i64, 3>> edges(m);for (auto& [u, v, w] : edges) {cin >> u >> v >> w;--u;--v;}sort(edges.begin(), edges.end(), [](const auto& lhs, const auto& rhs) {return lhs[2] > rhs[2];});UnionFind uf(n);vector<i64> tree_edges;// 使用Kruskal算法构建最大生成树for (const auto& [u, v, w] : edges) {if (uf.unite(u, v)) {tree_edges.push_back(w);}}// 二分查找最小可能的边权i64 left = *min_element(tree_edges.begin(), tree_edges.end());i64 right = 1e14 + k;while (left < right) {i64 mid = left + (right - left + 1) / 2;i64 required = 0;// 计算需要多少次操作才能将所有边权提升到至少 midfor (i64 w : tree_edges) {required += max(0LL, mid - w);if (required > k) break; }if (required <= k) left = mid;else right = mid - 1;}cout << left << "\n";return 0;
}