Giúp giải thuật toán

#1

image
image771×595 52.9 KB

Em đọc bài này trên Codelearn Link bài này đây ạ (codelearn.io)
Em không thấy hướng nào giải bài này theo phương pháp chia để trị cả (phương pháp cũng z =))) ), nhìn 2^50 hết hồn ạ @@.
Ai giúp em tìm hướng giải bài này với ạ, Em cảm ơn nhiều.

#2

Tìm các điểm đối xứng thử xem :slight_smile:

3 Likes
#3

để ý tổng tất cả các số 1 của số n khi được phân tích ra hết bằng chính n :V

vậy chỉ cần tìm vị trí L, R thuộc về số X, Y nào tính tổng số 1 với độ dài ko hoàn chỉnh của 2 số này, rồi tính tổng tất cả các số từ X+1 tới Y-1 là ra :V

edit: chắc ko đơn giản vậy :V

Cho dãy n = dãy n/2 thứ 1, n%2, dãy n/2 thứ 2

Giả sử tìm tổng trên đoạn [1, r] của dãy n, thì ta chỉ cần tìm r thuộc dãy n/2 nào, thứ 1 hoặc thứ 2.

  • Nếu r thuộc dãy n/2 thứ 1, bài toán trở về tìm tổng trên đoạn [1, r] của dãy n/2.
  • Nếu r = chính giữa 2 dãy thì trả về tổng trên đoạn [1, r] của dãy n/2 cộng với n%2.
  • Nếu r thuộc dãy n/2 thứ 2, bài toán trở về tìm tổng trên đoạn [1, x] của dãy n/2, với x = r - (độ dài của dãy n/2 + 1). Kết quả là tổng đó cộng với n/2 + n%2.

Giả sử tìm tổng trên đoạn [l, max] thì cũng tương tự: tìm l thuộc dãy n/2 thứ 1 hay thứ 2, chỉnh số lại tí thôi :V

  • Nếu l thuộc dãy n/2 thứ 2 thì trả về tổng [x, max] với x = l - (độ dài của dãy n/2 + 1).
  • Nếu l = chính giữa thì rả về tổng [x, max] + n%2 với x = l - (độ dài của dãy n/2 + 1).
  • Nếu l thuộc dãy n/2 thứ 1 thì trả về tổng [l, max] của dãy n/2. Kết quả là tổng đó cộng với n/2 + n%2.

Trường hợp [l, r] thì chia làm 2 tổng: tổng [l, max] của dãy n/2 và tổng [1, x] của dãy n/2 với x = r - (độ dài của dãy n/2 + 1). Cộng với n%2 nữa là ra :V (hoặc 1 tổng nếu l, r nằm cùng 1 bên của dãy n/2)

Cần phải tìm hàm tìm độ dài của dãy n nữa. Hàm này có thể là O(\log n)

Đệ quy [l, r] \log n lần, vậy đpt chắc là O(\log^2 n) lẹ :triumph:

4 Likes
#4

Em cảm ơn bác nhiều nha hehe em hiểu rồi

#5

em không rành phương pháp này lắm

#6

Độ dài là 2^số bit của n - 1. Bit thứ zero sẽ xuất hiện 1 lần, bit thứ nhất xuất hiện 2 lần, …

4 Likes
#7

Mình không nghĩ ra được chuyện bù trừ :smiley:

Để tính được số bit 1 từ 1 đến k ta dựa vào tất cả chữ số nhị phân của k. Các dãy [m*2^p+1…(m+1)*2^p-1] đều có n & (1 << p - 1) bit 1 do là cây con.

VD: từ 1 đến 5 = 4 + 1 thì lấy 2 bit cuối của n, rồi bit thứ 2 (do ở giữa), còn bit cuối.

Đặc biệt, nếu k có dạng 2^m - 1 (tức là k & (k+1) = 0) thì lấy k bit cuối của n.

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?