Nasser və Hədəf VƏYA (Həll təhlili)

Həll yolu

Ümumi İdeya: Məqsədimiz, bitləndirmək üçün mümkün minimum dəyişikliklər sayını tapmaqdır ki, bir çəksisubarray (alt massiv) var ki, onun OR dəyəri $k$-yə bərabərdir.

Diqqət edin ki, bit mövqeyini $p$ dəyişmək onu tərəb ilə uyğun hala gətirməklə ekvivalentdir. Beləliklə, OR dəyəri $x$ olan hər hansı bir subarray üçün tələb olunan əməliyyatların sayı sadəcə fərqli bitlərin sayıdır:

Beləliklə, vəzifə bütün mümkün subarray OR dəyərlərini səmərəli belə təhlil etməyə köçürülür.

Açar Müşahidə: Mövcud arrayın üzərində sola doğru iterasiya edərkən, bitən mövqedə subarrayların fərqli OR dəyərlərinin sayı azdır — ən çoxu təxminən $30$.

Niyə? Çünki OR tətbiq etdikcə, bitlər yalnız $0$-dan $1$-ə dəyişə bilər. Çünki tam ədədlərin ən çoxu $30$ biti var, hər bit yalnız bir dəfə təyin edilə bilər.

Algoritm: Hazırki indeksdə bitən altmassivlər üçün fərqli OR dəyərlərini təqdim edən bir cütləri başda bir vector saxlayın.

Hər element üçün:

• OR $a[i]$-yə bərabər yeni bir subarray başlayın.

• Bunu əvvəllər saxlanılan dəyərlərlə OR edin.

• Vector-un kiçik saxlanılması üçün dublikatları birləşdirin.

• Hər OR dəyəri $x$ üçün, \text{popcount}(x \oplus k) hesablayın və cavabı yeniləyin.

Nəhayət, ən yaxşı OR dəyəri ilə $k$ arasında fərqli olan bit mövqelərini çıxış edin.

Mürəkkəblik Analizi:

Görünür ki, biz çox alt massivləri yoxlayırıq, amma hər indeksdə fərqli OR dəyərlərinin sayı bitlərin sayı ilə məhdudlaşdırılıb (ən çoxu $30$).

Hər $n$ elementlər üçün, ən çox $30$ fərqli OR dəyərləri prosesi edirik.

Bu səbəbdən, vaxt mürəkkəbliyi belədir:

Yaddaş mürəkkəbliyi: Hər mövqedə fərqli OR dəyərləri saxlamaqda \mathcal{O}(30) = \mathcal{O}(1).

Əsas İcraatı

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    vector<pair<int, int>> v; 
    int ans = 30, pos = 0;
    
    for (int i = 1; i <= n; i++) {
        vector<pair<int, int>> u;
        u.push_back({a[i], 1});
        
        for (auto [x, c] : v) {
            int g = (x | a[i]);
            if (g == u.back().first) {
                u.back().second = c;
            } else {
                u.push_back({g, c});
            }
        }
        
        v = u;
        
        for (auto [x, c] : v) {
            int cnt = (x ^ k);
            int res = __builtin_popcount(cnt);
            if (res <= ans) {
                ans = res;
                pos = cnt;
            }
        }
    }
    
    cout << ans << "\n";
    for (int i = 0; i < 30; i++) {
        if (pos & (1 << i)) {
            cout << i << " ";
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
        cout << "\n";
    }
    return 0;
}