Shawn's Blog

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
int h[10], t, cnt = 0;
int main() {
    for (int i = 0; i < 10; ++i)
        cin >> h[i];
    cin >> t;
    t += 30;
    for (int i = 0; i < 10; ++i)
        if (h[i] <= t)
            ++cnt;
    cout << cnt << endl;
    return 0;
}

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
int l, m, u, v, tree[10001] = {0}, cnt = 0;
int main() {
    cin >> l >> m;
    for (int i = 0; i < m; ++i) {
        cin >> u >> v;
        while (u <= v)
            tree[u++] = 1;
    }
    for (int i = 0; i <= l; ++i)
        if (tree[i] == 0)
            ++cnt;
    cout << cnt << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int l, m, cnt = 0;
int main() {
    cin >> l >> m;
    vector<vector<int>> v(m, vector<int>(2));
    for (int i = 0; i < m; ++i)
        cin >> v[i][0] >> v[i][1];
    sort(begin(v), end(v));
    int i = 0, j = 0;
    while (j < m) {
        if (i <= v[j][1]) {
            i = max(i, v[j][0]);
            cnt += v[j][1] - i + 1;
            i = v[j][1] + 1;
        }
        ++j;
    }
    cout << l + 1 - cnt << endl;
    return 0;
}

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
int T, M;
int t[101], v[101];
int dp[101][1001];
int main() {
    cin >> T >> M;
    for (int i = 1; i <= M; ++i)
        cin >> t[i] >> v[i];
    for (int i = 1; i <= M; ++i)
        for (int j = 0; j <= T; ++j) {
            dp[i][j] = dp[i - 1][j];
            if (j >= t[i])
                dp[i][j] = max(dp[i][j], dp[i - 1][j - t[i]] + v[i]);
        }
    cout << dp[M][T] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
int T, M;
int t[101], v[101];
int dp[1001];
int main() {
    cin >> T >> M;
    for (int i = 1; i <= M; ++i)
        cin >> t[i] >> v[i];
    for (int i = 1; i <= M; ++i)
        for (int j = T; j >= t[i]; --j)
            dp[j] = max(dp[j], dp[j - t[i]] + v[i]);
    cout << dp[T] << endl;
    return 0;
}

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        const int n = nums.size();
        sort(nums.begin(), nums.end());
        int l = 0, ans = 0;
        long sum = 0;
        for (int r = 0; r < n; ++r) {
            sum += nums[r];
            while (l < r && sum + k < static_cast<long>(nums[r]) * (r - l + 1))
                sum -= nums[l++];
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        unordered_map<int, Employee*> m;
        for (Employee* e : employees)
            m[e->id] = e;
        function<int(int)> dfs = [&](int id) {
            Employee* e = m[id];
            int ans = e->importance;
            for (int sub : e->subordinates)
                ans += dfs(sub);
            return ans;
        };
        return dfs(id);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        unordered_map<int, Employee*> m;
        for (const auto& e : employees)
            m[e->id] = e;
        int ans = 0;
        queue<int> q;
        q.push(id);
        while (!q.empty()) {
            int curr = q.front(); q.pop();
            Employee* e = m[curr];
            ans += e->importance;
            for (int sub : e->subordinates)
                q.push(sub);
        }
        return ans;
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> freq;
        for (const auto& num: nums)
            ++freq[num];
        int ans = 0;
        for (auto [num, occ]: freq)
            if (occ == 1) {
                ans = num;
                break;
            }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int sum = 0;
            for (const auto& num : nums) {
                sum += (num >> i) & 1;
            }
            if (sum % 3)
                ans |= (1 << i);
        }
        return ans;
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool canCross(vector<int>& stones) {
        const int n = stones.size();
        vector<unordered_map<int, bool>> m(n);
        function<bool(int, int)> dfs = [&](int i, int lastDist) {
            // `i` is current position, `lastDist` is the distance that frog jump over to get to `i`.
            if (i == n - 1) return true;
            if (m[i].find(lastDist) != m[i].end()) return m[i][lastDist];
            for (int currDist = lastDist - 1; currDist <= lastDist + 1; ++currDist) {
                if (currDist > 0) {
                    int j = lower_bound(stones.begin(), stones.end(), currDist + stones[i]) - stones.begin();
                    if (j != n && stones[j] == stones[i] + currDist && dfs(j, currDist)) {
                        return m[i][lastDist] = true;
                    }
                }
            }
            return m[i][lastDist] = false;
        };
        return dfs(0, 0);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool canCross(vector<int>& stones) {
        const int n = stones.size();
        for (int i = 1; i < n; ++i)
            if (stones[i] - stones[i - 1] > i)
                return false;
        // dp[i][k] stands for whether frog can jump to `i` from `j` with distance `k`,
        // so dp[i][k] = dp[j][k − 1] || dp[j][k] || dp[j][k + 1].
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        dp[0][0] = true;
        for (int i = 1; i < n; ++i)
            for (int j = i - 1; j >= 0; --j) {
                int k = stones[i] - stones[j];
                if (k > j + 1)
                    break;
                dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k + 1];
                if (i == n - 1 && dp[i][k])
                    return true;
            }
        return false;
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool judgeSquareSum(int c) {
        for (long a = 0; a * a <= c; a++) {
            double b = sqrt(c - a * a);
            if (b == (int) b)
                return true;
        }
        return false;
    }
};

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int shipWithinDays(vector<int>& weights, int D) {
        int left = *max_element(weights.begin(), weights.end()),
            right = accumulate(weights.begin(), weights.end(), 0);
        while (left < right) {
            int mid = (left + right) / 2;
            int dayCnt = 1, curr = 0;
            for (const auto& w : weights) {
                if (curr + w > mid) {
                    ++dayCnt;
                    curr = 0;
                }
                curr += w;
            }
            if (dayCnt <= D) right = mid;
            else left = mid + 1;
        }
        return left;
    }
};
0%