December 2022 Algorithm Solution

Missing Coin Sum Queries

题目链接：CSES - Missing Coin Sum Queries
题目大意：给定 n 个硬币，每个硬币都有一个价值 aia_i ，q 次询问，每次询问求只使用某一段子区间硬币的子集所不能凑出的最小价值
解题思路：只有一次询问的做法是把硬币价值从小到大排序，定义 ans=0ans=0 ，遍历价值为 aia_i 的硬币时，如果 ans+1<aians+1<a_i ，就代表 ans+1ans+1 无法凑出来，直接输出答案即可

可以发现如果 ans+1≥aians+1\ge a_i ，那么[ai,ans+ai+1][a_i,ans+a_i+1] 都可以凑到，将所有硬币分成 30 层，每层为 [2i,2i+1)[2^i,2^{i+1}) ，遍历每一层，设这一层的最小值为 x ，如果 ans+1≥xans+1\ge x ，那么这一层所有的硬币都可以加入到答案中，只需要用一个维护区间最小值的数据结构，如果使用并查集离线处理的话，复杂度应该是 O(30(n+q)α(n))O(30(n+q)\alpha(n))

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
const int logC = 30;
int n, q;
int c[N], a[N][logC + 1], ls[N], fa[N][logC + 1];
ll t[N][logC + 1], ans[N];
vector<int> rs[N];
stack<int> st[logC + 1];
inline int get(int id, int x) {
    return x == fa[x][id] ? x : (fa[x][id] = get(id, fa[x][id]));
}
signed main() {
    cin.sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> q;
    lep(i, 1, n) {
        cin >> c[i];
        int id = __lg(c[i]);
        a[i][id] = c[i];
        t[i][id] = c[i];
    }
    lep(id, 0, logC) {
        lep(i, 1, n) {
            a[i][id] = (a[i][id] == 0 ? INF : a[i][id]);
            t[i][id] += t[i - 1][id];
            fa[i][id] = i;
        }
    }
    lep(i, 1, q) {
        int l, r;
        cin >> l >> r;
        rs[r].emplace_back(i);
        ls[i] = l;
    }
    lep(i, 1, n) {
        lep(id, 0, logC) {
            while (st[id].size() && a[st[id].top()][id] >= a[i][id]) {
                fa[st[id].top()][id] = i;
                st[id].pop();
            }
            st[id].push(i);
        }
        for (auto k : rs[i]) {
            ll res = 0;
            lep(id, 0, logC) {
                int minn = a[get(id, ls[k])][id];
                if (minn == INF) minn = 0;
                if (res + 1 >= minn) {
                    res += t[i][id] - t[ls[k] - 1][id];
                } else
                    break;
            }
            ans[k] = res + 1;
        }
    }
    lep(i, 1, q) cout << ans[i] << endl;
    return 0;
}

Balance Update Query

题目链接：https://atcoder.jp/contests/abc287/tasks/abc287_g

题目大意：有 n 种卡片，给定每种卡片的价值 v 和数量 p ，有以下三种操作

  • 1 x y 表示把第 x 种卡片的价值改成 y
  • 2 x y 表示把第 x 种卡片的数量改成 y
  • 3 x 表示拿 x 张卡片的最大价值和，如果不足 x 张输出 -1

解题思路：权值线段树，先把价值离散化，根据价值建立线段树，每个节点存储价值为 i 的卡片数量以及卡片数量和价值的乘积，对于前两个操作只需要维护单点修改即可，对于操作三可以在线段树上二分，时间复杂度为 O(nlogn)O(nlogn)

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#define int ll
int mp[N];
struct segment {
    int l;
    int r;
    int sum;
    int num;
    int lazy_inc;
} tr[N << 2];

void increase(int rt, int v) {
    int l = tr[rt].l, r = tr[rt].r;
    tr[rt].num += (r - l + 1) * v;
    tr[rt].sum = mp[l] * tr[rt].num;
    tr[rt].lazy_inc += v;
}
void pushdown(int rt) {
    if (tr[rt].lazy_inc) {
        increase(rt << 1, tr[rt].lazy_inc);
        increase(rt << 1 | 1, tr[rt].lazy_inc);
        tr[rt].lazy_inc = 0;
    }
}
void pushup(int rt) {
    tr[rt].sum = tr[rt << 1].sum + tr[rt << 1 | 1].sum;
    tr[rt].num = tr[rt << 1].num + tr[rt << 1 | 1].num;
}
void build(int rt, int l, int r) { 
    tr[rt].l = l;
    tr[rt].r = r;
    tr[rt].lazy_inc = 0;
    if (l == r) {
        tr[rt].sum = tr[rt].num = 0;
        return;
    }
    int mid = (l + r) >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    pushup(rt);
}
void add(int rt, int l, int r, int v) { 
    if (l > tr[rt].r || tr[rt].l > r) return;
    if (l <= tr[rt].l && tr[rt].r <= r) {
        increase(rt, v);
        return;
    }
    pushdown(rt);
    add(rt << 1, l, r, v);
    add(rt << 1 | 1, l, r, v);
    pushup(rt);
}
int get_num(int rt, int l, int r) {  
    if (l > tr[rt].r || tr[rt].l > r) return 0;
    if (l <= tr[rt].l && tr[rt].r <= r) {
        return tr[rt].num;
    }
    pushdown(rt);
    int lsum = get_num(rt << 1, l, r);
    int rsum = get_num(rt << 1 | 1, l, r);
    pushup(rt);
    return lsum + rsum;
}
int get_sum(int rt, int l, int r) {
    if (l > tr[rt].r || tr[rt].l > r) return 0;
    if (l <= tr[rt].l && tr[rt].r <= r) {
        return tr[rt].sum;
    }
    pushdown(rt);
    int lsum = get_sum(rt << 1, l, r);
    int rsum = get_sum(rt << 1 | 1, l, r);
    pushup(rt);
    return lsum + rsum;
}
int get(int rt, int x) {
    if (tr[rt].l == tr[rt].r) return tr[rt].l;
    if (tr[rt << 1 | 1].num < x) return get(rt << 1, x - tr[rt << 1 | 1].num);
    return get(rt << 1 | 1, x);
}
PII a[N];
vector<int> que[N], b;
void solve() {
    int n, q;
    cin >> n;
    vector<int> id;
    lep(i, 1, n) {
        cin >> a[i].first >> a[i].second;
        id.emplace_back(a[i].first);
    }
    cin >> q;
    lep(i, 1, q) {
        int op, x, y;
        cin >> op;
        if (op == 3) {
            cin >> x;
            que[i].emplace_back(op);
            que[i].emplace_back(x);
        } else {
            cin >> x >> y;
            que[i].emplace_back(op);
            que[i].emplace_back(x);
            que[i].emplace_back(y);
            if (op == 1) id.emplace_back(y);
        }
    }
    b = id;
    sort(b.begin(), b.end());
    unique(b.begin(),b.end());
    int cnt = b.size();
    auto ask = [](auto x) {
        return lower_bound(b.begin(), b.end(), x) - b.begin() + 1;
    };
    build(1, 1, cnt);
    for (auto i : id) mp[ask(i)] = i;
    lep(i, 1, n) add(1, ask(a[i].first), ask(a[i].first), a[i].second);
    lep(i, 1, q) {
        if (que[i][0] == 1) {
            int k = que[i][1], v = que[i][2];
            int id = ask(a[k].first);
            add(1, id, id, -a[k].second);
            a[k].first = v;
            id = ask(a[k].first);
            add(1, id, id, a[k].second);
        } else if (que[i][0] == 2) {
            int k = que[i][1], v = que[i][2];
            int id = ask(a[k].first);
            add(1, id, id, -a[k].second);
            a[k].second = v;
            add(1, id, id, a[k].second);
        } else {
            if (tr[1].num < que[i][1]) {
                cout << -1 << endl;
            } else {
                int id = get(1, que[i][1]);
                cout << get_sum(1, id, cnt) -
                            (get_num(1, id, cnt) - que[i][1]) * mp[id]
                     << endl;
            }
        }
    }
}

Grid Paths

题目链接：CSES - Grid Paths

题目大意：给定一个 n*n 的矩阵，有 m 个障碍物，只能向下或向右走，问从(1,1) 走到 (n,n) 有多少不同的路径

解题思路：如果没有障碍物的话，可以往下走 n-1 次，往右走也是同理，那么总路径数就是 Cn+n−2n−1C_{n+n-2}^{n-1}

设 dp[i] 表示不经过其他障碍物到达第 i 个障碍物的路径数，从反面求

考虑以下两种情况

1
2
3
s.k.
.j..
...i

显然 s→j→is\to j\to i 和 s→k→is\to k\to i 的路径是不会重复的

1
2
3
sk..
..j.
...i

根据定义 s→js\to j 是不会经过 k 的，那么 s→j→is\to j\to i 和 s→k→is\to k\to i 的路径也是不会重复的

因此对于任意两个在 i 左上角的障碍物，经过他们到达 i 的路径是不同的

那么就可以得到

dp[i]=Cxi+yj−2xi−1−∑xj≤xi,yj≤yidp[j]∗Cxi+yi−xj−yjxi−xjdp[i]=C_{x_i+y_j-2}^{x_i-1}-\sum_{x_j\le x_i,y_j\le yi} dp[j]*C_{x_i+y_i-x_j-y_j}^{x_i-x_j}

把所有障碍物按 x,y 从小到大排序，然后顺序 dp

把终点也当做障碍物，那么答案就是该点的 dp 值

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
ll A[N], S[N], inv[N];
ll qpow(ll a, ll n) {
    ll res = 1;
    while (n) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
void INIT(int n) {
    A[0] = S[0] = 1;
    lep(i, 1, n) A[i] = A[i - 1] * i % mod;
    for (int i = 1; i <= n; ++i) S[i] = S[i - 1] * A[i] % mod;
    inv[n] = qpow(S[n], mod - 2);
    for (int i = n; i >= 1; --i) inv[i - 1] = inv[i] * A[i] % mod;
    for (int i = 1; i <= n; ++i) inv[i] = inv[i] * S[i - 1] % mod;
}
ll C(ll n, ll m) { return A[n] * inv[m] % mod * inv[n - m] % mod; }
ll n, m;
ll dp[N];
void solve() {
    cin >> n >> m;
    INIT(2 * n);
    vector<pii> a;
    lep(i, 1, m) {
        int u, v;
        cin >> u >> v;
        a.emplace_back(u, v);
    }
    a.emplace_back(n, n);
    sort(all(a));
    lep(i, 0, m) {
        ll res = C(a[i].fi + a[i].se - 2, a[i].fi - 1);
        lep(j, 0, i - 1) {
            if (a[i].fi >= a[j].fi && a[i].se >= a[j].se) {
                res = (((res - (dp[j] * C(a[i].fi - a[j].fi + a[i].se - a[j].se,
                                          a[i].fi - a[j].fi)) %
                                   mod)) %
                           mod +
                       mod) %
                      mod;
            }
        }
        dp[i] = res;
    }
    cout << dp[m] << endl;
}

最少得分子序列

题目链接：最少得分子序列

题目大意：给定两个字符串 s 和 t ，可以从 t 中删去任意字符，定义 left 是删去的字符串中最小的下标，right 是删去的字符串中最大的下标，字符串的得分为 right - left + 1 ，找到使 t 成为 s 子序列的最小得分。

解题思路：先求出两个数组 pre 和 suf ，分别表示 t 的前缀和 s 的前缀所匹配的最小下标与 t 的后缀和 s 后缀所匹配的最大下标，然后就可以通过二分或者双指针求解了，二分的话，如果删除 k 个字符符合条件，那么删除包含这 k 个字符的一段，也一定符合条件，且得分保持不变，二分的判定就是删除长为 mid 的子段，然后查询剩下的前缀和后缀与 s 匹配的区间有没有交集

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
int minimumScore(string s, string t) {
    int n = s.size(), m = t.size();
    s = "#" + s + "#";
    t = "#" + t + "#";
    vector<int> pre(m + 2, 0), suf(m + 2, 0);
    int id = 0;
    for (int i = 0; i <= m + 1; i++) {
        while (s[id] != t[i] && id <= n) id++;
        pre[i] = id;
        if (id <= n) id++;
    }
    id = n + 1;
    for (int i = m + 1; i >= 0; i--) {
        while (s[id] != t[i] && id >= 1) id--;
        suf[i] = id;
        if (id >= 1) id--;
    }
    int l = 0, r = m;
    while (l < r) {
        int mid = (l + r) >> 1;
        int f = 0;
        for (int i = 0; i <= m - mid; i++) {
            if (pre[i] < suf[i + mid + 1]) f = 1;
        }
        if (f)
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}
Algorithm Solution
Algorithm

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！