按位或#题解

admin 2024-12-17 23:02:03 2024-12-20 15:18:21

Hint1

最暴力的 的算法你是否能优化到 ? 虽然仍然过不了本题,但对于下一步优化有很大的参考意义

Hint2

按位或 ( 按位与 , 都有这个性质)对于本题有什么比较有用的性质,能够优化到 来通过本题?

Solution

本题考察 按位或的性质 + 去重

对于本题有用的一个按位或性质如下:

满足 1 范围的 的二进制至多只有 位,而按位或则是对 位里面的每一位进行操作,对于两个数中的某一位来说,只要有一位有 或两个数的这一位都是 ,或的结果就是 ,从中我们就可以分析出,无限长的数组中所有的连续子数组(必须从第一个下标开始)按位或得到或的结果最多只有 个状态,最极限的情况也只是 的幂次方进行或,例如 ,我们连续异或了 次,每次其实只改了 位,但是总共也才 位, 不管你怎么改,最终你也只能改 位(这个过程是不可逆向的,改为 的位不可能再变成 ),而这个性质其实就是将复杂度 中的一个 优化到 的巧妙思想。

知道了按位或的性质,我们将利用dp的思想,巧妙利用到该性质。

对于 我们定义为结尾都必须包含第 个的所有连续子数组的或的结果(注意里面存储的是多个或的结果)

例如对于 个整数的数组 , , ,

那么答案其实就是 中所有的数全部放在一起,并且去重,然后计算其中小于k的个数。

转移规律就是 (注意 里面存储的是多个或的结果), 这是因为 是必须结尾包含 ,那么求 结尾必须包含 的所有连续子数组,就只需要把 或上 中所有存储的结果

上述思路看起来完全正确 , 但是我们会发现 中,随着 的增加其存储个数会急剧,因为根据转移规律来看,每次都会或上前面 中存储的所有数,如果不处理,时间会超时,内存也会爆炸

而根据我们得到的按位或性质, 中会有很多重复的东西,去重之后个数一定不会超过 个,因此求一次 时间接近 ,求完 时间复杂度就是 即可通过本题,下述代码中通过 容器去重,也可以 去重,也可以使用其他的去重算法。

C++代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 10);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<set<int>> mp(n + 10);
    for (int i = 1; i <= n; i++) {
        if (a[i] >= k)
            continue;
        mp[i].insert(a[i]);
        if (i >= 2) {
            for (auto j : mp[i - 1]) {
                mp[i].insert((a[i] | j));
            }
        }
    }
    set<int> ans;
    for (int i = 1; i <= n; i++) {
        for (auto j : mp[i]) {
            ans.insert(j);
        }
    }
    int cnt = 0;
    for (auto i : ans) {
        if (i < k)
            cnt++;
    }
    cout << cnt << endl;
}
signed main() {
    int t = 1;
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    //	cin>>t;
    while (t--) solve();
    return 0;
}