牛客小白月赛100（上）

ACM中的A题

题目描述

登录—专业IT笔试面试备考平台_牛客网

运行代码

#include <iostream>
using namespace std;
#define ll long long
bool can(ll a, ll b, ll c) {// 检查 a*2, b, c 是否能形成三角形if ((a * 2 < b + c) && (b < a * 2 + c) && (c < a * 2 + b)) return true;// 检查 a, b*2, c 是否能形成三角形if ((b * 2 < a + c) && (a < b * 2 + c) && (c < b * 2 + a)) return true;// 检查 a, b, c*2 是否能形成三角形if ((c * 2 < a + b) && (a < c * 2 + b) && (b < c * 2 + a)) return true;// 如果以上都不满足，则不能形成三角形return false;
}int main() {ll a, b, c;cin >> a >> b >> c;if (can(a, b, c)) {cout << "Yes";} else {cout << "No";}return 0;
}

代码思路

1. can 函数

   • 三角形的形成条件是任意两边之和大于第三边。这里通过检查三种可能的加倍情况来判断是否能形成三角形。
   • 对于 a*2, b, c 的情况，首先检查 a*2 分别与 b 和 c 的和是否大于另外两边，即 a * 2 < b + c、b < a * 2 + c、c < a * 2 + b。如果这三个条件都满足，则说明这种加倍情况可以形成三角形，返回 true。
   • 同理，对 a, b*2, c 和 a, b, c*2 的情况进行类似的检查。
   • 如果三种情况都不满足，则不能形成三角形，返回 false。

2. main 函数

   • 从标准输入读取三个整数 a、b、c。
   • 调用 can 函数判断这三个整数是否能在某种加倍情况下形成三角形。
   • 根据 can 函数的返回结果输出相应的信息，如果能形成三角形输出 "Yes"，否则输出 "No"。

ACM中的CM题

题目描述

登录—专业IT笔试面试备考平台_牛客网

运行代码

#include<iostream>using namespace std;using ll = long long;int nxt[200005];void solve() {int n;cin >> n;for (int i = 1;i <= n;i++) {int e;cin >> e;nxt[e] = 1;}int lst = 0;for (int i = 200000;i >= 0;i--) {if (nxt[i]) lst = i;nxt[i] = lst;}int ans = 1e9;for (int i = 0;i <= 200000;i++) {int nw = 0;int cnt = i;while (nw <= 200000) {nw = nxt[nw];if (nw == 0) break;nw += i + 1;cnt++;}ans = min(ans,cnt);}cout << ans << endl;
}signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);solve();
}

代码思路

1. 初始化：创建一个大小为 200005 的数组 nxt 来记录每个值的下一个出现位置，默认值为 1（因为如果找不到相同值，则可以尝试跳到至少自身位置）。

2. 输入处理：读取输入的序列，并更新 nxt 数组，如果遇到某个值，则将其对应的 nxt 数组元素设置为 1，表示这个值至少在当前或之后的位置出现过一次。

3. 反向填充：从后向前遍历 nxt 数组，如果当前位置的值为 1，则记录此位置为最新出现的位置；否则将当前位置的 nxt 设置为最新位置。

4. 计算最小步数：对于每一个可能的起始点 ii，计算到达或超过 200000 所需的最小步数。每次尝试跳到 nxt[nw] 并加上 i+1i+1，直到无法继续跳为止。记录所有起始点的最小步数。

5. 输出结果：输出所有起始点中的最小步数作为答案。

ACM中的ACM题

题目描述

登录—专业IT笔试面试备考平台_牛客网

运行代码

#include <iostream>
#include <vector>
#include <numeric>using namespace std;using ll = long long;struct DSU {vector<int> fa, sz;DSU(int n) {fa.resize(n);sz.resize(n, 1);iota(fa.begin(), fa.end(), 0);}int find(int x) {return x == fa[x]? x : fa[x] = find(fa[x]);}void merge(int x, int y) {int dx = find(x), dy = find(y);if (dx == dy) return;if (sz[dx] > sz[dy]) swap(dx, dy);fa[dx] = dy;sz[dy] += sz[dx];}int same(int x, int y) {return find(x) == find(y);}int size(int x) {return sz[find(x)];}
};void solve() {int n, m;cin >> n >> m;vector<pair<int, int>> e(m);vector<int> deg(n);for (int i = 0; i < m; i++) {int u, v;cin >> u >> v;u--, v--;e[i] = {u, v};deg[u]++;deg[v]++;}vector<vector<pair<int, int>>> list(n);for (int i = 0; i < m; i++) {auto [u, v] = e[i];if (deg[u] > deg[v]) swap(u, v);else if (deg[u] == deg[v] && u > v) swap(u, v);list[u].push_back({v, i});}DSU d(m);vector<int> dfn(n, -1), adj(n, -1);for (int i = 0; i < n; i++) {for (auto [j, x] : list[i]) {dfn[j] = i;adj[j] = x;}for (auto [j, x] : list[i]) {for (auto [k, y] : list[j]) {if (dfn[k] == i) {d.merge(y, x);d.merge(y, adj[k]);}}}}cout << (d.size(0) == m? "Yes" : "No") << "\n";
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t;cin >> t;while (t--) {solve();}
}

代码思路

这段代码的目的是判断给定的无向图是否连通。它通过使用并查集（Disjoint Set Union，DSU）数据结构来实现这个目标。

1. 首先读取输入的图的顶点数 n 和边数 m。
2. 然后读取 m 条边的信息，并计算每个顶点的度。
3. 根据顶点的度对边进行排序，将度小的顶点放在前面。如果度相同，则编号小的顶点放在前面。
4. 使用并查集来合并边，通过遍历顶点和与该顶点相邻的边，将满足一定条件的边进行合并操作。
5. 最后检查并查集中代表元素为 0 的集合大小是否等于边数 m，如果是，则说明图是连通的，输出 "Yes"，否则输出 "No"。

二、具体步骤原理

1. 定义并查集结构体 DSU：

   • vector<int> fa：用于存储每个元素的父节点。初始化时，每个元素的父节点都是自身。
   • vector<int> sz：用于存储每个集合的大小。初始化时，每个集合只有一个元素，所以大小为 1。
   • 构造函数 DSU(int n)：接收一个参数 n，表示元素的个数。在构造函数中，初始化 fa 和 sz 两个向量，并使用 std::iota 函数将 fa 初始化为从 0 到 n - 1 的连续序列，表示每个元素的父节点都是自身。

2. 函数 find(int x)：

   • 这是并查集的查找操作。用于找到给定元素 x 所在集合的代表元素（根节点）。
   • 如果 x 的父节点就是自身，说明 x 是根节点，直接返回 x。
   • 如果 x 的父节点不是自身，递归地调用 find(fa[x])，继续向上查找父节点，直到找到根节点。同时，在查找过程中进行路径压缩，将 x 的父节点直接设置为根节点，以减少后续查找的时间复杂度。

3. 函数 merge(int x, int y)：

   • 这是并查集的合并操作。用于将两个元素所在的集合合并为一个集合。
   • 首先找到 x 和 y 所在集合的代表元素（根节点）dx 和 dy。
   • 如果 dx 和 dy 相同，说明 x 和 y 已经在同一个集合中，无需合并，直接返回。
   • 如果 sz[dx] > sz[dy]，则交换 dx 和 dy，保证将较小的集合合并到较大的集合中，以减少合并后的树的高度。
   • 将 dx 的父节点设置为 dy，即将 x 所在的集合合并到 y 所在的集合中。同时，更新 dy 所在集合的大小 sz[dy] += sz[dx]。

4. 函数 same(int x, int y)：

   • 用于判断两个元素 x 和 y是否在同一个集合中。
   • 调用 find 函数找到 x 和 y 所在集合的代表元素，如果代表元素相同，则说明它们在同一个集合中，返回 true，否则返回 false。

5. 函数 size(int x)：

   • 用于返回包含元素 x 的集合的大小。
   • 调用 find 函数找到 x 所在集合的代表元素，然后返回 sz[find(x)]，即代表元素所在集合的大小。

6. 函数 solve()：

   • 读取输入的顶点数 n 和边数 m。
   • 创建 vector<pair<int, int>> e(m) 用于存储边的信息，vector<int> deg(n) 用于存储每个顶点的度。
   • 遍历 m 条边，读取每条边的两个顶点 u 和 v，将它们减一以适应 0 索引，将边的信息存储在 e 中，并更新顶点的度 deg[u]++ 和 deg[v]++。
   • 创建 vector<vector<pair<int, int>>> list(n)，用于存储每个顶点的相邻边信息。根据顶点的度对边进行排序，将度小的顶点放在前面。如果度相同，则编号小的顶点放在前面。然后将边的信息存储在 list 中。
   • 创建并查集对象 DSU d(m)，表示有 m 条边。
   • 创建 vector<int> dfn(n, -1) 和 vector<int> adj(n, -1)，分别用于存储每个顶点的前驱顶点和对应的边的编号。
   • 遍历每个顶点 i：
     • 对于顶点 i 的每个相邻边 (j, x)，将 j 的前驱顶点设置为 i，即 dfn[j] = i，并将对应的边的编号设置为 x，即 adj[j] = x。
     • 对于顶点 i 的每个相邻边 (j, x)，再遍历 j 的相邻边 (k, y)：如果 k 的前驱顶点是 i，说明 k 是通过顶点 i 和 j 可达的。调用并查集的 merge 函数，将边 y、x 和 adj[k] 所在的集合合并。
   • 最后，检查并查集中代表元素为 0 的集合大小是否等于边数 m，如果是，则说明图是连通的，输出 "Yes"，否则输出 "No"。

7. 主函数 main()：

   • 设置输入输出流不与标准输入输出同步，以提高输入输出效率。
   • 读取测试用例的数量 t。
   • 循环 t 次，每次调用 solve() 函数处理一个测试用例。