Shawn's Blog

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int n = fruits.size(), ans = 0;
        vector<int> freq(n);
        for (int left = 0, right = 0, cnt = 0; right < n; ++right) {
            if (++freq[fruits[right]] == 1) ++cnt;
            while (cnt > 2)
                if (--freq[fruits[left++]] == 0) --cnt;
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int findSubstringInWraproundString(string p) {
        int f[26] = {0}, cnt = 0;
        for (int i = 0; i < p.size(); ++i) {
            cnt = i && (p[i] - p[i - 1] + 26) % 26 == 1 ? cnt + 1 : 1;
            f[p[i] - 'a'] = max(f[p[i] - 'a'], cnt);
        }
        return accumulate(f, f + 26, 0);
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
        function<int(int)> count = [&](int lower) {
            int res = 0, cnt = 0;
            for (int num : nums) {
                cnt = num <= lower ? cnt + 1 : 0;
                res += cnt;
            }
            return res;
        };
        return count(right) - count(left - 1);
    }
};

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 countBalls(int lowLimit, int highLimit) {
        Map<Integer, Integer> m = new HashMap<>();
        for (int i = lowLimit; i <= highLimit; ++i) {
            int num = i, box = 0;
            while (num > 0) {
                box += num % 10;
                num /= 10;
            }
            m.put(box, m.getOrDefault(box, 0) + 1);
        }
        int ans = 0;
        for (Map.Entry<Integer, Integer> e : m.entrySet()) ans = Math.max(ans, e.getValue());
        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
class Solution {
    static int N = 100010, MOD = (int) 1e9 + 7;
    static long[] p = new long[N];
    static {
        p[0] = 1;
        for (int i = 1; i < N; ++i) p[i] = p[i - 1] * 2 % MOD;
    }
    public int sumSubseqWidths(int[] nums) {
        int n = nums.length;
        long ans = 0;
        Arrays.sort(nums);
        for (int i = 0; i < n; ++i) {
            ans += (p[i] * nums[i]) % MOD;
            ans %= MOD;
            ans -= (p[n - i - 1] * nums[i]) % MOD;
            ans %= MOD;
        }
        return (int) ans;
    }
}
// https://leetcode.cn/problems/sum-of-subsequence-widths/solutions/1977822/by-ac_oier-6tyk/

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1, M = 3e5;
int n, m, a, b, h[N], e[M], ne[M], idx, color[N], cnt[3];
void add(int u, int v) {
    e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}
int main() {
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
        scanf("%d%d", &a, &b);
        a < b ? add(a, b) : add(b, a);
    }
    bool invalid = false;
    fill(color + 1, color + 1 + n, 1);
    cnt[0] = n;
    for (int u = 1; u <= n; ++u) {
        for (int cu = color[u], i = h[u]; ~i; i = ne[i]) {
            int v = e[i], &cv = color[v];
            if (cv == cu) {
                if (cv == 1) cv = 2, --cnt[0], ++cnt[1];
                else if (cv == 2) cv = 3, --cnt[1], ++cnt[2];
                else {
                    invalid = true;
                    break;
                }
            }
        }
        if (invalid) break;
    }
    if (invalid ||
        cnt[0] * cnt[1] + cnt[0] * cnt[2] + cnt[1] * cnt[2] != m ||
        !cnt[0] || !cnt[1] || !cnt[2])
        puts("-1");
    else
        for (int i = 1; i <= n; ++i)
            printf("%d%c", color[i], i < n ? ' ' : '\n');
    return 0;
}

Posted on Edited on In

Source: USACO 2008 January Silver.

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
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1001, M = 20002;
int n, m, k, u, v, ww, h[N], e[M], w[M], ne[M], idx, dist[N];
bool st[N];
void add(int u, int v, int ww) {
    e[++idx] = v, w[idx] = ww, ne[idx] = h[u], h[u] = idx;
}
bool check(int bound) {
    memset(dist, 0x3f, sizeof(dist));
    memset(st, 0, sizeof(st));
    dist[1] = 0;
    deque<int> q;
    q.push_back(1);
    while (q.size()) {
        int u = q.front(); q.pop_front();
        if (st[u]) continue;
        st[u] = true;
        for (int i = h[u]; i; i = ne[i]) {
            int v = e[i], d = w[i] > bound;
            if (dist[v] > dist[u] + d) {
                dist[v] = dist[u] + d;
                if (!d) q.push_front(v);
                else q.push_back(v);
            }
        }
    }
    return dist[n] <= k;
}
int main() {
    scanf("%d%d%d", &n, &m, &k);
    while (m--) {
        scanf("%d%d%d", &u, &v, &ww);
        add(u, v, ww), add(v, u, ww);
    }
    int l = 0, r = 1e6 + 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    if (r == 1e6 + 1) r = -1;
    printf("%d\n", r);
    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
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
const int N = 1001, INF = 0x3f3f3f3f;
int n, m, dist[3][N][N], ds[5] = {1, 0, -1, 0, 1}, ans = INF;
char g[N][N];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%s", g[i]);
    memset(dist, 0x3f, sizeof(dist));
    for (int c = '1'; c <= '3'; ++c) {
        int idx = c - '1';
        deque<pair<int, int>> q;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                if (g[i][j] == c) {
                    dist[idx][i][j] = 0;
                    q.emplace_back(i, j);
                }
        while (q.size()) {
            auto [x, y] = q.front(); q.pop_front();
            for (int i = 0; i < 4; ++i) {
                int nx = x + ds[i], ny = y + ds[i + 1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || g[nx][ny] == '#') continue;
                int d = g[nx][ny] == '.';
                if (dist[idx][nx][ny] > dist[idx][x][y] + d) {
                    dist[idx][nx][ny] = dist[idx][x][y] + d;
                    if (d) q.emplace_back(nx, ny);
                    else q.emplace_front(nx, ny);
                }
            }
        }
    }
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (dist[0][i][j] != INF && dist[1][i][j] != INF && dist[2][i][j] != INF)
                if (g[i][j] == '.') ans = min(ans, dist[0][i][j] + dist[1][i][j] + dist[2][i][j] - 2);
                else ans = min(ans, dist[0][i][j] + dist[1][i][j] + dist[2][i][j]);
    printf("%d", ans == INF ? -1 : 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
34
35
36
37
38
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
using PII = pair<int, int>;
const int N = 1001;
int t, R, C, dist[N][N], ds[5] = {1, 0, -1, 0, 1};
char g[N][N];
int bfs() {
    memset(dist, 0x3f, sizeof(dist));
    dist[0][0] = 0;
    deque<PII> q;
    q.emplace_back(0, 0);
    while (q.size()) {
        auto [x, y] = q.front(); q.pop_front();
        for (int i = 0; i < 4; ++i) {
            int nx = x + ds[i], ny = y + ds[i + 1];
            if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
            int d = g[x][y] != g[nx][ny];
            if (dist[nx][ny] > dist[x][y] + d) {
                dist[nx][ny] = dist[x][y] + d;
                if (d) q.emplace_back(nx, ny);
                else q.emplace_front(nx, ny);
            }
        }
    }
    return dist[R - 1][C - 1];
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &R, &C);
        for (int i = 0; i < R; ++i) scanf("%s", g[i]);
        printf("%d\n", bfs());       
    }
    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
class Solution {
public:
    int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), s1 = 0, s2 = 0;
        vector<int> d(n + 1);
        for (int i = 0; i < n; ++i) {
            s1 += nums1[i], s2 += nums2[i];
            d[i + 1] = d[i] + nums1[i] - nums2[i]; // 前缀和数组记录两数组间的差值。
        }
        int ans = max(s1, s2), mind = 0, maxd = 0;
        for (int x : d) {
            ans = max(ans, s2 + (x - mind));
            ans = max(ans, s1 - (x - maxd));
            mind = min(mind, x);
            maxd = max(maxd, x);
        }
        return ans;
    }
};
0%