按位或#题解 - 帖子

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;
}