猿辅导笔试交流

第一道

我的思路是使用差分求解，但只过了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。

求大佬给前两道指导一下。