第一道
我的思路是使用差分求解,但只过了90%,求指导。
#include <iostream> #include <algorithm> #include <vector> #include <set> #include <limits> #include <cstring> #include <queue> #include <unordered_map> #include <unordered_set> using namespace std; int main() { int n; cin >> n; vector<pair<int, int>> times; int min_s, max_e; while (n--) { int s, e; cin >> s >> e; times.push_back({s, e}); min_s = min(s, min_s); max_e = max(e, max_e); } vector<int> data(max_e - min_s + 1, 0); for (auto item : times) { int start = item.first; int end = item.second; data[start - min_s]++; data[end - min_s]--; } int sum = 0; int ans = 0; for (int i = 0; i <= data.size(); i++) { sum += data[i]; ans = max(ans, sum); } cout << ans << endl; return 0; }
第二道题
用的有向图加DFS,但忘了取模,不知道会不会超时。
#include <iostream> #include <algorithm> #include <vector> #include <set> #include <limits> #include <cstring> #include <queue> #include <unordered_map> #include <unordered_set> using namespace std; const int N = 100010; int h[N], e[N], ne[N], idx; int value[N]; bool seen[N]; int max_value = INT32_MIN; void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } int dfs(int start) { int cur = value[start]; for (int i = h[start]; i != -1; i = ne[i]) { int j = e[i]; if (seen[j] != true) { seen[j] = true; int temp = dfs(j); // 这块要取模? if (temp > 0) { cur += temp; } seen[j] = false; } } max_value = max(max_value, cur); return max_value; } int main() { int n; cin >> n; memset(h, -1, sizeof h); for (int i = 1; i <= n; i++) { int x, y; cin >> x >> y; if (y == 0) { value[1] = x; } else { add(y - 1, i); value[i] = x; } } int value = dfs(1); cout << max_value; return 0; }
第三道
没看题ORZ。
求大佬给前两道指导一下。
全部评论
(0) 回帖