Stack Weights

题目链接：https://cses.fi/problemset/task/2425

题目大意：你有 n 枚硬币，每一个都有不同的重量，硬币的编号为 1-n ，第 i 枚硬币的重量大于第 i-1 枚硬币

有两个堆栈最初是空的。在每一步中，您将一枚硬币移到一堆。你永远不会从堆栈中取出硬币。

每次移动后，您的任务是确定哪个堆栈更重（如果我们可以确定哪个堆栈更重）。

解题思路：定义 $l_i$ 表示左堆重量大于第 i 枚硬币的数量， $r_i$ 表示右堆重量大于第 i 枚硬币的数量，如果确定左堆的重量小于右堆，必须满足 $\forall i ,li\le ri$ 。因此可以定义 $a_i=l_i-r_i$

$\forall i，a_i\ge0$ 说明左堆重
$\forall i，a_i\le0$ 说明右堆重
无法确定

因此可以用线段树维护区间最大最小值，对于放入硬币 x ,它的前缀加一或减一，然后判断最大最小值是否满足即可

int n, h;
PII t[2 * N];
int d[N];
void apply(int p, int value) {
    t[p].fi += value;
    t[p].se += value;
    if (p < n) d[p] += value;
}
void build(int p) {
    while (p > 1) {
        p >>= 1;
        t[p].fi = min(t[p << 1].fi, t[p << 1 | 1].fi) + d[p];
        t[p].se = max(t[p << 1].se, t[p << 1 | 1].se) + d[p];
    }
}
void push(int p) {
    for (int s = h; s > 0; --s) {
        int i = p >> s;
        if (d[i] != 0) {
            apply(i << 1, d[i]);
            apply(i << 1 | 1, d[i]);
            d[i] = 0;
        }
    }
}
void inc(int l, int r, int value) { 
    l += n, r += n;
    int l0 = l, r0 = r;
    for (; l < r; l >>= 1, r >>= 1) {
        if (l & 1) apply(l++, value);
        if (r & 1) apply(--r, value);
    }
    build(l0);
    build(r0 - 1);
}
int query_min(int l, int r) {  
    l += n, r += n;
    push(l);
    push(r - 1);
    int res = 2e9;
    for (; l < r; l >>= 1, r >>= 1) {
        if (l & 1) res = min(res, t[l++].fi);
        if (r & 1) res = min(t[--r].fi, res);
    }
    return res;
}
int query_max(int l, int r) {  
    l += n, r += n;
    push(l);
    push(r - 1);
    int res = -2e9;
    for (; l < r; l >>= 1, r >>= 1) {
        if (l & 1) res = max(res, t[l++].se);
        if (r & 1) res = max(t[--r].se, res);
    }
    return res;
}
void solve() {
    cin >> n;
    h = sizeof(int) * 8 - __builtin_clz(n);
    lep(i, 1, n) {
        int x, opt;
        cin >> x >> opt;
        if (opt == 1)
            inc(0, x, 1);
        else
            inc(0, x, -1);
        int a = query_min(0, n);
        int b = query_max(0, n);
        if (a >= 0) {
            cout << '>' << endl;
            continue;
        }
        if (b <= 0) {
            cout << '<' << endl;
            continue;
        }
        cout << '?' << endl;
    }
}

Programmers and Artists

题目链接：https://cses.fi/problemset/task/2426

题目大意：一家公司想招人，a 个程序员和 b 个艺术家，共有 n 个申请人，每个申请人都可以成为程序员或艺术家。你知道每个申请人的编程和艺术技能。你的任务是选择新员工，使他们的技能总和最大化。

解题思路：将所有人按编程能力从大到小排序，如果第 i 个人是最后一个程序员，那么 i 之前的都应该有职业，否则我可以让那个没有职业的人和 i 交换，这样答案可以更优。定义 pre[i] 表示从前面选择 a 个程序员，其余都是艺术家的最优答案，suf[i] 表示在 i 之后的人中选择剩余的艺术家的最优答案，用一个优先队列可以计算，最大答案就是 pre[i]+suf[i+1]

ll a, b, n, pre[N], suf[N];
pair<ll, ll> v[N];
void solve() {
    cin >> a >> b >> n;
    lep(i, 1, n) cin >> v[i].fi >> v[i].se;
    sort(v + 1, v + 1 + n, greater<>());
    ll sum = 0;
    priority_queue<ll> q;
    lep(i, 1, a+b) {
        sum += v[i].se;
        sum += v[i].fi - v[i].se;
        q.push(-(v[i].fi - v[i].se));
        while (q.size() > a) {
            sum += q.top();
            q.pop();
        }
        pre[i] = sum;
    }
    sum = 0;
    q = priority_queue<ll>();
    rep(i, n, a) {
        q.push(v[i].se);
        while (q.size() > n-a-b) {
            sum += q.top();
            q.pop();
        }
        suf[i] = sum;
    }
    ll ans = 0;
    lep(i, a, a+b) ans = max(ans, pre[i] + suf[i + 1]);
    cout << ans << endl;
}

Backpack

题目链接：https://acm.hdu.edu.cn/showproblem.php?pid=7140

题目大意：给你 n 个物品，每个物品都有 $v_i$ 的重量和 $w_i$ 的价值，以及一个容量为 m 的背包，求把背包装满时包内物品价值的最大异或和

解题思路：dp+bitset优化，定义 $dp[i][j][k]$ 表示前 i 个物品中选了总重量为 k 的物品且最大异或和为 j 的状态是否存在，那么 $dp[i-1][j][k]=dp[i-1][j][k]|dp[i-1][j \oplus w][k-v]$ .这是三维的，可以用 bitset 优化，考虑 k-v 可以变成位的左移。定义 $bitset<2^{10}>f[2^{10}],g[2^{10}]$ , $f[i][j]$ 表示异或和为 i 重量为 j 的状态， $g[i][j]$ 表示上一步的状态，直接或一下即可

int n, m;
bitset<1030> f[1030], g[1030];
void solve() {
    cin >> n >> m;
    int v, w;
    lep(i,0,1024) f[i].reset();
    f[0][0] = 1;
    lep(i, 1, n) {
        cin >> v >> w;
        lep(j, 0, 1024) {
            g[j] = f[j];
            g[j] <<= v;
        }
        lep(j, 0, 1024) f[j] |= g[j ^ w];
    }
    int ans = -1;
    lep(i, 0, 1024) if (f[i][m]) ans = i;
    cout << ans << endl;
}

Package Delivery

题目链接：https://acm.hdu.edu.cn/showproblem.php?pid=7170

题目大意：你有 n 个快递，存放在驿站，每个快递都有到达时间和带回家的最后期限，你每天可以去驿站多次，但是每次最多只能拿 k 个快递，问拿所有快递最少需要去驿站多少次

解题思路：对于每个快递，我们在它截止日期那一天去拿，并且优先拿这一天截止的快递，设这一天截止的快递有 cnt 个，如果 cnt 是 k 的倍数，显然就拿这 cnt 个是最优的，否则我们应该尽可能拿那些已经到了且快要截止的快递，凑到 k 个。具体做法是将快递分别按照到达时间和截止时间排序，枚举所有的截止时间，用一个优先队列维护即可

int n, k;
void solve() {
    cin >> n >> k;
    vector<PII> a(n);
    vector<int> end(n);
    priority_queue<int, vector<int>, greater<int>> q;
    lep(i, 0, n - 1) cin >> a[i].fi >> a[i].se, end[i] = a[i].se;
    sort(a.begin(), a.end());
    sort(end.begin(), end.end());
    int id = 0, ans = 0;
    for (auto t : end) {
        int cnt = 0;
        while (id < n && a[id].fi <= t) q.push(a[id++].se);
        while (q.size() && q.top() == t) cnt++, q.pop();
        ans += cnt / k;
        if (cnt % k == 0) continue;
        int res = k - cnt % k;
        while (q.size() && res--) q.pop();
        ans++;
    }
    cout << ans << endl;
}

Algorithm Solution

Algorithm

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

August 2022 Algorithm Solution 上一篇

June 2022 Algorithm Solution 下一篇

July 2022 Algorithm Solution

Stack Weights

Programmers and Artists

Backpack

Package Delivery