Array masukan : 5,2,7,100,1090,1,3,6,4,1062 (array berindeks 0)

Tugas : Untuk barisan bilangan bulat positif tertentu, saya ingin mencari jumlah tiga kali lipat (i,j,k) sedemikian hingga 1 i < j k ≤ N dan

A[i]^…^A[j]−1=A[j]^A[j]+1^…^A[k], di mana ^ menunjukkan XOR bit bijaksana.

Saya sudah mencoba masalah menggunakan array dan peta prefix_xor di C++ tetapi saya masih perlu meningkatkan kompleksitas waktu.

cin >> n;
int A[n];
ll count = 0;
unordered_map<int, vector<int>> map_table;
for (int i = 0; i < n; ++i)
    cin >> A[i];
map_table[A[0]].push_back(0);
for (int i = 1; i < n; ++i)
{
    A[i] = A[i] ^ A[i-1];
    if (!A[i])
        count += i;
    map_table[A[i]].push_back(i);
}
unordered_map<int, vector<int>>::iterator i2; 
for (i2 = map_table.begin(); i2 != map_table.end(); ++i2)
{
    int size = i2->second.size();
    if (size >= 2)
    {
        for (int i = 0; i < size-1; ++i)
        {
            for (int k = i+1; k < size; ++k)
                count += ((i2->second[k])-(i2->second[i])-1);
        }
    }
}
cout << count << '\n';

Dalam contoh ini jawabannya adalah 20

[0,2], [5,8], [0,9], [3,9]

XOR(5, 2, 7) = 0; XOR(1, 3, 6, 4) = 0; XOR(100, 1090, .... 1062) = 0; XOR(5, 2, 7 .... 1062) = 0

3
Obi Wan Kenobi 6 Agustus 2019, 20:17

1 menjawab

Jawaban Terbaik

Saya akan mengoptimalkan bagian kode Anda ini:

for (int i = 0; i < size-1; ++i)
{
    for (int k = i+1; k < size; ++k)
        count += ((i2->second[k])-(i2->second[i])-1);
}

Perhatikan bahwa pada dasarnya Anda mencoba mencari jumlah perbedaan antara setiap pasangan angka dalam larik (i2->second). Anda melakukan ini di O(n^2), tetapi jika kita sedikit memanipulasi rumus, kita bisa melakukannya lebih cepat.

Katakanlah array kita, yang akan kita panggil a untuk saat ini, memiliki panjang n. Kami hanya akan fokus pada elemen ke i(diindeks 0) untuk saat ini, dan kami akan menghitung berapa kali elemen tersebut ditambahkan dan dikurangi dari jumlah. Untuk setiap j < i, jumlah total akan mencakup a[i] - a[j]. Demikian pula, untuk setiap j > i, jumlah total termasuk a[j] - a[i]. Dalam kasus sebelumnya, a[i] ditambahkan sebanyak i kali. Dalam kasus terakhir, a[i] dikurangi sebanyak n - i - 1 kali. Jadi koefisien a[i] dalam jumlah total (berapa kali ditambah dikurangi berapa kali dikurangi) adalah i - (n - i - 1) == 2 * i - n + 1. Mengalikan ini dengan setiap elemen dan menambahkan semuanya memberi kita jawabannya (setelah menyesuaikan bagian -1).

Sekarang untuk kompleksitasnya, algoritma ini akan menjadi O(n) untuk satu nilai XOR awalan di mana n adalah berapa kali nilai itu muncul. Karena berapa kali setiap nilai awalan XOR muncul akan dijumlahkan dengan panjang larik asli, kompleksitas totalnya linier setelah peta dibuat.

Berikut ini contoh seperti yang diminta:

Katakanlah array memiliki lima elemen, a[0...4]. Jika kami menuliskan jumlah yang Anda coba hitung, akan terlihat seperti ini:

  (a[1] - a[0]) + (a[2] - a[0]) + (a[3] - a[0]) + (a[4] - a[0])
+ (a[2] - a[1]) + (a[3] - a[1]) + (a[4] - a[1])
+ (a[3] - a[2]) + (a[4] - a[2])
+ (a[4] - a[3])

Kita akan berurusan dengan -1 nanti. Jika kita mengelompokkan suku-suku sejenis, akan terlihat seperti ini:

-4 * a[0] + -2 * a[1] + 0 * a[2] + 2 * a[3] + 4 * a[4]

Perhatikan bahwa koefisien suatu suku berhubungan dengan indeks suku tersebut dengan rumus yang disebutkan di atas. Jadi, alih-alih mengulangi setiap pasangan elemen, kami menghitung ekspresi singkat ini. Dalam masalah awal, Anda perlu mengurangi satu untuk setiap pasangan elemen, jadi kita bisa mengurangi jumlah pasangan elemen dari hasilnya.

2
BessieTheCookie 7 Agustus 2019, 02:36