Shawn's Blog

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
34
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 300001, M = 600002;
int n, u, v, cc, w[N], h[N], c[M], e[M], ne[M], idx;
LL ans;
void add(int u, int v, int cc) {
    e[++idx] = v, c[idx] = cc, ne[idx] = h[u], h[u] = idx;
}
LL dfs(int u, int f) {
    LL d1 = 0, d2 = 0;
    for (int i = h[u]; i; i = ne[i]) {
        int v = e[i];
        if (v == f) continue;
        LL d = dfs(v, u);
        if (d < c[i]) continue;
        d -= c[i];
        if (d >= d1) d2 = d1, d1 = d;
        else if (d > d2) d2 = d;
    }
    ans = max(ans, d1 + d2 + w[u]);
    return d1 + w[u];
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
    for (int i = 1; i < n; ++i) {
        scanf("%d%d%d", &u, &v, &cc);
        add(u, v, cc), add(v, u, cc);
    }
    ans = max(ans, dfs(1, 0));
    printf("%lld", 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
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;
int T, n, k;
LL l, r, s;
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &k);
        s =  (LL) k * 2;
        l = sqrt(s);
        if (l * (l + 1) < s) ++l;
        r = k - (l * (l - 1) / 2 + 1);
        for (int i = 0; i < n - 1 - l; ++i) printf("a");
        printf("b");
        for (int i = n - l; i < n - 1 - r; ++i) printf("a");
        printf("b");
        for (int i = n - r; i < n; ++i) printf("a");
        printf("\n");
    }
    return 0;
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;
int T, h, m;
int main() {
    cin >> T;
    while (T--) {
        cin >> h >> m;
        int ans = (24 - h) * 60 - m;
        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
class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length, freq = (n + 1) / 2, cnt[] = new int[32], ans = 0;
        for (int num : nums)
            for (int i = 0; i <= 31; ++i)
                if ((num >> i & 1) != 0)
                    ++cnt[i];
        for (int i = 0; i <= 31; ++i)
            if (cnt[i] >= freq)
                ans ^= (1 << i);
        for (int num : nums)
            if ((ans ^ num) == 0)
                --freq;
        return freq > 0 ? -1 : ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length, freq = (n + 1) / 2, candidate = 0, cnt = 0;
        for (int num : nums) {
            if (cnt == 0) candidate = num;
            if (num == candidate) ++cnt;
            else --cnt;
        }
        if (cnt <= 0) return -1;
        cnt = 0;
        for (int num : nums)
            if (num == candidate)
                ++cnt;
        return cnt >= freq ? candidate : -1;
    }
}

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int cnt[30001];
class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        memset(cnt, 0, (nums.size() + 1) * 4);
        cnt[0] = 1;
        int sum = 0, ans = 0;
        for (int num : nums) {
            sum += num;
            if (sum - goal >= 0) ans += cnt[sum - goal];
            ++cnt[sum];
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        int ans = 0;
        for (int l1 = 0, l2 = 0, sum1 = 0, sum2 = 0, r = 0; r < nums.size(); ++r) {
            sum1 += nums[r];
            sum2 += nums[r];
            while (sum1 > goal) sum1 -= nums[l1++];
            while (l2 <= r && sum2 >= goal) sum2 -= nums[l2++];
            ans += l2 - l1;
        }
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int MOD = 1'000'000'007;
class Solution {
public:
    int countPairs(vector<int>& deliciousness) {
        unordered_map<int, int> freq;
        int maxSum = 0;
        int ans = 0;
        for (int d : deliciousness) {
            maxSum = max(maxSum, d * 2);
            for (int sum = 1; sum <= maxSum; sum <<= 1) {
                int t = sum - d;
                int c = freq.find(t) != freq.end() ? freq[t] : 0;
                ans = (ans + c) % MOD;
            }
            ++freq[d];
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int MOD = 1000000007;
int freq[(1 << 21) + 1] = {0,}, maxSum, ans;
class Solution {
public:
    int countPairs(vector<int>& deliciousness) {
        memset(freq, 0, sizeof freq);
        maxSum = ans = 0;
        for (int &d : deliciousness)
            ++freq[d];
        for (int &d : deliciousness) {
            --freq[d];
            for (int sum = 1; sum <= (1 << 21); sum <<= 1) {
                int t = sum - d;
                if (t >= 0)
                    ans = (ans + freq[t]) % MOD;
            }
        }
        return ans;
    }
};

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
class Solution {
public:
    vector<vector<string>> displayTable(vector<vector<string>>& orders) {
        vector<unordered_map<string, int>> tables(501);
        set<string> foods;
        for (auto &v : orders) {
            foods.insert(v[2]);
            ++tables[stoi(v[1])][v[2]];
        }
        vector<vector<string>> ans;
        for (int t = 0; t <= 500; t++) {
            if (t > 0 && tables[t].empty()) continue;
            ans.push_back({});
            ans.back().emplace_back(t == 0 ? "Table" : to_string(t));
            for (auto it = foods.begin(); it != foods.end(); it++)
                ans.back().emplace_back(t == 0 ? *it : to_string(tables[t][*it]));
        }
        return ans;
    }
};

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
    string countOfAtoms(string formula) {
        int i = 0, n = formula.length();
        auto parseAtom = [&]() -> string {
            string atom;
            atom += formula[i++];
            while (i < n && islower(formula[i]))
                atom += formula[i++];
            return atom;
        };
        auto parseNum = [&]() -> int {
            if (i == n || !isdigit(formula[i]))
                return 1;
            int num = 0;
            while (i < n && isdigit(formula[i]))
                num = num * 10 + (formula[i++] - '0');
            return num;
        };
        stack<unordered_map<string, int>> stk;
        stk.push({});
        while (i < n) {
            char ch = formula[i];
            if (ch == '(') {
                i++;
                stk.push({});
            } else if (ch == ')') {
                ++i;
                int num = parseNum();
                auto atomNum = stk.top();
                stk.pop();
                for (auto &[atom, v] : atomNum)
                    stk.top()[atom] += v * num;
            } else {
                string atom = parseAtom();
                int num = parseNum();
                stk.top()[atom] += num;
            }
        }
        auto &atomNum = stk.top();
        vector<pair<string, int>> pairs;
        for (auto &[atom, v] : atomNum)
            pairs.emplace_back(atom, v);
        sort(pairs.begin(), pairs.end());
        string ans;
        for (auto & [atom, num] : pairs) {
            ans += atom;
            if (num > 1)
                ans += to_string(num);
        }
        return ans;
    }
};
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
34
35
36
37
class Solution {
public:
    map<string, int> dfs(const string &formula, int &curr) {
        map<string, int> ans;
        while (curr < formula.size() && formula[curr] != ')') {
            if (formula[curr] == '(') {
                ++curr;
                auto tmp = dfs(formula, curr);
                int next = curr;
                while (next < formula.size() && isdigit(formula[next])) ++next;
                int num = curr == next ? 1 : stoi(formula.substr(curr, next - curr));
                curr = next;
                for (auto &[atom, v] : tmp)
                    ans[atom] += num * v;
            } else {
                int next = curr + 1;
                while (next < formula.size() && islower(formula[next])) ++next;
                string atom = formula.substr(curr, next - curr);
                curr = next;
                while (next < formula.size() && isdigit(formula[next])) ++next;
                int num = curr == next ? 1 : stoi(formula.substr(curr, next - curr));
                ans[atom] += num;
                curr = next;
            }
        }
        ++curr;
        return ans;
    }
    string countOfAtoms(string formula) {
        int curr = 0;
        auto atomNum = dfs(formula, curr);
        string ans;
        for (auto &[atom, num] : atomNum)
            ans += (num == 1 ? atom : atom + to_string(num));
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef long long LL;
const int MOD = 1000000007;
class Solution {
public:
    LL quickpow(LL x, LL n) {
        LL ans = 1;
        while (n) {
            if (n & 1) ans = ans * x % MOD;
            x = x * x % MOD;
            n /= 2;
        }
        return ans;
    }
    int countGoodNumbers(long long n) {
        return quickpow(5, (n + 1) / 2) * quickpow(4, n / 2) % MOD;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
        int n = dist.size();
        vector<int> t(n);
        for (int i = 0; i < n; ++i) {
            t[i] = (dist[i] + speed[i] - 1) / speed[i];
        }
        sort(t.begin(), t.end());
        for (int i = 0; i < n; ++i)
            if (t[i] <= i) return i;
        return n;
    }
};
0%