Tushuntirish

Markazda birlashtirish sport dasturlashda mashhur texnikalardan hisoblanadi. Markazda birlashtirish berilgan sohani teng ikkiga bo'lib qidiradigan texnika. Har bir qismda qidiruv alohida o'tkaziladi va yakunida javoblar birlashtiriladi.

Bu texnikani yaxshiroq tushunish uchun bu https://cses.fi/problemset/task/1628 masalani tushunib yechishga harakat qilib ko'raylik. Masala sharti quyidagicha: Sizga a massiv (massiv elementlari noldan katta) va x (noldan katta) soni berilgan. Massiv ichida elementlari yig'indisi x ga teng bo'lgan, qism massivlar sonini chiqarishingiz kerak. Masala shartida n<=40 (massiv uzunligi) berilgan, demak agar biz berilgan massivning barcha qism massivlarini hosil qilsak ularning soni 2^n == 2^40 == 1099511627776 ga teng bo'ladi. Tabiiyki buni hosil qilish masalada berilgan vaqt va xotiraga to'g'ri kelmaydi.

Yechim

Uzunligi 40 bo'lgan massivning qism massivlarini hosil qila olmasak ham, uzunligi 20 bo'lgan 2 ta massivning qism massivlarini hosil qila olamiz. Demak bu yerda markazda birlashtirish texnikasidan foydalanamiz. Birinchi navbatda massivni (deyarli) teng ikkiga bo'lamiz, hosil bo'lgan 2 massiv har biridan, qism massivlarning elementlari yig'indisini bir massivga joylaymiz. Pastda buni qanday qilinganini ko'ring:

a = [1, 2, 3, 4, 5, 6]
a1 = [1, 2, 3]
a2 = [4, 5, 6]

a1 massivining qism massivlari
{[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]}

Har bir qism massiv yig'indisi:
q1 = [0, 1, 2, 3, 3, 4, 5, 6]

a2 massivining qism massivlari
{[], [4], [5], [6], [4, 5], [4, 6], [5, 6], [4, 5, 6]}

Har bir qism massiv yig'indisi:
q2 = [0, 4, 5, 6, 9, 10, 11, 15]

Qism massivlarni qanday hosil qilish mumkinligini avvalgi maqolaladan o'qib o'rganishingiz mumkin. https://onecompiler.com/posts/438chnjpz

Endi ikkala massiv qism massivlari yig'indisini birlashtirishga kelsak. Hosil bo'lgan 2 massiv orasidan, xohlagan birini tanlab sikl orqali aylanib chiqamiz, keling hozir q1 ni tanlaylik. Aylanayotganda agar biz kelgan indeksdagi element q1[i] x dan katta bo'lsa shunchaki bu sonni e'tiborsiz qoldiramiz, aks holda ikkinchi massiv q2 ichida x-q1[i] sonidan nechtaligini topamiz va javobga qo'shib ketamiz. Masalan tepada keltirilgan massivni x=10 bo'lgan holati uchun hisoblab ko'rsak.

q1 = [0, 1, 2, 3, 3, 4, 5, 6]
q2 = [0, 4, 5, 6, 9, 10, 11, 15]

0-indeks uchun 0 soni 10 dan katta emas demak q2 ichidagi 10-0 dan nechtaligi => 1 ta
1-indeks uchun 1 soni 10 dan katta emas demak q2 ichidagi 10-1 dan nechtaligi => 1 ta
2-indeks uchun 2 soni 10 dan katta emas demak q2 ichidagi 10-2 dan nechtaligi => 0 ta
3-indeks uchun 3 soni 10 dan katta emas demak q2 ichidagi 10-3 dan nechtaligi => 0 ta
4-indeks uchun 3 soni 10 dan katta emas demak q2 ichidagi 10-3 dan nechtaligi => 0 ta
5-indeks uchun 4 soni 10 dan katta emas demak q2 ichidagi 10-4 dan nechtaligi => 1 ta
6-indeks uchun 5 soni 10 dan katta emas demak q2 ichidagi 10-5 dan nechtaligi => 1 ta
7-indeks uchun 6 soni 10 dan katta emas demak q2 ichidagi 10-6 dan nechtaligi => 1 ta

Umumiy qilganda jami 5 ta qism massiv yig'indisi x ga ya'ni 10 ga teng.

Kodda yozish

Qism massivlarni hosil qilish maqolasida ko'rganingizdek bu yerda ham xuddi shunday hosil qilindi, lekin bu yerda qism massivlar yig'indisi, qism massivlar hosil qilinayotgan paytning o'zida hisoblab ketilgan. Sababi vaqt va xotiradan kamroq joy olish uchun.

q2 massiv ichida x-q1[i] dan nechta mavjudligini topish uchun binar qidiruvdan foydalanildi. Foydalanilgan upper_bound va lower_bound haqida qisqacha.

lower_bound funksiyasi berilgan son masalan k uchun sortlangan massiv ichida eng chap tarafda turgan k dan kichik bo'lmagan sonning indeksini qaytaradi.

upper_bound funksiyasi berilgan son masalan k uchun sortlangan massiv ichida eng chap tarafda turgan k dan katta birinchi sonning indeksini qaytaradi.

Shunday qilib upper_bound funksiyasidan qaytgan indeksdan lower_bound funksiyasidan qaytgan indeksni ayirganda k sonidan q2 massivida nechta borligini chiqaradi. Quyida kod bilan tanishib chiqishingiz mumkin.

vector<ll> subsets_sum(vector<int> &nums){
    vector<ll> q;
    int n=nums.size();
    for(int i=0; i<(1<<n); i++){
        ll sm=0;
        for(int j=0; j<n; j++){
            if(i&(1<<j)) sm+=nums[j];
        }
        q.push_back(sm);
    }
    return q;
}

void solution()
{
    int n, x; cin >> n >> x;
    vector<int> a(n);
    for(int i=0; i<n; i++) cin >> a[i];
    vector<int> a1, a2;
    for(int i=0; i<n/2; i++) a1.push_back(a[i]);
    for(int i=n/2; i<n; i++) a2.push_back(a[i]);
    
    vector<ll> q1=subsets_sum(a1);
    vector<ll> q2=subsets_sum(a2);
    sort(q1.begin(), q1.end());
    sort(q2.begin(), q2.end());
    ll res=0;
    for(int i=0; i<q1.size(); i++){
        if(q1[i]>x) continue;
        auto it1=lower_bound(q2.begin(), q2.end(), x-q1[i]);
        auto it2=upper_bound(q2.begin(), q2.end(), x-q1[i]);
        res+=it2-it1;
    }
    cout << res;
}

Foydalanilgan saytlar:

codeforces.com
usaco.guide
cses.fi