Trung tâm cá nhân
cuốn sách gpt4 ai đã làm

thuật toán - UVA-1394 : Và có một thuật toán

In lại Tác giả: Taklimakan Thời gian cập nhật: 2023-11-03 04:19:22 29 4
mua khóa gpt4 Nike

Liên kết đến câu hỏi làUVA - 1394 : Và Có Một Người .
Thuật toán đơn giản là quét toàn bộ mảng và đánh dấu phần tử thứ k trong mỗi lần lặp và dừng ở cuối: việc này mất thời gian O(n^2).
Tôi đã tìm kiếm một thuật toán thay thế và tìm thấy blog tiếng trungđiều này cho tôi biếtCây phân đoạnSử dụng phương pháp lan truyền lười biếng làm giải pháp thời gian O(N lgN).
Sau khi xem xét cây phân đoạn, tôi đã cố gắng hình thành một thuật toán trong thời gian O(N lgN), nhưng không có kết quả.

我的问题是:
1. Có thể sử dụng cây phân đoạn để đạt được thời gian chạy cần thiết không?
2. Nếu có, vui lòng dạy tôi cách sử dụng chúng.
3. Cây phân đoạn và cây phân đoạn "zkw" có giống nhau không? - Anh ấy đã đề cập đến zkw Duan Shu trong blog của mình.
gia hạn:Câu hỏi trên là một ví dụ về bài toán Josephus.

câu trả lời hay nhất

  1. Vâng, bạn có thể.

  2. Bạn có thể xem mô tả cấu trúc dữ liệu bên dưới, ở đây tôi chỉ đưa ra gợi ý về cách sử dụng nó trong vấn đề đã cho. Dân số mà chúng tôi đại diện rõ ràng là một vòng tròn đá. chúng ta bắt đầu từ tất cả N đá bắt đầucòn sống, và tại mỗi bướcgiếtNhững viên đá thích hợp trong cây của chúng ta. Chỉ cần biết chúng ta hiện đang sử dụng phần tử nào (tôi nghĩ gọi nó làmthích hợp hơn). Thuật toán cấp cao (tôi để lại chi tiết cho bạn) như sau (P là cấu trúc dữ liệu của chúng tôi):

    Trong khi P.size > 1:
      P.toggle(m) // loại bỏ viên đá thứ m
      m = P.kth(viên đá tiếp theo bị giết)

    P.size trong đoạn mã trên chỉ đơn giản là số lượng tất cả các viên đá còn lại. Trong mô tả sau đây, nó tương ứng với cây [1].

    Để ý:Ký hiệu dùng trong cấu trúc dữ liệukvới đầu vào câu hỏi được thể hiện trongKhoảng cách nhảybiểu tượng là khác nhau. p>

  3. hầu hết. Tôi chưa từng thấy cái tên này trước đây nhưng mã này trông giống như những gì tôi đã thấy mọi người nóicây dân sốNhư nhau.

    Cây dân số là một cách đơn giản để sử dụng cây phân đoạn. bạn có N phần tử, mỗi phần tử có hai trạng thái có thể có: 1 nghĩa là còn sống, 0 nghĩa là đã chết. Cây hỗ trợ hai thao tác:

    • Số công tắc là Tôi Trạng thái của phần tử.
    • Quay lại trang kChỉ mục của phần tử sự kiện (theo kích thước chỉ mục của nó).

    Để minh họa thao tác thứ hai, giả sử rằng tập hợp các phần tử sự sống là {1, 2, 4, 7}. nếu như N = 8, tương ứng với mảng trạng thái 01101001 (phần tử 0 đã chết, phần tử 1 còn sống, phần tử 3 còn sống, v.v.).

    Vì vậy, làm thế nào để đạt được nó? Như thường lệ, lá của cây tương ứng vớimảng. Tức là nếu phần tử thứ i tồn tại thì giá trị của lá thứ i là 1, ngược lại là 0. Mỗi nút bên trong ghi nhớ tổng giá trị của các nút con của nó.

    Để chuyển đổi trạng thái của một phần tử, chúng ta chuyển đổi giá trị của lá tương ứng và sau đó sửa đường dẫn từ lá đó đến gốc:

    const int size = 1 << 18; // 2^17 phần tử, phần còn lại là các nút bên trong
    int tree[size]; // số phần tử sống trong cây con của một nút

    chuyển đổi void(int i) {
      tree[i + size / 2] ^= 1; // chuyển đổi lá
      cho (i /= 2; i > 0; i /= 2)
        cây[i] = cây[2 * i] + cây[2 * i + 1];
    }

    Để ý:Một cách phổ biến để gắn nhãn các nút là đểgốcbằng 1 thì theo cách đệ quy, nút n Các nút con của là 2n Và 2n+1.

    Để tìm thứ k các yếu tố của cuộc sống, chúng ta có thể nghĩ về nó một cách đệ quy: chúng ta hiện đang ở nút n, và đang tìm kiếm thứ k Phần tử sự kiện (cây con của nút là cây có gốc tại nút đó). nếu nhưnđứa con trái 2n有kmột hoặc nhiều yếu tố sống, hãyn = 2n . Nếu không, rõ ràng chúng ta sẽ tìm thấy con chính xác, đó là tập hợp n = 2n+1. Trong trường hợp này, chúng ta không còn tìm kiếm cây con nữa k những yếu tố còn sót lại. Vì chúng ta đã bỏ qua tất cả các phần tử sống của phần tử con bên trái nên chúng ta bắt đầu với k Trừ số này từ . Để đơn giản, chúng ta đang xem xét các yếu tố cuộc sống dựa trên 1 ở đây.

    Ý tưởng cơ bản ở đây có lẽ là đệ quy, nhưng mô tả ngụ ý rằng việc thực hiện lặp đi lặp lại cũng phải đơn giản:

    int kth(int k) {
      ++k; // vì phương thức này xem xét các phần tử dựa trên 1
      int current_node = 1; // bắt đầu từ gốc
      trong khi (current_node < size / 2) {
        if (cây[2 * current_node] >= k) 
          current_node = 2 * current_node; // đi xuống con bên trái;
        khác {
          k -= cây[2 * current_node] // sửa k
          current_node = 2 * current_node + 1; // chuyển xuống con bên phải
        }
      }
    }

    Hai chức năng này làmCây phân đoạntrở nêncây dân số.

Đây là câu hỏi về cấu trúc dữ liệu nên các ý tưởng được mô tả đều sử dụng cấu trúc dữ liệu. Tuy nhiên, tôi muốn đề cập rằng câu hỏi này được gọi là Câu hỏi của Josephus, và có một giải pháp thay thế, vì vậy bạn có thể muốn tìm kiếm giải pháp đó.

Về thuật toán - UUV-1394: And There Was One Algorithm, chúng tôi tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/14462401/

29 4 0
Bài viết khuyến nghị: android - Thời gian chạy thuật toán duyệt cây theo thứ tự của Morris
Bài viết khuyến nghị: Có thể buộc trình biên dịch Java 8 tạo các tệp lớp có thể tái tạo không?
Bài viết khuyến nghị: Bỏ chọn nút khỏi JTree khi nhấp vào bất kỳ vị trí nào bên ngoài cây
Bài viết khuyến nghị: thuật toán - Câu lệnh vòng lặp này mất bao lâu để chạy?
Taklimakan
Hồ sơ

Tôi là một lập trình viên xuất sắc, rất giỏi!

Nhận phiếu giảm giá taxi Didi miễn phí
Phiếu giảm giá taxi Didi
Các bài viết phổ biến trên toàn bộ trang web
Chứng chỉ ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com
Xem sitemap của VNExpress