Bỏ qua đến nội dung

Hướng giải: MATRIXA

MATRIXA

Mã bài: free034 Nhóm: Uncategorized Điểm: 100 điểm
Giới hạn
1,0 s, 256 MB
Tỉ lệ AC
25,0%
Người giải
3
Chỉ đọc hướng giải khi bế tắc và đừng sao chép mã trong đó. Hãy tôn trọng người ra đề và người viết hướng giải: nộp lời giải chính thức khi chưa tự giải được bài có thể khiến bạn bị khóa tài khoản.

Nguồn: Free Contest

Subtask 1

Ta duyệt từng bộ cặp điểm (x_1, y_1), (x_2, y_2) là góc trái trên và phải dưới của hình chữ nhật đang xét. Sau đó duyệt tính tổng từng ô trên viền hình chữ nhật đang xét và cập nhật kết quả.

Độ phức tạp: O(max(m, n)^5)

Subtask 2

Vẫn tư tưởng như subtask 1 nhưng ta lập thêm các mảng đếm (prefix sum). Cụ thể:

  • Row_{i,j} = A_{i,1} + A_{i,2} + ... + A_{i,j}
  • Column_{i,j} = A_{1,j} + A_{2,j} + ... + A_{i,j}

Khi đó từng bộ cặp điểm (x_1, y_1) và (x_2, y_2) là góc trái trên và phải dưới của hình chữ nhật đang xét thì tổng của viền hình chữ nhật được xác định theo công thức :

S = Row_{x_1,y_2}-Row_{x_1,y_1-1}+Row_{x_2,y_2}-Row_{x_2,y_1-1}+Column_{x_2-1,y_1}-Column_{x_1,y_1}+Column_{x_2-1,y_2}-Column_{x_1,y_2}

Độ phức tạp: O(m^2.n^2)

Subtask 3

Ta có thể biến đổi công thức tính S ở trên như sau: S = (Row_{x_1,y_2}+Row_{x_2,y_2}-Column_{x_1,y_2}+Column_{x_2-1,y_2})-(Column_{x_1,y_1}+Row_{x_1,y_1-1}+Row_{x_2,y_1-1}-Column_{x_2-1,y_1})

Như vậy nếu ta cố định x_1, x_2 thì với mỗi y_2 ta cần tìm y_1 mà 0 \le y_1 < y_2 sao cho S lớn nhất. Ta dễ dàng có thể làm được trong O(n) với mỗi bộ x_1, x_2 (có thể sử dụng prefix max).

Độ phức tạp: O(m^2.n)

Bình luận