Editorial for Bedao Mini Contest 15 - 2SEG


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

  • Subtask 1: Duyệt trâu

  • Subtask 2: Vì ~a[i] \leq 20~ nên kết quả của ta sẽ có tối đa 20 phần tử, vậy nên ta sẽ duyệt trâu đoạn 1, lưu các phần tử của đoạn 1 dưới dạng bitmask và tìm đoạn 2 là một bitmask có nhiêu bit 1 nhất sao cho nó là mask con của phần bù của đoạn 1. Phần còn lại xin phép nhường bạn đọc

  • Subtask 3: Đầu tiên, cần tính mảng ~dp[l][r]~ là dãy con liên tiếp có các phần tử phân biệt dài nhất nếu xét các phần từ trong đoạn từ ~l~ đến ~r~. Ta có thể đơn giản dùng 2 con trỏ đến tính mảng này

Tiếp theo, cố định độ dài của dãy con liên tiếp thứ nhất ~[l, r]~ (phần tử phân biệt), vậy ta cần tìm đoạn ~[u, v]~ dài nhất sử dụng các phần tử khác với các phần tử trong đoạn thứ nhất và ~r < u \leq v~

Nhận xét: khi ta giảm từ đoạn ~[l, r]~ sang ~[l, r - 1]~, một số phần tử mới (cụ thể là bằng chính ~a[r]~) sẽ có thể được sử dụng cho đoạn thứ 2. Vì vậy, ta sẽ xử lí bằng cách cố định ~l~ và giảm dần ~r~ từ ~n~ về ~l~, khi giảm ~r~ ta sẽ duy trì tập các phân tử có thể sử dụng cho đoạn 2. Tập S sẽ gồm các vị trí ~S = \{i_1, i_2, i_3, ..., i_k\}~ và ta cần duy trì ~max(dp[u][v])~ sao cho đoạn ~[u, v]~ chỉ chứa các giá trị có thể sử dụng và đó cũng chính là độ dài lớn nhất của đoạn 2.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.