sosdp题集

1. 165E - Compatible Numbers Compatible Numbers

由于 , 那么显然找 的子集必然满足条件。不妨令 表示 的子集里存在于所给序列中的某一个，枚举子集即可。

/*
 * @Author: Kurisu
 */
#include<bits/stdc++.h>
const int mod = 1e9 + 7;
const int N = (1 << 23) + 5;

int a[N], dp[N];

void solve() {
    int n; std::cin >> n;
    int bits = (1 << 23) - 1;
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        dp[a[i]] = a[i];
    }
    for (int j = 0; j <= bits; j++) {
        for (int i = 0; i <= 23; i++) {
            if (dp[j]) { // 已经有了
                continue;
            }
            if (j & (1 << i)) {
                dp[j] |= dp[j ^ (1 << i)];
            }
        }
    }
    for (int i = 0; i <= n; i++) {
        if (!dp[i]) {
            dp[i] = -1;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (dp[bits ^ a[i]]) { // 补集的子集存在于所给序列中
            std::cout << dp[bits ^ a[i]] << ' ';
        } else {
            std::cout << -1 << ' ';
        }
    }
    std::cout << '\n';
}

signed main() {
    std::cin.sync_with_stdio(false), std::cin.tie(nullptr);
    int T = 1; //std::cin >> T;
    while (T--) {
        solve();
    } 
    return 0;
}

2. 1208F - Bits And Pieces

对 做 ，只要有大于等于两个元素即可与 得到某一位的贡献，枚举 ，从高位往低位，找到哪一位 不具有并且满足大于等于两个元素即可加上这一位。

/*
 * @Author: Kurisu
 */
#include<bits/stdc++.h>
const int mod = 1e9 + 7;
const int N = (1 << 22) + 5;

int a[N], b[N];

void insert(int bits, int x) {
    if (b[x] >= 2) {
        return ;
    }
    if (bits == -1) {
        b[x]++;
        return ;
    }
    if (x & (1 << bits)) {
        insert(bits - 1, x);
        insert(bits - 1, x ^ (1 << bits));
    } else {
        insert(bits - 1, x);
    }
}

int get(int bits, int x) {
    int ans = 0, cur = 0;
    for (int i = 21; i >= 0; i--) {
        if (!(x & (1 << i))) { $这一位没有$ 
            cur |= (1 << i);
            if (b[cur] >= 2) { // 满足条件
                ans |= (1 << i);
            } else { // 无法做到，返回
                cur ^= (1 << i);
            }
        }
    }
    return ans;
}

void solve() {
    int n; std::cin >> n;
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    int ans = 0;
    for (int i = n; i >= 1; i--) {
        if (i <= n - 2) {
            ans = std::max(ans, a[i] | get(21, a[i]));
        }
        insert(21, a[i]);
    }
    std::cout << ans << '\n';
}

signed main() {
    std::cin.sync_with_stdio(false), std::cin.tie(nullptr);
    int T = 1; //std::cin >> T;
    while (T--) {
        solve();
    } 
    return 0;
}

3. arc 100E

要求 ，显然 是 的一个子集，令 表示 的所有子集里 的最大值，一直取 就可以了。

/*
 * @Author: Kurisu
 */
#include<bits/stdc++.h>
const int mod = 1e9 + 7;
const int N = (1 << 18) + 5;

std::pair<int, int> dp[N];
int a[N];

auto merge(std::pair<int, int> x, std::pair<int, int> y) {
    std::pair<int, int> res = std::max(x, y);
    if (res.second < std::min(x, y).first) {
        res.second = std::min(x, y).first;
    }
    return res;
}

void solve() {
    int n; std::cin >> n;
    for (int i = 0; i < (1 << n); i++) {
        std::cin >> a[i];
        dp[i] = std::make_pair(a[i], -1e9);
    }
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < (1 << n); i++) {
            if (i & (1 << j)) {
                dp[i] = merge(dp[i], dp[i ^ (1 << j)]); // 子集
            }
        }
    }
    int ans = 0;
    for (int i = 1; i < (1 << n); i++) {
        ans = std::max(ans, dp[i].first + dp[i].second); // <= k,取 max
        std::cout << ans << '\n';
    }
}

signed main() {
    std::cin.sync_with_stdio(false), std::cin.tie(nullptr);
    int T = 1; //std::cin >> T;
    while (T--) {
        solve();
    } 
    return 0;
}

4. 449D - Jzzhu and Numbers

令 为按位与和至少为 的状态数量，显然可以用 处理出来，这些状态要么取，要么不取，总共有 种可能，最后容斥一下得到结果为 的方案。

/*
 * @Author: Kurisu
 */
#include<bits/stdc++.h>
const int mod = 1e9 + 7;
const int N = (1 << 22) + 5;

int a[N], dp[N];
long long qpow(long long a, long long b) {
    long long res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
int get1(int x) {
    return (__builtin_popcount(x) & 1) ? -1 : 1;
}
void solve() {
    int n; std::cin >> n;
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i], dp[a[i]]++;
    }
    for (int i = 0; i <= 20; i++) {
        for (int j = (1 << 20); j >= 0; j--) {
            if (!(j & (1 << i))) { // 子集:1的位置可以是0，超集:0的位置可以是1
                dp[j] = (dp[j] + dp[j | (1 << i)]) % mod; // 可以由超集转化而来
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < (1 << 20); i++) { // 容斥
        ans = (ans + get1(i) * (qpow(2, dp[i]) - 1)) % mod;
        ans = (ans + mod) % mod;     
    }
    std::cout << ans << '\n';
}

signed main() {
    std::cin.sync_with_stdio(false), std::cin.tie(nullptr);
    int T = 1; //std::cin >> T;
    while (T--) {
        solve();
    } 
    return 0;
}