Hướng dẫn giải của Tàu vũ trụ

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Lời giải: Tàu vũ trụ

Nhận xét quan trọng

Chuỗi nút nhấn hợp lệ của Bessie có cấu trúc đặc biệt: khi nhấn nút $x$ , tất cả các nút nhỏ hơn $x$ được "reset" và có thể dùng lại, nhưng nút $x$ trở nên không hợp lệ cho đến khi có nút lớn hơn được nhấn. Điều này có nghĩa là tập hợp các nút đang "hoạt động" luôn có dạng một tập hậu tố (suffix) liên tục không có lỗ hổng, và đây chính là cấu trúc của số Zeckendorf trong hệ đánh số đặc biệt.

Hướng tiếp cận

Chúng ta sử dụng quy hoạch động (DP) với node ảo (virtual node) cho mỗi truy vấn.

Định nghĩa $d p [a] [b]$ là số chuỗi hành trình và nhấn nút hợp lệ sử dụng các nút có số không vượt quá mức hiện tại, bắt đầu tại node $a$ và kết thúc tại node $b$ .

$a, b \in {0, 1, \dots, N - 1}$ : các phòng thực
$a = N + j$ : node ảo $α_{j}$ — đại diện cho trạng thái "bắt đầu ở phòng $s_{j}$ nhấn nút $b_{s}^{(j)}$ "
$b = N + j$ : node ảo $β_{j}$ — đại diện cho trạng thái "kết thúc ở phòng $t_{j}$ nhấn nút $b_{t}^{(j)}$ "

Câu trả lời cho truy vấn $j$ là $d p [N + j] [N + j]$ sau khi xử lý tất cả $K$ mức nút.

Thuật toán

Với mỗi mức nút $h$ (từ $0$ đến $K - 1$ , tương ứng nút $h + 1$ ):

Sao chép $d p$ từ mức trước (chuỗi không dùng nút $h + 1$ vẫn hợp lệ).
Với mỗi phòng "trung tâm" $c$ (nơi nhấn nút $h + 1$ ):
- Tính mảng left[a]: số chuỗi bắt đầu tại a kết thúc ngay trước khi vào c:
  - $left [c] = 1$ (chuỗi trái rỗng, Bessie bắt đầu ở $c$ )
  - $left [N + j] + = 1$ nếu $h = b_{s}^{(j)} - 1$ và $c = s_{j}$ (node alpha kích hoạt)
  - $left [a] + = \sum_{b^{'} : adj [b^{'}] [c]} d p [a] [b^{'}]$ (chuỗi DP đi vào $c$ )
- Tính mảng right[b]: số chuỗi bắt đầu ngay sau c kết thúc tại b:
  - $right [c] = 1$ (chuỗi phải rỗng, Bessie dừng ở $c$ )
  - $right [N + j] + = 1$ nếu $h = b_{t}^{(j)} - 1$ và $c = t_{j}$ (node beta kích hoạt)
  - $right [b] + = \sum_{a^{'} : adj [c] [a^{'}]} d p [a^{'}] [b]$ (chuỗi DP từ $c$ )
- Cộng vào DP mới: $d p^{'} [a] [b] + = left [a] \times right [b]$

Độ phức tạp

Số trạng thái DP: $O ((N + Q)^{2})$
Với mỗi mức nút và mỗi phòng trung tâm: tính left và right mỗi cái mất $O (N \cdot (N + Q))$ , cộng vào DP mất $O ((N + Q)^{2})$
Tổng: $O (N \cdot (N + Q)^{2} \cdot K)$

Với $N, K, Q \leq 60$ : $(N + Q)^{2} \cdot K \cdot N = 120^{2} \cdot 60 \cdot 60 \approx 5.2 \times 10^{7}$ , hoàn toàn trong giới hạn thời gian.

Bình luận

Không có bình luận tại thời điểm này.