Shawn's Blog

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        return dfs(nums, target, 0);
    }
    int dfs(vector<int>& nums, int target, int pos) {
        if (pos == nums.size()) return target == 0;
        return dfs(nums, target + nums[pos], pos + 1)
            + dfs(nums, target - nums[pos], pos + 1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    unordered_map<string, int> m;
    int findTargetSumWays(vector<int>& nums, int target) {
        return dfs(nums, target, 0);
    }
    int dfs(vector<int>& nums, int target, int pos) {
        string key = to_string(target) + "_" + to_string(pos);
        if (m.count(key)) return m[key];
        if (pos == nums.size()) return m[key] = target == 0;
        return m[key] = dfs(nums, target + nums[pos], pos + 1)
            + dfs(nums, target - nums[pos], pos + 1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        const int n = nums.size();
        int sum = 0;
        for (auto num : nums) sum += abs(num);
        if (target > sum) return 0;
        vector<vector<int>> f(n + 1, vector<int>(2 * sum + 1));
        f[0][sum] = 1;
        for (int i = 1; i <= n; ++i) {
            int x = nums[i - 1];
            for (int j = -sum; j <= sum; ++j) {
                if (j - x + sum >= 0) f[i][j + sum] += f[i - 1][j - x + sum];
                if (j + x + sum <= 2 * sum) f[i][j + sum] += f[i - 1][j + x + sum];
            }
        }
        return f[n][target + sum];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        const int n = nums.size();
        int sum = 0;
        for (auto num : nums) sum += abs(num);
        if (target > sum || (sum - target) % 2 != 0) return 0;
        int m = (sum - target) / 2;
        vector<int> f(m + 1);
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            int x = nums[i - 1];
            for (int j = m; j >= 0; --j) {
                f[j] += j >= x ? f[j - x] : 0;
            }
        }
        return f[m];
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        const int n = stones.size();
        int sum = 0;
        for (auto stone : stones) sum += stone;
        int t = sum / 2;
        vector<int> f(t + 1);
        for (int i = 1; i <= n; ++i) {
            int x = stones[i - 1];
            for (int j = t; j >= x; --j) {
                f[j] = max(f[j], f[j - x] + x);
            }
        }
        return sum - f[t] - f[t];
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const double PI = acos(-1);
const int N = 101;
int n;
int r[N];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &r[i]);
    sort(r, r + n, greater<int>());
    double ans = 0;
    for (int i = 0; i < n; i += 2)
        ans += PI * (r[i] * r[i] - r[i + 1] * r[i + 1]);
    printf("%lf\n", ans);
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200001;
int T;
char s[N];
int cnt[3];
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%s", &s);
        int n = strlen(s);
        int ans = n + 1;
        memset(cnt, 0, sizeof cnt);
        for (int i = 0, j = 0; j < n; ++j) {
            ++cnt[s[j] - '1'];
            while (cnt[s[i] - '1'] > 1)
                --cnt[s[i++] - '1'];
            if (cnt[0] && cnt[1] && cnt[2])
                ans = min(ans, j - i + 1);
        }
        printf("%d\n", ans == n + 1 ? 0 : ans);
    }
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 40001;
int n, m, k;
int a[N], b[N];
int s1[N], s2[N];
void work(int w[], int s[], int n) {
    for (int i = 0, j = 0; i < n; ++i)
        if (w[i]) {
            ++j;
            ++s[1], --s[j + 1];
        } else {
            j = 0;
        }
    for (int i = 1; i <= n; ++i) s[i] += s[i - 1];
}
int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < m; ++i) cin >> b[i];
    work(a, s1, n);
    work(b, s2, m);
    LL ans = 0;
    for (int i = n; i >= 1; --i) {
        if (k % i) continue;
        int j = k / i;
        if (j > m) break;
        ans += s1[i] * s2[j];
    }
    cout << ans << endl;
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int N = 1001;
const double eps = 1e-8, INF = INT_MAX;
double f[N][N];
class Solution {
public:
    int minSkips(vector<int>& dist, int speed, int hoursBefore) {
        int n = dist.size();
        for (int i = 1; i <= n; ++i) {
            double t = (double) dist[i - 1] / speed;
            for (int j = 0; j <= i; ++j) {
                f[i][j] = INF;
                if (j <= i - 1) f[i][j] = ceil(f[i - 1][j] + t - eps);
                if (j) f[i][j] = min(f[i][j], f[i - 1][j - 1] + t);
            }
        }
        for (int i = 0; i <= n; ++i)
            if (f[n][i] < hoursBefore + eps)
                return i;
        return -1;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
typedef pair<long long, int> PLI;
typedef pair<int, int> PII;
class Solution {
public:
    vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {
        const int n = tasks.size();
        priority_queue<PLI, vector<PLI>, greater<PLI>> busy; // <t, idx>
        priority_queue<PII, vector<PII>, greater<PII>> idle; // <w, idx>
        for (int i = 0; i < servers.size(); ++i)
            idle.emplace(servers[i], i);
        long long t = -1;
        auto release = [&]() {
            while (!busy.empty() && busy.top().first <= t) {
                auto [_, idx] = busy.top(); busy.pop();
                idle.emplace(servers[idx], idx);
            }
        };
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) {
            t = max(t, static_cast<long long> (i));
            release();
            if (idle.empty()) {
                t = busy.top().first;
                release();
            }
            auto [_, idx] = idle.top(); idle.pop();
            ans[i] = idx;
            busy.emplace(t + tasks[i], idx);
        }
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), range = 1 << n;
        vector<int> dp(range, INT_MAX);
        dp[0] = 0;
        for (int mask = 1; mask < range; ++mask) {
            int bits = __builtin_popcount(mask);
            for (int pos = 0; pos < n; ++pos)
                if (mask >> pos & 1)
                    dp[mask] = min(dp[mask], dp[mask ^ (1 << pos)] + (nums1[bits - 1] ^ nums2[pos]));
        }
        return dp[range - 1];
    }
};

Posted on Edited 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 n;
bool check(int n) {
    int ans = 0;
    while (n) {
        ans += n % 10;
        n /= 10;
    }
    return ans % 4 == 0;
}

int main() {
    cin >> n;
    while (!check(n)) ++n;
    cout << n << endl;
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int n;
int p[N];
int main() {
    cin >> n;
    int l = 0, r = -1;
    while (n--) {
        char c;
        int x;
        cin >> c >> x;
        if (c == 'L') p[x] = --l;
        else if (c == 'R') p[x] = ++r;
        else cout << min(r - p[x], p[x] - l) << endl;
    }
    return 0;
}
0%