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
35
36
37
38
39
40
41
42
43
44
const int N = 1000, M = N * 2;
int h[N], e[M], ne[M], idx;
class Solution {
public:
    int ans = 1e9;
    vector<int> w;
    void add(int u, int v) {
        e[idx] = v, ne[idx] = h[u], h[u] = idx++;
    }
    int dfs(int u, int f, int sumx, int sumy) {
        int res = w[u];
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (v == f) continue;
            int t = dfs(v, u, sumx, sumy);
            res ^= t;
            if (sumx != -1) {
                int a[3] = {sumy, t, sumx ^ t};
                sort(a, a + 3);
                ans = min(ans, a[2] - a[0]);
            }
        }
        return res;
    }
    int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
        int n = nums.size();
        w = nums;
        for (int i = 0; i < n - 1; ++i) { // 枚举被删除的边。
            memset(h, -1, n * 4);
            idx = 0;
            for (int j = 0; j < n - 1; ++j) { // 建图。
                if (i != j) {
                    int u = edges[j][0], v = edges[j][1];
                    add(u, v), add(v, u);
                }
            }
            int x = edges[i][0], y = edges[i][1]; // 以被删除的边的两个端点分别作为根节点进行 DFS 计算分数。
            int sumx = dfs(x, -1, -1, -1), sumy = dfs(y, -1, -1, -1);
            dfs(x, -1, sumx, sumy); // 假设分割 x 子树，计算分数。
            dfs(y, -1, sumy, sumx); // 假设分割 y 子树，计算分数。
        }
        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
38
39
40
// Reference: https://leetcode.cn/problems/minimum-score-after-removals-on-a-tree/solution/dfs-shi-jian-chuo-chu-li-shu-shang-wen-t-x1kk/
class Solution {
public:
    int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
        // 建图。
        int n = nums.size();
        vector<vector<int>> g(n);
        for (auto &e : edges) {
            int u = e[0], v = e[1];
            g[u].push_back(v);
            g[v].push_back(u);
        }
        int xr[n], in[n], out[n], clock = 0;
        function<void(int, int)> dfs = [&](int u, int f) {
            in[u] = ++clock;
            xr[u] = nums[u];
            for (int v : g[u])
                if (v != f) {
                    dfs(v, u);
                    xr[u] ^= xr[v];
                }
            out[u] = clock;
        };
        // 以 0 为根遍历并记录节点访问次序。
        dfs(0, -1);
        // 根据访问次序判断节点父子关系。
        auto is_ancestor = [&](int x, int y) -> bool { return in[x] < in[y] && in[y] <= out[x]; };
        int ans = INT_MAX;
        // 枚举删除的两条边所对应的端点（四个点中的两个子点，因此 0 除外）。
        for (int i = 2, x, y, z; i < n; ++i) // 枚举被删除的点 i。
            for (int j = 1; j < i; ++j) { // 枚举被删除的另一个点 j。
                if (is_ancestor(i, j)) x = xr[j], y = xr[i] ^ x, z = xr[0] ^ xr[i]; // i 是 j 的父节点。
                else if (is_ancestor(j, i)) x = xr[i], y = xr[j] ^ x, z = xr[0] ^ xr[j]; // j 是 i 的父节点。
                else x = xr[i], y = xr[j], z = xr[0] ^ x ^ y; // 删除的两条边分属于两个子树。
                ans = min(ans, max({x, y, z}) - min({x, y, z}));
                if (ans == 0) return 0; // 剪枝。
            }
        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
const int N = 1e4 + 1, MOD = 1e9 + 7;
int f[N][7][7];
bool valid[7][7];
class Solution {
public:
    int distinctSequences(int n) {
        fill(valid[0], valid[6] + 7, 1);
        valid[2][4] = valid[2][6] = valid[3][6] = valid[4][2] = valid[4][6] = valid[6][2] = valid[6][3] = valid[6][4] = false;
        function<int(int, int, int)> dfs = [&](int n, int p1, int p2) {
            if (n == 0) return 1;
            if (f[n][p1][p2]) return f[n][p1][p2];
            int res = 0;
            for (int x = 1; x <= 6; ++x)
                if (x != p1 && x != p2 && valid[p2][x])
                    res = (res + dfs(n - 1, p2, x)) % MOD;
            f[n][p1][p2] = res;
            return res;
        };
        return dfs(n, 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
24
25
26
27
28
29
// Reference: https://leetcode.cn/problems/number-of-distinct-roll-sequences/solution/by-endlesscheng-tgkn/
const int MOD = 1e9 + 7, MX = 1e4;
int f[MX + 1][6][6];
int init = []() {
    for (int i = 0; i < 6; ++i)
        for (int j = 0; j < 6; ++j)
            if (j != i && gcd(j + 1, i + 1) == 1)
                f[2][i][j] = 1;
    for (int i = 2; i < MX; ++i)
        for (int j = 0; j < 6; ++j)
            for (int last = 0; last < 6; ++last)
                if (last != j && gcd(last + 1, j + 1) == 1)
                    for (int last2 = 0; last2 < 6; ++last2)
                        if (last2 != j && last2 != last)
                            f[i + 1][j][last] = (f[i + 1][j][last] + f[i][last][last2]) % MOD;
    return 0;
}();

class Solution {
public:
    int distinctSequences(int n) {
        if (n == 1) return 6;
        int ans = 0;
        for (int i = 0; i < 6; ++i)
            for (int j = 0; j < 6; ++j)
                ans = (ans + f[n][i][j]) % MOD;
        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
// Reference: https://leetcode.cn/problems/number-of-distinct-roll-sequences/solution/by-endlesscheng-tgkn/
const int MOD = 1e9 + 7, MX = 1e4;
int f[MX + 1][6];
int init = []() {
    for (int i = 0; i < 6; ++i)
        f[1][i] = 1;
    for (int i = 2; i <= MX; ++i)
        for (int j = 0; j < 6; ++j) {
            long s = 0L;
            for (int k = 0; k < 6; ++k)
                if (k != j && gcd(k + 1, j + 1) == 1)
                    s += f[i - 1][k] - f[i - 2][j];
            if (i > 3) s += f[i - 2][j];
            f[i][j] = s % MOD;
        }
    return 0;
}();

class Solution {
public:
    int distinctSequences(int n) {
        long ans = 0L;
        for (int v : f[n])
            ans += v;
        return (ans % MOD + MOD) % MOD;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
class Solution {
public:
    int longestSubsequence(string s, int k) {
        int n = s.size(), m = 32 - __builtin_clz(k);
        if (n < m) return n;
        int ans = stoi(s.substr(n - m), nullptr, 2) <= k ? m : m - 1;
        return ans + count(s.begin(), s.end() - m, '0');
    }
};

Posted on Edited on In

原题：POJ 1742 Coins

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
const int N = 101, M = 100001;
int n, m, w[N], s[N], num[M], f[M], ans;
int main() {
    while (scanf("%d%d", &n, &m), n) {
        for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
        for (int i = 1; i <= n; ++i) scanf("%d", &s[i]);
        memset(f, false, sizeof(f));
        f[0] = true;
        ans = 0;
        for (int i = 1; i <= n; ++i) {
            memset(num, 0, sizeof(num));
            for (int j = w[i]; j <= m; ++j)
                if (!f[j] && f[j - w[i]] && num[j - w[i]] < s[i]) {
                    f[j] = true;
                    num[j] = num[j - w[i]] + 1;
                    ++ans;
                }
        }
        printf("%d\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
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
const int N = 100001;
int n, m, x, y, dist[N];
vector<PII> g[N];
priority_queue<PII, vector<PII>, greater<PII>> q;
int main() {
    scanf("%d%d", &n, &m);
    while (m--) {
        scanf("%d%d", &x, &y);
        g[x].emplace_back(y, 0);
        g[y].emplace_back(x, 1);
    }
    memset(dist, 0x3f, sizeof(dist));
    q.emplace(0, 1);
    dist[1] = 0;
    while (q.size()) {
        auto p = q.top(); q.pop();
        int d = p.first, u = p.second;
        for (auto &x : g[u]) {
            int v = x.first, w = x.second;
            if (dist[v] > d + w) {
                dist[v] = d + w;
                q.emplace(dist[v], v);
            }
        }
    }
    printf("%d\n", dist[n] == 0x3f3f3f3f ? -1 : dist[n]);
    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
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
const int N = 100001;
int n, m, x, y, dist[N];
vector<PII> g[N];
queue<int> q;
bool vis[N];
int main() {
    scanf("%d%d", &n, &m);
    while (m--) {
        scanf("%d%d", &x, &y);
        g[x].emplace_back(y, 0);
        g[y].emplace_back(x, 1);
    }
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    q.emplace(1);
    while (q.size()) {
        int u = q.front(); q.pop();
        vis[u] = false;
        for (auto &x : g[u]) {
            int v = x.first, w = x.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!vis[v])
                    q.emplace(v), vis[v] = true;
            }
        }
    }
    printf("%d\n", dist[n] == 0x3f3f3f3f ? -1 : dist[n]);
    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
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
const int N = 100001;
int n, m, x, y, dist[N];
vector<pair<int, int>> g[N];
deque<int> q;
int main() {
    scanf("%d%d", &n, &m);
    while (m--) {
        scanf("%d%d", &x, &y);
        g[x].emplace_back(y, 0);
        g[y].emplace_back(x, 1);
    }
    memset(dist, 0x3f, sizeof(dist));
    q.emplace_back(1);
    dist[1] = 0;
    while (q.size()) {
        auto u = q.front(); q.pop_front();
        for (auto &x : g[u]) {
            int v = x.first, w = x.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (w) q.emplace_back(v);
                else q.emplace_front(v);
            }
        }
    }
    printf("%d\n", dist[n] == 0x3f3f3f3f ? -1 : dist[n]);
    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
class Solution {
    using TII = tuple<int, int, int>;
public:
    int minCost(vector<vector<int>>& grid) {
        // 1->right, 2->left, 3->down, 4->up.
        int m = grid.size(), n = grid[0].size(), ds[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        vector<vector<int>> dist(m, vector<int>(n, 0x3f3f3f3f));
        vector<vector<bool>> vis(m, vector<bool>(n));
        dist[0][0] = 0;
        priority_queue<TII, vector<TII>, greater<TII>> q;
        q.emplace(0, 0, 0);
        while (q.size()) {
            auto [d, x, y] = q.top(); q.pop();
            if (vis[x][y]) continue;
            vis[x][y] = true;
            for (int i = 0; i < 4; ++i) {
                int nx = x + ds[i][0], ny = y + ds[i][1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                int w = grid[x][y] != i + 1;
                if (dist[nx][ny] > dist[x][y] + w) {
                    dist[nx][ny] = dist[x][y] + w;
                    q.emplace(dist[nx][ny], nx, ny);
                }
            }
        }
        return dist[m - 1][n - 1];
    }
};
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
class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        // 1->right, 2->left, 3->down, 4->up.
        int m = grid.size(), n = grid[0].size(), ds[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        vector<vector<int>> dist(m, vector<int>(n, 0x3f3f3f3f));
        // vector<vector<bool>> vis(m, vector<bool>(n));
        dist[0][0] = 0;
        deque<pair<int, int>> q;
        q.emplace_back(0, 0);
        while (q.size()) {
            auto [x, y] = q.front(); q.pop_front();
            // if (vis[x][y]) continue;
            // vis[x][y] = true;
            for (int i = 0; i < 4; ++i) {
                int nx = x + ds[i][0], ny = y + ds[i][1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                int w = grid[x][y] != i + 1;
                if (dist[nx][ny] > dist[x][y] + w) {
                    dist[nx][ny] = dist[x][y] + w;
                    if (w) q.emplace_back(nx, ny);
                    else q.emplace_front(nx, ny);
                }
            }
        }
        return dist[m - 1][n - 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
class Solution {
public:
    int minimumObstacles(vector<vector<int>> &grid) {
        int m = grid.size(), n = grid[0].size(), ds[] = {1, 0, -1, 0, 1};
        vector<vector<int>> dist(m, vector<int>(n, 0x3f3f3f3f));
        dist[0][0] = 0;
        deque<pair<int, int>> q;
        q.emplace_front(0, 0);
        while (!q.empty()) {
            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 >= m || ny < 0 || ny >= n) continue;
                int w = grid[nx][ny];
                if (dist[nx][ny] > dist[x][y] + w) {
                    dist[nx][ny] = dist[x][y] + w;
                    if (w == 0) q.emplace_front(nx, ny);
                    else q.emplace_back(nx, ny);
                }
            }
        }
        return dist[m - 1][n - 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
33
34
35
36
37
38
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2002;
int n, m, r, c, x, y, dist[N][N], ans, ds[] = {1, 0, -1, 0, 1};
char s[N][N];
deque<pair<int, int>> q;
int main() {
    scanf("%d%d%d%d%d%d", &n, &m, &r, &c, &x, &y);
    for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
    memset(dist, 0x3f, sizeof(dist));
    dist[r][c] = 0;
    q.emplace_back(r, c);
    while (q.size()) {
        auto [r, c] = q.front(); q.pop_front();
        for (int i = 0; i < 4; ++i) {
            int nr = r + ds[i], nc = c + ds[i + 1];
            if (nr <= 0 || nr > n || nc <= 0 || nc > m || s[nr][nc] == '*') continue;
            int w = 0;
            if (i == 3) w = 1; // when r + 0 and c + 1.
            if (dist[nr][nc] > dist[r][c] + w) {
                dist[nr][nc] = dist[r][c] + w;
                if (w) q.emplace_back(nr, nc);
                else q.emplace_front(nr, nc);
            }
        }
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            int b = dist[i][j];
            if (b <= y && b + c - j <= x)
                ++ans;
        }
    printf("%d\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
27
28
#include <iostream>
#include <cmath>
using namespace std;
int a, b;
int cnt(int n) {
    int res = 0;
    while (n) ++res, n /= 10;
    return res;
}
int cnt(int n, int x) {
    int res = 0, d = cnt(n);
    for (int i = 1; i <= d; ++i) {
        int p = pow(10, i - 1), l = n / p / 10, r = n % p, di = n / p % 10;
        if (x) res += l * p;
        else if (l) res += (l - 1) * p;
        if (di > x && (x || l)) res += p;
        else if (di == x && (x || l)) res += r + 1;
    }
    return res;
}
int main() {
    while (scanf("%d%d", &a, &b), a) {
        if (a > b) swap(a, b);
        for (int i = 0; i <= 9; ++i)
            printf("%d%c", cnt(b, i) - cnt(a - 1, i), i == 9 ? '\n' : ' ');
    }
    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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
using LL = long long;
const int N = 2e5;
const LL INF = -1e15;
int t, n, a[N], pg[N], ng[N];
LL ps[N], ss[N];
void nextGreater() { // Get and save index of next gerater number into ng[].
    stack<int> s;
    for (int i = 0; i < n; ++i) {
        ng[i] = n;
        while (s.size() && a[s.top()] < a[i]) {
            ng[s.top()] = i;
            s.pop();
        }
        s.push(i);
    }
}
void prevGreater() { // Get and save index of previous gerater number into pg[].
    stack<int> s;
    for (int i = n - 1; i >= 0; --i) {
        pg[i] = -1;
        while (s.size() && a[s.top()] < a[i]) {
            pg[s.top()] = i;
            s.pop();
        }
        s.push(i);
    }
}
// Query segment tree to get maximum prefix/suffix sum within a[L, R].
LL query(vector<LL> &tree, int u, int l, int r, int L, int R) {
    if (R < l || L > r) return INF;
    if (L <= l && r <= R) return tree[u];
    int mid = (l + r) >> 1;
    LL ans = INF;
    ans = max(ans, query(tree, u << 1, l, mid, L, R));
    ans = max(ans, query(tree, u << 1 | 1, mid + 1, r, L, R));
    return ans;
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
        ps[0] = a[0];
        for (int i = 1; i < n; ++i) ps[i] = ps[i - 1] + a[i];
        ss[n - 1] = a[n - 1];
        for (int i = n - 2; i >= 0; --i) ss[i] = ss[i + 1] + a[i];
        // Round off n to next power of 2.
        int _n = n;
        while (__builtin_popcount(_n) != 1) _n++;
        // Two segment trees to store maximum prefix/suffix sum.
        vector<LL> pt(2 * _n, INF), st(2 * _n, INF);
        // Initiate value of root nodes.
        for (int i = 0; i < n; ++i) pt[_n + i] = ps[i], st[_n + i] = ss[i];
        // Push up.
        for (int i = _n - 1; i >= 1; --i) {
            pt[i] = max(pt[i << 1], pt[i << 1 | 1]);
            st[i] = max(st[i << 1], st[i << 1 | 1]);
        }
        nextGreater();
        prevGreater();
        bool flag = true;
        for (int i = 0; i < n; ++i) {
            LL rightMax = query(pt, 1, 0, _n - 1, i + 1, ng[i] - 1) - ps[i];
            if (rightMax > 0) {
                flag = false;
                break;
            }
            LL leftMax = query(st, 1, 0, _n - 1, pg[i] + 1, i - 1) - ss[i];
            if (leftMax > 0) {
                flag = false;
                break;
            }
        }
        printf(flag ? "YES\n" : "NO\n");
    }
    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
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <cmath>
using namespace std;
using LL = long long;
const int N = 2e5, M = 18;
const LL INF = -1e15;
int t, n, a[N], pg[N], ng[N];
LL ps[N], ss[N], f[2][N][M];
void nextGreater() { // Get and save index of next gerater number into ng[].
    stack<int> s;
    for (int i = 0; i < n; ++i) {
        ng[i] = n;
        while (s.size() && a[s.top()] < a[i]) {
            ng[s.top()] = i;
            s.pop();
        }
        s.push(i);
    }
}
void prevGreater() { // Get and save index of previous gerater number into pg[].
    stack<int> s;
    for (int i = n - 1; i >= 0; --i) {
        pg[i] = -1;
        while (s.size() && a[s.top()] < a[i]) {
            pg[s.top()] = i;
            s.pop();
        }
        s.push(i);
    }
}
void init() {
    for (int j = 0; j < M; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
            if (!j) f[0][i][j] = ps[i - 1], f[1][i][j] = ss[i - 1];
            else
                f[0][i][j] = max(f[0][i][j - 1], f[0][i + (1 << (j - 1))][j - 1]),
                f[1][i][j] = max(f[1][i][j - 1], f[1][i + (1 << (j - 1))][j - 1]);
}
LL query(int t, int l, int r) {
    if (l > r) return INF;
    int k = log2(r - l + 1);
    return max(f[t][l][k], f[t][r - (1 << k) + 1][k]);
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
        ps[0] = a[0];
        for (int i = 1; i < n; ++i) ps[i] = ps[i - 1] + a[i];
        ss[n - 1] = a[n - 1];
        for (int i = n - 2; i >= 0; --i) ss[i] = ss[i + 1] + a[i];
        nextGreater();
        prevGreater();
        init();
        bool flag = true;
        for (int i = 0; i < n; ++i) {
            LL rightMax = query(0, i + 2, ng[i]) - ps[i];
            if (rightMax > 0) {
                flag = false;
                break;
            }
            LL leftMax = query(1, pg[i] + 2, i) - ss[i];
            if (leftMax > 0) {
                flag = false;
                break;
            }
        }
        printf(flag ? "YES\n" : "NO\n");
    }
    return 0;
}
0%