Cho mảng nhị phân n phần tử, ban đầu toàn 0. Cung cấp M lệnh. Mỗi lệnh chứa chỉ số bắt đầu và kết thúc. Lệnh(a,b) áp dụng từ vị trí a đến b. Lệnh đảo giá trị (toggle): 0->1, 1->0. Vấn đề đơn giản, xem thuật toán.
Thuật toán
toggleCommand(arr, a, b)
BAT DAU
Với mỗi phần tử e từ chỉ số a đến b:
Đảo e và gán lại vào arr tại vị trí đó.
KẾT THÚC
KET THUC
Ví dụ
#include <iostream>
using namespace std;
void toggleCommand(int arr[], int a, int b) {
for (int i = a; i <= b; i++) {
arr[i] ^= 1; // đảo bit trong khoảng a đến b
}
}
void display(int arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int n = sizeof(arr) / sizeof(arr[0]);
display(arr, n);
toggleCommand(arr, 3, 6);
toggleCommand(arr, 8, 10);
toggleCommand(arr, 2, 7);
display(arr, n);
}
Kết quả
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 0