• https://www.facebook.com/codingcompetitions/hacker-cup/2022/round-2

Problem A. Perfectly Balanced

题意：给定一个字符串，每次询问一个子串，问是否是几乎平衡的。
几乎平衡的定义是，从子串中删除一个字符后，长度为偶数，且前半段中每个字符的出现次数与后半段相等。

A1 中字符集来自小写字符。A2 中字符集来自任意 int。

分析：再考虑弱化，如果字符集只有 {0, 1}，那么我们只要先判断下长度是否为奇数，然后枚举一下删哪个位置，然后树状数组比较一下两段 1 的个数是否一样即可。

再考虑如何不枚举删哪个位置，哪么就讨论从哪边删，然后看两边的 diff 是否是一即可。设 S(l, r) 表示 [l, r) 这个区间里 1 出现的次数，那么就是比较一下

• S(ml, r) – S(l, ml) = 1 或者
• S(l, mr) – S(mr, r) = 1。

因此对于 A1，我们只要开 25 棵树状数组就能通过。对于字符集任意的情况，我们把所有数字映射成一个随机 uint，然后看 diff 是否恰好是某个字符的映射即可。代码反而比 A1 更简单。

#include <lastweapon/bitwise>
#include <lastweapon/fenwicktree>
#include <bits/stdc++.h>

using namespace lastweapon;

mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<uint64_t> rnd(0, ULLONG_MAX);

const int N = int(1e6) + 9;

map<int, uLL> H;
set<uLL> inHash;
uLL h(int x) {
    if (!CTN(H, x)) inHash.insert(H[x] = rnd(gen));
    return H[x];
}

fenwick_tree<uLL> T;
int a[N];
int n;

int f(int l, int r) {
    if ((r-l)&1) return 0;
    int m = (l+r)/2;
    uLL L = T.sum(l), R = T.sum(r+1), ML = T.sum(m), MR = T.sum(m+1);
    return CTN(inHash, (MR-L)-(R-MR)) || CTN(inHash, (R-ML)-(ML-L));
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    Rush {
        printf("Case #%d: ", ++Case);
        H.clear(); inHash.clear();

        RD(n); T = fenwick_tree<uLL>(n+1);
        REP_1(i, n) T.add(i, h(RD(a[i])));

        int z = 0; Rush {
            int cmd, l, r; RD(cmd, l, r);
            if (cmd == 1) {
                T.add(l, h(r) - h(a[l]));
                a[l] = r;
            } else {
                z += f(l, r);
            }
        }
        printf("%d\n", z);
    }
}

Problem B. Balance Sheet

我们把 day 看成点，client 看成边，那么显然是 dag dp。
对于对于 top K 只要用 multiset 记录 dp 值即可。

const int N = int(1e6) + 9;

typedef pair<pair<int, int>, int> rec;

multiset<LL> z;

map<int, multiset<LL> > c, d;

vector<rec> e;
int a[N],b[N],x[N],y[N];

int n, k;

void fix(multiset<LL>& x) {
    while (x.size() > k) x.erase(x.begin());
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("balance_sheet_input.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    Rush {
        printf("Case #%d: ", ++Case);
        z.clear(); RD(n, k);

        c.clear(); d.clear(); e.clear();
        REP_1(i, n) {
            RD(a[i],b[i],x[i],y[i]);
            e.PB({{a[i], x[i]}, -i});
            e.PB({{b[i], y[i]}, i});
        }
        SRT(e);

        for (auto& t: e) {
            if (t.se < 0) { // buy
                int id = -t.se;
                c[id].insert(0);
                for (auto i: d[a[id]]) {
                    c[id].insert(i + x[id]);
                    fix(c[id]);
                }
                for (auto i: c[id]) {
                    z.insert(i); fix(z);
                }

            } else { // sell
                int id = t.se;
                for (auto i : c[id]) {
                    d[b[id]].insert(i - y[id]);
                    fix(d[b[id]]);
                }
            }
        }

        Int zz = 0; for (auto& t: z) zz += Int(t);
        cout << zz <<endl;
    }

}

Problem C. Balance Scale

n 袋饼干，第 i 待里有 C_i 块重 W_i 的饼干。
从所有的饼干中任取 k 个，问其中最重的一块饼干（如果有多个，任取其一）来自第一袋的概率。

Problem D. Work-Life Balance

题意：给定长度为 n 的序列 {Ai}，支持 m 次单点修改，问每次修改后至少多少次 swap 操作，可以让序列的一个给定的前缀和等于剩下部分的后缀和。

• D1 中 Ai ∈ {1,2,3}，可以交换任意位置。
• D2 中 Ai ∈ {1,2}，只可以交换相邻位置。

分析：D1 的情况显然可以贪心。

Posted by xiaodao
Category: 日常