前言
95分钟AK，到处写bug。
题目总览
题目细览
第1题 A-1 Intersection Set of Prime Factors
思路
先计算n的所有质因子，枚举i, j交换位置，每次都计算当前n的所有质因子，将这两个集合取交集，每次打擂台求最大值即可。
我的AC代码
#include <bits/stdc++.h>constexpr int inf = 2E9;int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int n;std::cin >> n;std::string sn = std::to_string(n);int max = 0, ans = inf;auto get = [&](int x) {std::vector<int> res;for (int i = 2; i <= x / i; i++) {while (x % i == 0) {res.push_back(i);x /= i;}}if (x != 1) {res.push_back(x);x = 1;}std::sort(res.begin(), res.end());res.erase(std::unique(res.begin(), res.end()), res.end());return res;};auto set1 = get(n);for (int i = 0; i < sn.size(); i++) {for (int j = i + 1; j < sn.size(); j++) {if (sn[i] == sn[j]) {continue;}std::string t = sn;std::swap(t[i], t[j]);int tmp = std::stoi(t);auto set2 = get(tmp);std::vector<int> set3;std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), std::back_inserter(set3));if (set3.size() > max || (set3.size() == max && tmp < ans)) {max = set3.size();ans = tmp;}}}std::cout << max << " " << ans << "\n";return 0;
}
第2题 A-2 Finding the Owner
思路
模拟check一下即可，这一场最简单的一题了。
我的AC代码
#include <bits/stdc++.h>int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);std::string s;std::cin >> s;int n;std::cin >> n;std::vector<std::string> t(n);for (int i = 0; i < n; i++) {std::cin >> t[i];}auto check = [&](const std::string & x) {if (s[7] != x[7] || s[8] != x[8]) {return false;}if (s[9] != x[4]) {return false;}if (s[10] != x[17]) {return false;}return true;};std::string ans;for (int i = 0; i < n; i++) {if (check(t[i])) {ans = t[i];}}std::cout << ans << "\n";return 0;
}
第3题 A-3 Dominant Set
思路
对于给定的一组集合，我们开一个vis数组用于记录是否访问过，将集合内的节点都放进队列，标记这些节点被访问，每次取出队头元素u，枚举它的所有出边节点v，标记一下v被访问。最后判断是否所有节点都被访问了，如果是输出yes否则输出no。
我的AC代码
#include <bits/stdc++.h>int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int n, m;std::cin >> n >> m;std::vector<std::vector<int>> adj(n + 1);for (int i = 0; i < m; i++) {int u, v;std::cin >> u >> v;adj[u].push_back(v);adj[v].push_back(u);}int K;std::cin >> K;for (int ki = 0; ki < K; ki++) {int k;std::cin >> k;std::vector<int> a(k);for (int i = 0; i < k; i++) {std::cin >> a[i];}std::vector<bool> vis(n + 1);std::queue<int> q;for (int i = 0; i < k; i++) {q.push(a[i]);vis[a[i]] = true;}while (q.size()) {auto u = q.front();q.pop();for (const auto& v : adj[u]) {if (vis[v]) {continue;}vis[v] = true;}}bool isok = true;for (int i = 1; i <= n; i++) {if (!vis[i]) {isok = false;break;}}std::cout << (isok ? "yes\n" : "no\n");}return 0;
}
第4题 A-4 Is It A Tree
思路
由于可能存在有重边（无自环），所以读入结束后需要去重（先排序再去重），如果边数不等于n - 1，或者入度为0的节点数量不等于1，或者无法通过根节点（唯一的那个入度为0的节点）遍历所有节点，都不是一棵树，输出no和入度为0的节点数量，否则输出yes和根节点编号。
我的AC代码
#include <bits/stdc++.h>int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int n;std::cin >> n;std::vector<std::vector<int>> adj(n + 1);std::vector<std::array<int, 2>> edges;int u, v;while (std::cin >> u) {if (u == 0) {break;}std::cin >> v;adj[u].push_back(v);edges.push_back({u, v});}for (int i = 1; i <= n; i++) {std::sort(adj[i].begin(), adj[i].end());adj[i].erase(std::unique(adj[i].begin(), adj[i].end()), adj[i].end());}std::sort(edges.begin(), edges.end());edges.erase(std::unique(edges.begin(), edges.end()), edges.end());std::vector<int> ind(n + 1);for (int u = 1; u <= n; u++) {for (const auto& v : adj[u]) {ind[v]++;}}int cnt = std::count(ind.begin() + 1, ind.end(), 0);if (edges.size() != n - 1 || cnt != 1) {std::cout << "no " << cnt << "\n";} else {int rt = 1;for (int i = 1; i <= n; i++) {if (ind[i] == 0) {rt = i;break;}}std::vector<int> vis(n + 1);std::queue<int> q;q.push(rt);vis[rt] = true;while (q.size()) {auto u = q.front();q.pop();for (const auto& v : adj[u]) {if (vis[v]) {continue;}vis[v] = true;q.push(v);}}bool isok = true;for (int i = 1; i <= n; i++) {if (!vis[i]) {isok = false;break;}}if (!isok) {std::cout << "no " << cnt << "\n";} else {std::cout << "yes " << rt << "\n";}}return 0;
}