Bài tập Code bitmask, training Dumv 20/03/2025 0 Comments

AND and OR operations

NA là 1 người thích học về các phép toán bit. Hiểu được tâm lí đó , thầy Vinh đã giao cho Na 1 bài tập rất thú vị như sau. Cho 1 mảng gồm n phần tử a₀ , a₁ , a₂ , ... , a_n-1 . NA được thực hiện tùy số ( có thể không thực hiện) phép biến đổi như sau : Chọn 2 chỉ số i , j phân biệt trong mảng thỏa mãn (0 ≤ i,j ≤ n-1), ta giả sử trước phép biến đổi thì x = a_i , y = a_j,thì sau phép biến đổi ta gán a_i = x AND y và a_j = x OR y , với AND và OR là 2 phép toán bit. Sau khi hoàn thành xong, NA nhận thấy tổng bình phương của các phần tử thay đổi tùy vào số lần thực hiện. Nhiệm vụ của bạn là tìm tổng bình phương lớn nhất có thể đạt được sau khi thực hiện tùy ý số phép biến đổi như trên.

Ví dụ:

Với n = 3 và a = [1,3,5] thì AND_and_OR(n,a) = 51.
Giải thích : Ta chọn phần tử 1 và 2 để thực hiện phép biến đổi , ta có x = a[1] = 3 , y = a[2] = 5 thì lúc này a[1] = x AND y = 1 và a[2] = x OR y = 7. Lúc này ta có mảng a = [1,1,7] và đây là mảng có giá trị tổng bình phương mỗi phần tử lớn nhất : 1² + 1² + 7² = 51.