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
struct F {
    int x, y, c;
    F(int x, int y, int c): x(x), y(y), c(c) {}
};
class Solution {
private:
    static constexpr int ds[5] = {1, 0, -1, 0, 1};
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        if (m == 1 && n == 1) return 0;
        if (k >= m + n - 3) return m + n - 2;
        bool vis[m][n][k + 1];
        memset(vis, false, sizeof(vis));
        queue<F> q;
        q.emplace(0, 0, k);
        vis[0][0][k] = true;
        int step = 0;
        while (q.size()) {
            ++step;
            int size = q.size();
            while (size--) {
                auto [x, y, c] = q.front(); q.pop();
                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;
                    if (nx == m - 1 && ny == n - 1) return step;
                    if (grid[nx][ny] == 0) {
                        if (vis[nx][ny][c]) continue;
                        q.emplace(nx, ny, c);
                        vis[nx][ny][c] = true;
                    } else if (c > 0 && !vis[nx][ny][c - 1]) {
                        q.emplace(nx, ny, c - 1);
                        vis[nx][ny][c - 1] = true;
                    }
                }
            }
        }
        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
class Solution {
public:
    bool hasValidPath(vector<vector<char>> &grid) {
        int m = grid.size(), n = grid[0].size();
        if (((m + n - 1) & 1) || grid[0][0] == ')' || grid[m - 1][n - 1] == '(') return false;
        bool vis[m][n][(m + n + 1) / 2];
        memset(vis, 0, sizeof(vis));
        function<bool(int, int, int)> dfs = [&](int x, int y, int c) {
            if (c > m - x + n - y + 1) return false; // pruning, too many '('.
            if (x == m - 1 && y == n - 1) return c == 1;
            if (vis[x][y][c]) return false;
            vis[x][y][c] = true;
            c += grid[x][y] == '(' ? 1 : -1;
            return c >= 0 && (x < m - 1 && dfs(x + 1, y, c) || y < n - 1 && dfs(x, y + 1, c));
        };
        return dfs(0, 0, 0);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool hasValidPath(vector<vector<char>>& grid) {
        int m = grid[0].size();
        vector<__uint128_t> f(m);
        f[0] = 1;
        for (auto &s : grid) {
            for (int i = 0; i < m; ++i) {
                if (i) f[i] |= f[i - 1];
                if (s[i] == '(') f[i] <<= 1;
                else f[i] >>= 1;
            }
        }
        return f.back() & 1;
    }
};

References:

  1. 添加状态后 DFS + 剪枝优化（Python/Java/C++/Go）
  2. __uint128_t位运算优化动态规划

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
class Solution {
    using LL = long long;
    const int MOD = 1e9 + 7;
public:
    int countTexts(string pressedKeys) {
        int n = pressedKeys.size();
        // a => press once on a key.
        // b => press twice on the same key.
        // c => press thrice on the same key.
        // d => press four times on the same key.
        LL a = 1, b = 0, c = 0, d = 0;
        for (int i = 1; i < n; ++i) {
            char x = pressedKeys[i];
            if (x != pressedKeys[i - 1]) {
                a = (a + b + c + d) % MOD;
                b = 0, c = 0, d = 0;
            } else {
                LL t = (a + b + c + d) % MOD;
                if (x == '7' || x == '9') d = c;
                c = b;
                b = a;
                a = t;
            }
        }
        return (a + b + c + d) % MOD;
    }
};

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
#include <iostream>
#include <algorithm>
using namespace std;
using PII = pair<int, int>;
const int N = 1010;
int c, n, x, y, sum[N][N];
PII points[N];
vector<int> numbers;
int get(int x) {
    return lower_bound(numbers.begin(), numbers.end(), x) - numbers.begin();
}
bool check(int len) {
    for (int x1 = 0, x2 = 1; x2 < numbers.size(); ++x2) {
        while (numbers[x2] - numbers[x1 + 1] + 1 > len) ++x1;
        for (int y1 = 0, y2 = 1; y2 < numbers.size(); ++y2) {
            while (numbers[y2] - numbers[y1 + 1] + 1 > len) ++y1;
            if (sum[x2][y2] - sum[x1][y2] - sum[x2][y1] + sum[x1][y1] >= c)
                return true;
        }
    }
    return false;
}
int main() {
    scanf("%d%d", &c, &n);
    numbers.push_back(0);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &x, &y);
        points[i] = {x, y};
        numbers.push_back(x);
        numbers.push_back(y);
    }
    sort(numbers.begin(), numbers.end());
    numbers.erase(unique(numbers.begin(), numbers.end()), numbers.end());
    for (int i = 0; i < n; ++i) {
        int x = get(points[i].first), y = get(points[i].second);
        ++sum[x][y];
    }
    for (int i = 1; i < numbers.size(); ++i)
        for (int j = 1; j < numbers.size(); ++j)
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
    int l = 1, r = 10000;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%d\n", l);
    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
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int n, m, k, tot, a[N], b[N], c[N], cnt[3 * N], langs[3 * N];
int find(int x) {
    return lower_bound(langs + 1, langs + 1 + k, x) - langs;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), langs[++tot] = a[i];
    scanf("%d", &m);
    for (int i = 1; i <= m; ++i) scanf("%d", &b[i]), langs[++tot] = b[i];
    for (int i = 1; i <= m; ++i) scanf("%d", &c[i]), langs[++tot] = c[i];
    sort(langs + 1, langs + 1 + tot);
    for (int i = 1; i <= tot; ++i) {
        langs[++k] = langs[i];
        while (i < tot && langs[i + 1] == langs[i]) ++i;
    }
    for (int i = 1; i <= n; ++i) ++cnt[find(a[i])];
    int ans = 0, m1 = 0, m2 = 0;
    for (int i = 1; i <= m; ++i) {
        int v1 = cnt[find(b[i])], v2 = cnt[find(c[i])];
        if (v1 > m1 || (v1 == m1 && v2 > m2)) {
            ans = i, m1 = v1, m2 = v2;
        }
    }
    printf("%d\n", ans ? ans : 1);
    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>
#include <algorithm>
#include <unordered_map>
using namespace std;
using PII = pair<int, int>;
const int N = 2e5 + 10, MOD = 998244353;
unordered_map<int, PII> m(N);
int n, a;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a);
        if (m.count(a)) {
            m[a].second = i;
        } else {
            m[a] = {i, i};
        }
    }
    vector<PII> v(m.size());
    int i = 0;
    for (auto &[_, p] : m) v[i++] = p;
    sort(v.begin(), v.end());
    int cnt = v.size(), pr = v[0].second;
    for (int i = 1; i < v.size(); ++i) {
        auto &[l, r] = v[i];
        if (l <= pr) pr = max(pr, r), --cnt;
        else pr = r;
    }
    long long ans = 1;
    for (int i = 1; i < cnt; ++i) ans = ans * 2 % MOD;
    printf("%lld\n", ans);
    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
#include <iostream>
#include <unordered_map>
using namespace std;
using PII = pair<int, int>;
const int N = 4e5 + 10, MOD = 998244353;
unordered_map<int, PII> m(N);
int n, a, sub[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a);
        if (m.count(a)) {
            m[a].second = i;
        } else {
            m[a] = {i, i};
        }
    }
    for (auto &[_, p] : m) {
        auto &[l, r] = p;
        ++sub[l << 1], --sub[r << 1 | 1];
    }
    int cnt = 0;
    for (int i = 1; i < N; ++i) {
        sub[i] += sub[i - 1];
        if (!sub[i - 1] && sub[i]) ++cnt;
    }
    long long ans = 1;
    for (int i = 1; i < cnt; ++i) ans = ans * 2 % MOD;
    printf("%lld\n", ans);
    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
#include <iostream>
#include <unordered_map>
using namespace std;
using PII = pair<int, int>;
const int N = 2e5 + 10, MOD = 998244353;
unordered_map<int, PII> m(N);
int n, a, f[N];
int find(int x) {
    if (f[x] != x) f[x] = find(f[x]);
    return f[x];
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a);
        if (m.count(a)) {
            m[a].second = i;
        } else {
            m[a] = {i, i};
        }
    }
    for (int i = 0; i < n; ++i) f[i] = i;
    int cnt = n;
    for (auto &[_, p] : m) {
        auto &[l, r] = p;
        int pa = find(l);
        while (pa < r) {
            f[pa] = find(pa + 1);
            pa = find(pa);
            --cnt;
        }
    }
    long long ans = 1;
    for (int i = 1; i < cnt; ++i) ans = ans * 2 % MOD;
    printf("%lld\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
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n, m, p, q, f[N], color[N];
int find(int x) {
    if (f[x] != x) f[x] = find(f[x]);
    return f[x];
}
int main() {
    scanf("%d%d%d%d", &n, &m, &p, &q);
    for (int i = 1; i <= n + 1; ++i) f[i] = i;
    for (int i = m; i > 0; --i) {
        int l = (i * p + q) % n + 1,
            r = (i * q + p) % n + 1;
        if (l > r) swap(l, r);
        int pa = find(l);
        while (pa <= r) {
            color[pa] = i;
            f[pa] = find(pa + 1);
            pa = find(pa);
        }
    }
    for (int i = 1; i <= n; ++i) printf("%d\n", color[i]);
    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
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
struct Node {
    int l, r, v;
} t[N << 2];
int n, m, p, q;
void build(int u, int l, int r) {
    t[u] = {l, r, 0};
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
void update(int u, int l, int r, int v) {
    if (t[u].v) return;
    if (t[u].l == t[u].r) t[u].v = v;
    else {
        int mid = t[u].l + t[u].r >> 1;
        if (l <= mid) update(u << 1, l, r, v);
        if (r > mid) update(u << 1 | 1, l, r, v);
        if (t[u << 1].v && t[u << 1 | 1].v) t[u].v = true;
    }
}
void output(int u) {
    if (t[u].l == t[u].r) printf("%d\n", t[u].v);
    else output(u << 1), output(u << 1 | 1);
}
int main() {
    scanf("%d%d%d%d", &n, &m, &p, &q);
    build(1, 1, n);
    for (int i = m; i; --i) {
        int l = (i * p + q) % n + 1, r = (i * q + p) % n + 1;
        if (l > r) swap(l, r);
        update(1, l, r, i);
    }
    output(1);
    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
class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) {
        map<int, int> diff;
        for (auto &f : flowers) ++diff[f[0]], --diff[f[1] + 1];
        int n = persons.size();
        vector<int> id(n);
        iota(id.begin(), id.end(), 0);
        sort(id.begin(), id.end(), [&](int i, int j) {
            return persons[i] < persons[j];
        });
        vector<int> ans(n);
        auto it = diff.begin();
        int s = 0;
        for (int i : id) {
            while (it != diff.end() && it->first <= persons[i])
                s += it++->second;
            ans[i] = s;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) {
        int n = flowers.size();
        vector<int> s(n), e(n);
        for (int i = 0; i < n; ++i) s[i] = flowers[i][0], e[i] = flowers[i][1];
        sort(s.begin(), s.end());
        sort(e.begin(), e.end());
        int m = persons.size();
        vector<int> ans(m);
        for (int i = 0; i < m; ++i) {
            ans[i] = (upper_bound(s.begin(), s.end(), persons[i]) - s.begin())
                - (lower_bound(e.begin(), e.end(), persons[i]) - e.begin());
        }
        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
struct Trie {
    unordered_map<int, Trie*> ch;
    int cnt = 0;
    int insert(vector<int>& nums, int i, int k, int p) {
        if (i == nums.size() || k - (nums[i] % p == 0) < 0)
            return 0;
        if (ch[nums[i]] == nullptr)
            ch[nums[i]] = new Trie();
        return (++ch[nums[i]]->cnt == 1) +
            ch[nums[i]]->insert(nums, i + 1, k - (nums[i] % p == 0), p);
    }
};
class Solution {
public:
    int countDistinct(vector<int>& nums, int k, int p) {
        int ans = 0;
        Trie t;
        for (int i = 0; i < nums.size(); ++i)
            ans += t.insert(nums, i, k, p);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int countDistinct(vector<int>& nums, int k, int p) {
        unordered_set<string> s;
        for(int i = 0; i < nums.size(); i++) { // start point.
            int cnt = 0;
            string tmp = "";
            for (int j = i; j < nums.size(); j++) { // end point.
                if (nums[j] % p == 0 && ++cnt > k) break;
                tmp += nums[j] + '0';
                s.insert(tmp);
            }
        }
        return s.size();
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    long long appealSum(string s) {
        int n = s.size();
        long long ans = 0L, sum = 0L;
        vector<int> pos(26, -1);
        for (int i = 0; i < n; ++i) {
            int c = s[i] - 'a';
            sum += i - pos[c];
            ans += sum;
            pos[c] = i;
        }
        return ans;
    }
};
0%