7.12 模拟赛 G 题题解

wusixuan · 2025-07-12 18:47:46 · 题解

题目：WiFi Password

别人的二分+ST表都是 O(n \log n) 的，我来一个 O(n \log V) 的做法。

观察到 OR 值随着区间的增长而不会减少，所以区间扩张满足单调性，所以考虑尺取法。

尺取法只需要顺便维护 OR 值即可。

多测要清空！！！

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int cnt[30];
int n, x;
int a[N];

int get() {
    int ans = 0;
    for (int i = 29; i >= 0; i--)
        if (cnt[i] >= 1)
            ans += (1 << i);
    return ans;
}

int main() {
    freopen("wifi.in", "r", stdin);
    int t;
    cin >> t;
    while (t--) {
        cin >> n >> x;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        for (int i = 0; i <= 29; i++)
            cnt[i] = 0;
        int ans = 0;
        for (int l = 1, r = 0; l <= n; l++) {
            while (r < n) {
                r++;
                for (int i = 0; i <= 29; i++)
                    if (a[r] & (1 << i))
                        cnt[i]++;
//              cout << l << " " << r << " " << get() << endl;
                if (get() > x) {
                    for (int i = 0; i <= 29; i++)
                        if (a[r] & (1 << i))
                            cnt[i]--;
                    r--;
                    break;
                }
            }
            if (get() <= x)
                ans = max(ans, r - l + 1);
            for (int i = 0; i <= 29; i++)
                if (a[l] & (1 << i))
                    cnt[i]--;
        }
        cout << ans << endl;
    }
    return 0;
}