Shawn's Blog

Posted on Edited on In

今天吃瓜吃得很开心，却发现没什么人能分享的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 201;
int n, m, t, f[N][N];
int main() {
    scanf("%d%d%d", &n, &m, &t);
    for (int i = 0, v, w; i < n; ++i) {
        scanf("%d%d", &v, &w);
        for (int j = m; j >= v; --j)
            for (int k = t; k >= w; --k)
                f[j][k] = max(f[j][k], f[j - v][k - w] + 1);
    }
    printf("%d\n", f[m][t]);
    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
class Solution {
    static constexpr int N = 1e5 + 1;
    struct Node {
        int l, r, cnt1;
        bool flip;
    } tr[N << 2];
    void pushup(int u) {
        tr[u].cnt1 = tr[u << 1].cnt1 + tr[u << 1 | 1].cnt1;
    }
    void build(vector<int>& nums, int u, int l, int r) {
        tr[u] = {l, r, 0};
        if (l == r) {
            tr[u].cnt1 = nums[l - 1];
        } else {
            int mid = (l + r) >> 1;
            build(nums, u << 1, l, mid), build(nums, u << 1 | 1, mid + 1, r);
            pushup(u);
        }
    }
    void reverse(int u) {
        tr[u].cnt1 = tr[u].r - tr[u].l + 1 - tr[u].cnt1;
        tr[u].flip = !tr[u].flip;
    }
    void update(int u, int L, int R) {
        if (L <= tr[u].l && tr[u].r <= R) {
            reverse(u);
        } else {
            int mid = (tr[u].l + tr[u].r) >> 1;
            if (tr[u].flip) {
                reverse(u << 1), reverse(u << 1 | 1);
                tr[u].flip = false;
            }
            if (L <= mid) update(u << 1, L, R);
            if (mid < R)  update(u << 1 | 1, L, R);
            pushup(u);
        }
    }
public:
    vector<long long> handleQuery(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
        int n = nums1.size();
        build(nums1, 1, 1, n);
        vector<long long> ans;
        long long sum = accumulate(nums2.begin(), nums2.end(), 0ll);
        for (auto &q : queries) {
            if (q[0] == 1) update(1, q[1] + 1, q[2] + 1);
            else if (q[0] == 2) sum += 1ll * q[1] * tr[1].cnt1;
            else ans.push_back(sum);
        }
        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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int INF = 1000;
int n, ans = INF;
LL x;
void dfs(LL x, int d) {
    bool st[10] = {0};
    int cnt = 0;
    for (LL y = x; y; y /= 10) {
        ++cnt;
        st[y % 10] = 1;
    }
    if (d + n - cnt >= ans) return;
    if (cnt == n) {
        ans = d;
        return;
    }
    for (int i = 9; i >= 2; --i)
        if (st[i])
            dfs(x * i, d + 1);
}
int main() {
    scanf("%d%lld", &n, &x);
    dfs(x, 0);
    if (ans == INF) ans = -1;
    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
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
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
const int N = 50000;
int n, k, ans;
struct Node {
    int p;
    int c;
} cow[N];
priority_queue<int, vector<int>, greater<int>> dq; // 折扣小根堆
priority_queue<PII, vector<PII>, greater<PII>> cq, pq; // [折后价,坐标]小根堆，[原价,坐标]小根堆
long long m, cost;
bool st[N];
int main() {
    scanf("%d%d%lld", &n, &k, &m);
    for (int i = 0; i < n; ++i) scanf("%d%d", &cow[i].p, &cow[i].c);
    sort(cow, cow + n, [](Node a, Node b) {
        return a.c < b.c; // 按折后价排序
    });
    for (int i = 0; i < k; ++i) { // 尽可能将 k 个优惠券用掉
        cost += cow[i].c;
        if (cost > m) {
            printf("%d\n", i);
            return 0;
        }
        dq.push(cow[i].p - cow[i].c);
    }
    if (k == n) {
        printf("%d\n", n);
        return 0;
    }
    for (int i = k; i < n; ++i) {
        cq.emplace(cow[i].c, i);
        pq.emplace(cow[i].p, i);
    }
    int ans = k;
    // 将剩下的钱花掉，要保持每一笔花费尽可能小，以此买更多的牛
    for (int i = k; i < n; ++i) {
        // 已买过的不再考虑购买
        while (st[cq.top().second]) cq.pop();
        while (st[pq.top().second]) pq.pop();
        auto [c, ci] = cq.top();
        auto [p, pi] = pq.top();
        // 要么用优惠券买 cow[ci]，花费 c，还需要原价购买 dp.top() 对应的牛
        int t1 = c + dq.top();
        // 要么买价格最小的，花费 p
        int t2 = p;
        if (t1 < t2) { // 前者花费更少
            cost += t1;
            dq.pop();
            dq.push(cow[ci].p - cow[ci].c);
            st[ci] = 1;
        } else { // 后者花费更少
            cost += t2;
            st[pi] = 1;
        }
        ++ans;
        if (cost > m) {
            printf("%d\n", ans - 1);
            return 0;
        }
    }
    printf("%d\n", 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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1, M = 2 * N, K = 21;
int n, k, u, v;
int c[N], h[N], e[M], ne[M], idx;
int dp[N][K];
void add(int u, int v) {
    e[++idx] = v, ne[idx] = h[u], h[u] = idx;
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i < n; ++i) {
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    for (int i = 1; i <= n; ++i) scanf("%d", &c[i]);
    function<void(int, int)> dfs = [&](int u, int f) {
        dp[u][0] = c[u];
        for (int i = h[u]; i; i = ne[i]) {
            int v = e[i];
            if (v != f) {
                dfs(v, u);
                for (int j = 1; j <= k; ++j)
                    dp[u][j] += dp[v][j - 1];
            }
        }
    };
    dfs(1, 0);
    function<void(int, int)> reroot = [&](int u, int f) {
        for (int i = h[u]; i; i = ne[i]) {
            int v = e[i];
            if (v != f) {
                for (int j = k; j >= 2; --j)
                    dp[v][j] -= dp[v][j - 2]; // 容斥定理
                for (int j = 1; j <= k; ++j)
                    dp[v][j] += dp[u][j - 1];
                reroot(v, u);
            }
        }
    };
    reroot(1, 0);
    for (int i = 1; i <= n; ++i)
        printf("%d\n", accumulate(dp[i], dp[i] + k + 1, 0));
    return 0;
}
0%