L2-013 红色警报
呃，怎么说呢，题目讲的可能不太清楚，大概就是说只要连通块数量增加，那么就要发出红色警报，所以我们每去掉一个点的时候重新再搜索一下不包含这个点的图的连通块数量就行，我这里用的是bfs
#include <bits/stdc++.h>
using namespace std;
#define int long long
using PII = pair<int, int>;void ylh_() {int n, m;cin >> n >> m;vector<vector<int>> g(n);for (int i = 1; i <= m; ++i) {int u, v;cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}vector<int> exist(n + 1, 1);auto bfs = [&]() -> int {vector<int> vis(n + 1);int cnt = 0;for (int i = 0; i < n; ++i) {if (vis[i] || !exist[i])continue;queue<int> q;q.push(i);++cnt;while (!q.empty()) {auto u = q.front();q.pop();if (vis[u])continue;vis[u] = 1;for (auto v : g[u]) {if (!vis[v] && exist[v]) {q.push(v);}}}}return cnt;};int k;cin >> k;vector<int> res(k + 1);res[0] = bfs();for (int i = 1; i <= k; ++i) {int x;cin >> x;exist[x] = 0;res[i] = bfs();if (res[i] > res[i - 1]) {cout << "Red Alert: City " << x << " is lost!\n";} else {cout << "City " << x << " is lost.\n";}if (res[i] == 0) {cout << "Game Over.";}}
}int32_t main() {ios::sync_with_stdio(0);cin.tie(0);int T = 1;// cin >> T;while (T--) {ylh_();}
}
L2-014 列车调度
用Set维护每一个轨道的尾巴，显然某个值比这个尾巴小的时候才能放进这个轨道，而且最好插入目前最相近的尾巴，如果不能插入，那么就新开一条轨道
#include <bits/stdc++.h>
using namespace std;
#define int long long
using PII = pair<int, int>;void ylh_() {int n;cin >> n;set<int> st;st.insert(0);for(int i = 0; i < n; i++) {int t;cin >> t;auto it = st.upper_bound(t);if(it != st.end()) st.erase(it);st.insert(t);}cout << st.size() - 1 << endl;
}int32_t main() {ios::sync_with_stdio(0);cin.tie(0);int T = 1;// cin >> T;while (T--) {ylh_();}
}
L2-015 互评成绩
时间复杂度可以用优先队列压一下，但是不压也能过，无所谓了
#include <bits/stdc++.h>
using namespace std;
#define int long long
using PII = pair<int, int>;void ylh_() {int n, k, m;cin >> n >> k >> m;vector<int> a(n + 1);for (int i = 1; i <= n; ++i) {int x;cin >> x;int min_ = x, max_ = x, sum_ = x;for (int j = 1; j < k; ++j) {cin >> x;min_ = min(min_, x);max_ = max(max_, x);sum_ += x;}a[i] = sum_ - min_ - max_;}sort(a.begin() + 1, a.end(), greater<int>());for (int i = m; i >= 1; --i) {double res = 1.00 * a[i] / (k - 2);cout << fixed << setprecision(3) << res;if (i != 1) {cout << ' ';}}
}int32_t main() {ios::sync_with_stdio(0);cin.tie(0);int T = 1;// cin >> T;while (T--) {ylh_();}
}
L2-016 愿天下有情人都是失散多年的兄妹
太保守了导致一开始少过几个点，注意即使为人父母也是可以被询问的
#include <bits/stdc++.h>
using namespace std;
#define int long long
using PII = pair<int, int>;void ylh_() {int n;cin >> n;const int N = 1e5;vector<int> dad(N + 1, -1), mom(N + 1, -1), x(N + 1);for (int i = 1; i <= n; ++i) {int idx, f, m;char c;cin >> idx >> c >> f >> m;x[idx] = ((c == 'M') ? 1 : 2);dad[idx] = f;mom[idx] = m;if (f != -1) x[f] = 1;if (m != -1) x[m] = 2;//注意即使身为人父人母也是可以被询问的}int ok = 1;auto f = [&](auto&& f, int x, int y, int cnt) -> void {// cout << x << ' ' << y << '\n';if (x == -1 || y == -1) return ;if (x == y) {ok = 0;return;}if (cnt > 4)return;if (dad[x] != -1 && dad[y] != -1)f(f, dad[x], dad[y], cnt + 1);if (dad[x] != -1 && mom[y] != -1)f(f, dad[x], mom[y], cnt + 1);if (mom[x] != -1 && dad[y] != -1)f(f, mom[x], dad[y], cnt + 1);if (mom[x] != -1 && mom[y] != -1)f(f, mom[x], mom[y], cnt + 1);};int q;cin >> q;while (q--) {int u, v;cin >> u >> v;if (x[u] == x[v]) {cout << "Never Mind\n";continue;}ok = 1;f(f, u, v, 1);cout << ((ok) ? "Yes" : "No") << '\n';}
}int32_t main() {ios::sync_with_stdio(0);cin.tie(0);int T = 1;// cin >> T;while (T--) {ylh_();}
}