CodeForces Round 888

​
E. Nastya and Potions [Medium] 题解

F. Lisa and the Martians [Hard] 题解

Problem - E - Codeforces

需要n个药水用于做实验，第i个药水价值cost[i]。

再给你k个药水下标，表示这些药水都是免费的（学生福利）。

最后告诉你每个药水不仅可以直接买，还可以通过其他药水合成。

问你分别得到每个药水费用最小值。

思路

经典的dp问题，将费用分为两种情况：

1. 直接购买
2. 通过其他合成

两者取最小即可，可以直接记忆化搜索（写起来快）。

代码

vector<int> a, cost;
vector<vector<int>> g;
ll dp(int x){
    if (a[x] != -1) return a[x];
    ll min_cost = cost[x]; // 直接购买
    // 如果直接购买费用不为0且可以通过其他合成->递归搜索
    if (min_cost != 0 && g[x].size() != 0){
        ll sum = 0;
        for (int pre : g[x]){
            sum += dp(pre);
        }
        min_cost = min(min_cost, sum);
    }
    a[x] = min_cost;
    return a[x];
}
void solve(){
    cin >> n >> k;
    a.resize(n + 1); a.assign(n + 1, -1);
    cost.resize(n + 1); cost.assign(n + 1, 0);
    g.resize(n + 1); g.assign(n + 1, vector<int>());
    for (int i = 1;i <= n;i++){
         cin >> cost[i];
    }
    for (int i = 0;i < k;i++){
        int tp = 0; cin >> tp;
        cost[tp] = 0;
    }
    for (int i = 1;i <= n;i++){
        int cnt = 0; cin >> cnt;
        for (int j = 0;j < cnt;j++){
            int cur = 0; cin >> cur;
            g[i].push_back(cur);
        }
    }
    for (int i = 1;i <= n;i++){
        p(dp(i));
    }
    nl;
}

复杂度分析

• 时间复杂度: O(n) 。
• 空间复杂度: O(n) 。

---

Problem - F - Codeforces

给你n个数字，每个数字二进制表示都是k位。

求一个整数x，使得(a_i ⊕ x)&(a_j ⊕ x)最大。

思路

1. 因为最后会&， 所以我们尽量要让两个数字高位都为1，这样最后才会尽可能大。
2. 又因为两边数字都会异或x，要为1的话就对应位需要和x不同。
3. 即a_i和a_j要求从高到低对应位尽量相同，与x尽量不同。
4. 即求出a_i和a_j的同或最大值即可，x可以根据这两个数中任意一个构造。
5. 此时可以通过字典树来解决。

代码

struct trie{
    trie* next[2] = {nullptr, nullptr};
    int x; //保存走到这个位置上的数的下标
};
trie* root;
int find(int t, int dx){
    trie* cur = root;
    int x = 0, f = 0;
    for (int i = k-1;i >= 0;i--){
        int bit = (t >> i & 1);
        if (cur->next[bit] == nullptr){
            cur->next[bit] = new trie();
            f = 1;
        }else{
            if (f == 0 || x == -1){
                x = cur->next[bit]->x;   
            }
        }
        cur->next[bit]->x = dx;
        cur = cur->next[bit];
    }
    if (x == 0) x = 1;
    return x;
}
// 计算同或
int cal(int x, int y){
    int res = 0;
    for (int i = k-1;i >= 0;i--){
        int bit1 = (x >> i & 1);
        int bit2 = (y >> i & 1);
        res |= (bit1^bit2^1) << i;
    }
    return res;
}
void solve(){
    cin >> n >> k;
    root = new trie();
    int ans = 0, x = 0, y = 0, z = 0;
    for (int i = 1;i <= n;i++){
        int t = 0; cin >> t;
        a[i] = t;
        int res = find(t, i);
        int maxv = cal(t, a[res]);
        if (i > 1 && ans <= maxv){
            ans = maxv;
            x = i, y = res;
        }
    }
    // 翻转二进制位
    for (int i = k-1;i >= 0;i--){
        int bit = (a[x] >> i & 1) ^ 1;
        z |= bit << i;
    }
    p(x);p(y);pl(z);
}

复杂度分析

• 时间复杂度: O(nk) 。
• 空间复杂度: O(n) 。