L2-029 特立独行的幸福
题面看了犯恶心，没见过这么读起来这么难受的题面，遍历每个数的时候，对每个数操作，如果路径里有的答案就不要了(因为显然这个数是个依附别的数的数)，然后注意一下当前这个数要不是依附别的数的数才能算进答案里
#include <bits/stdc++.h>
using namespace std;
#define int long longint isp(int x) {if (x == 1)return 1;for (int i = 2; i * i <= x; ++i) {if (x % i == 0)return 1;}return 2;
}void ylh_() {int l, r;cin >> l >> r;map<int, int> mp;set<int> ex;for (int i = l; i <= r; ++i) {int cur = i;int cnt = 0;set<int> st;st.insert(cur);while (1) {int sum = 0;while (cur) {sum += (cur % 10) * (cur % 10);cur /= 10;}cur = sum;if (mp.count(cur)) {mp.erase(cur);}if (cur == 1)break;if (st.count(cur))break;st.insert(cur);ex.insert(cur);}if (cur == 1 && !ex.count(i)) {mp[i] = st.size() * (isp(i));ex.insert(i);}}if (mp.size() == 0) {cout << "SAD";return;}for (auto [a, b] : mp) {cout << a << ' ' << b << '\n';}
}int32_t main() {ios::sync_with_stdio(0);cin.tie(0);int T = 1;// cin >> T;while (T--) {ylh_();}
}
L2-030 冰岛人
注意一种情况就是，可能两个人的公共祖先存在，但是只在一个人的五代以内
因为没给数据范围写了一发暴力发现可以过
#include <bits/stdc++.h>
using namespace std;
#define int long long
using PII = pair<int, int>;void ylh_() {int n;cin >> n;map<string, int> sex;map<string, string> fa;for (int i = 1; i <= n; ++i) {string x, y;cin >> x >> y;char ed = *(y.end() - 1);if (ed == 'm') {sex[x] = 1;fa[x] = "-1";} else if (ed == 'f') {sex[x] = 0;fa[x] = "-1";} else if (ed == 'n') {sex[x] = 1;for (int j = 1; j <= 4; ++j)y.pop_back();fa[x] = y;} else {sex[x] = 0;for (int j = 1; j <= 7; ++j) {y.pop_back();}fa[x] = y;}}auto check = [&](string x, string y) -> bool {vector<string> fx, fy;string cur = x;fx.push_back(x);for (int i = 0; i < 3; i++) {if (fa[cur] != "-1") {cur = fa[cur];fx.push_back(cur);} else {break;}}cur = y;fy.push_back(y);for (int i = 0; i < 3; i++) {if (fa[cur] != "-1") {cur = fa[cur];fy.push_back(cur);} else {break;}}for (auto s1 : fx) {for (string j = y; j != "-1"; j = fa[j]) {if (s1 == j) {return false;}}}for (auto s2 : fy) {for (string j = x; j != "-1"; j = fa[j]) {if (s2 == j) {return false;}}}return true;};int q;cin >> q;while (q--) {string x, y, z;cin >> x >> z >> y >> z;if (!sex.count(x) || !sex.count(y)) {cout << "NA\n";continue;}if (sex[x] == sex[y]) {cout << "Whatever\n";continue;}if (check(x, y)) {cout << "Yes\n";} else {cout << "No\n";}}
}int32_t main() {ios::sync_with_stdio(0);cin.tie(0);int T = 1;// cin >> T;while (T--) {ylh_();}
}
L2-031 深入虎穴
注意一号点不是入口，找到入口的方式就是找到入度为0的点就行了
#include <bits/stdc++.h>
using namespace std;
#define int long long
using PII = pair<int, int>;void ylh_() {int n;cin >> n;int st = 0;vector<int> d(n + 1);vector<vector<int>> g(n + 1);for (int i = 1; i <= n; ++i) {int m;cin >> m;for (int j = 1; j <= m; ++j) {int v;cin >> v;g[i].push_back(v);++d[v];}}for (int i = 1; i <= n; ++i) {if (d[i] == 0) {st = i;}}int ans = 1;int mxdep = 1;auto dfs = [&](auto&& dfs, int u, int dep) -> void {if (dep > mxdep) {mxdep = dep;ans = u;}for (auto v : g[u]) {dfs(dfs, v, dep + 1);}};dfs(dfs, st, 1);cout << ans;
}int32_t main() {ios::sync_with_stdio(0);cin.tie(0);int T = 1;// cin >> T;while (T--) {ylh_();}
}
L2-032 彩虹瓶
用个栈表示货架就行了
#include <bits/stdc++.h>
using namespace std;
#define int long long
using PII = pair<int, int>;void ylh_() {int n, m, k;cin >> n >> m >> k;stack<int> st;for (int i = 1; i <= k; ++ i) {bool ok = 1;int cur = 1;for (int j = 1; j <= n; ++ j) {int x;cin >> x;if (x == cur) {++ cur;while (!st.empty() && st.top() == cur) {++ cur;st.pop();}} else {if (st.size() < m) {st.push(x);} else {ok = 0;}}}if (st.size()) {ok = 0;}if (ok) {cout << "YES\n";} else {cout << "NO\n";}while (st.size()) st.pop();}
}int32_t main() {ios::sync_with_stdio(0);cin.tie(0);int T = 1;// cin >> T;while (T--) {ylh_();}
}