Ortada Görüş#11431

Ortada Görüş (Həll təhlili)

Giriş massivini iki bərabər hissəyə bölün: $t_{1}, t_{2}, ..., t_{n /2}$ t_1, t_2, ..., t_{n/2} və $t_{n /2 + 1}, t_{n /2 + 2}, ..., t_{n}$ t_{n/2+1}, t_{n/2+2}, ..., t_n. Birinci hissəni $a$ massivində, ikinci hissəni isə $b$ massivində saxlayırıq.

Əvvəlcə $a$ ardıcıllığı üçün problemi həll edək. Onun bütün mümkün altməsələlərini seçək (onların sayı $2^{20}$ 2^{20} -dən çox olmayacaq). Hər altməsələ üçün onun elementlər cəmini $s$ hesablayırıq və hər belə cəm üçün $m [s]$ dəyəri $1$ artırılır. Məlumat quruluşu kimi $m$ üçün unordered_map istifadə edilə bilər. Beləliklə, $m [s]$ $a$ massivindən cəmi elementi $s$ olan altməsələni seçmənin sayı olacaq.

Sonra $b$ massivinin bütün altməsələlərini götürək. Götürək ki, $s u m$ həmin altməsələlərdən birinin elementlərinin cəmidir. Əgər bu altməsələni $a$ massivindən elementi $s - s u m$ s - sum olan bütün altməsələlərlə birləşdirərək, orijinal massivdən $s$ cəmi olan altməsələ alınırsa.

Nümunə

İkinci nümunəni nəzərdən keçirək. Giriş ardıcıllığını iki hissəyə bölək:

$a = (1, 3, 2)$ a = (1, 3, 2),
$b = (2, 1, 4)$ b = (2, 1, 4)

$a = {1, 3, 2}$ a = \{1, 3, 2\} dəstinin bütün altməsələlərini yoxlayaq:

${1} : s u m = 1, m [1] + +$ \{1\}: sum = 1, m[1]++;	${1, 2} : s u m = 3, m [3] + +$ \{1, 2\}: sum = 3, m[3]++;
${3} : s u m = 3, m [3] + +$ \{3\}: sum = 3, m[3]++;	${3, 2} : s u m = 5, m [5] + +$ \{3, 2\}: sum = 5, m[5]++;
${2} : s u m = 2, m [2] + +$ \{2\}: sum = 2, m[2]++;	${1, 3, 2} : s u m = 6, m [6] + +$ \{1, 3, 2\}: sum = 6, m[6]++;
${1, 3} : s u m = 4, m [4] + +$ \{1, 3\}: sum = 4, m[4]++;	${} : s u m = 0, m [0] + +$ \{\}: sum = 0, m[0]++;

məlumat quruluşu $m$ hissə dəstələrdən sonra aşağıdakı qiymətlərə malik olacaq:

İndi $b = {2, 1, 4}$ b = \{2, 1, 4\} dəstinin bütün altməsələlərini yoxlayaq. Bu nümunədə tələb olunan cəm $s = 7$ s = 7 bərabərdir. Hər cəm üçün, $s u m$ , $b$ altməsələsinə uyğun olan, cavablara $m [s - s u m]$ m[s - sum] dəyərini əlavə edəcəyik.

${2} : s u m = 2, m [7 - 2] = m [5] = 1$ \{2\}: sum = 2, m[7 - 2] = m[5] = 1;
${1} : s u m = 1, m [7 - 1] = m [6] = 1$ \{1\}: sum = 1, m[7 - 1] = m[6] = 1;
${4} : s u m = 4, m [7 - 4] = m [3] = 2$ \{4\}: sum = 4, m[7 - 4] = m[3] = 2;
${2, 1} : s u m = 3, m [7 - 3] = m [4] = 1$ \{2, 1\}: sum = 3, m[7 - 3] = m[4] = 1;
${2, 4} : s u m = 6, m [7 - 6] = m [1] = 1$ \{2, 4\}: sum = 6, m[7 - 6] = m[1] = 1;
${1, 4} : s u m = 5, m [7 - 5] = m [2] = 1$ \{1, 4\}: sum = 5, m[7 - 5] = m[2] = 1;
${2, 1, 4} : s u m = 7, m [7 - 7] = m [0] = 1$ \{2, 1, 4\}: sum = 7, m[7 - 7] = m[0] = 1;
${} : s u m = 0, m [7 - 0] = m [7] = 0$ \{\}: sum = 0, m[7 - 0] = m[7] = 0;

Axtarılan cəm $1 + 1 + 2 + 1 + 1 + 1 + 1 + 0 = 8$ 1 + 1 + 2 + 1 + 1 + 1 + 1 + 0 = 8, bu da cavabdır.

Alqoritmin implementasiyası

İş məlumat strukturlarını elan edək.

vector<int> a, b;
unordered_map<long long, long long> m;

Giriş məlumatlarını oxuyuruq. Ardıcılın ilk yarısını $a$ massivinə, ikinci yarısını isə $b$ massivinə daxil edirik.

scanf("%d %d", &n, &s);
a.resize(n / 2);
for (i = 0; i < n / 2; i++)
  scanf("%d", &a[i]);

b.resize(n - n / 2);
for (i = n / 2; i < n; i++)
  scanf("%d", &b[i - n / 2]);

C++

$a$ ardıcıllığının bütün altməchullarını yoxlayırıq və onların elementlərinin cəmini hesablayırıq. unordered_map quruluşunda, bu altməchullar arasında hər bir cəmin neçə dəfə tapıldığını saxlayırıq. Əgər $s u m$ cari altmëxullanın cəmidir, $m [s u m]$ dəyərini $1$ artırırıq.

for (i = 0; i < (1 << a.size()); i++)
{
  sum = 0;

$i$ dəyişəni cari $a$ altməxullunun bit maskasını ehtiva edir. Onun elementlərinin cəmi $s u m$ dəyişənində hesablanır.

      for (j = 0; j < a.size(); j++)
        if (i & (1 << j)) sum += a[j];

Tapılmış hər cəm üçün $m [s u m]$ dəyərini $1$ artırırıq.

  m[sum]++;
}

Orijinal massivin elementlərindən $s$ cəmi əldə etməyin yollarını $r es$ dəyişənində sayırıq.

res = 0;

$b$ ardıcıllığının bütün altməchullarını yoxlayırıq.

for (i = 0; i < (1 << b.size()); i++)
{
  sum = 0;

$i$ dəyişəni cari $b$ altməxullunun bit maskasını ehtiva edir. Bu altməxullunun elementlərinin cəmi $s u m$ dəyişənində hesablanır.

  for (j = 0; j < b.size(); j++)
    if (i & (1 << j)) sum += b[j];

Əgər $b$ dəstinin cəm elementləri $s u m$ olan cari altməchuları, $s - s u m$ s - sum cəm elementləri olan bütün $a$ altməchuları ilə birləşdirilsə, cəmi $s$ olan bir altməchulaq əldə edilir.

  if (m.count(s - sum) > 0) res += m[s - sum];
}

Cavabı çıxışa yazırıq.

printf("%lld\n", res);