Hướng dẫn cho Cờ Vua

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: shiba

Subtask 1

Quay lui, thử mọi tổ hợp xếp quân vua.

Độ phức tạp: \(O(2^{N^2})\).

Subtask 2,3

Sử dụng quy hoạch động và mặt nạ bit AKA bitmask. Thay vì quy hoạch động 2 chiều theo bàn cờ, hay gì đó tương tự, thì ta sẽ xem xét các hàng xếp quân vua theo dãy nhị phân, với 1 là xếp vua và 0 là không. Ví dụ:

000010100

Thì ta có thể đặt một dãy bit khác sao cho không con vua nào tấn công nhau, ví dụ:

000010100
101000001

Đầu tiên ta quay lui và nhét tất cả các dãy bit thỏa mãn (không con vua nào trên dãy đó ăn nhau) vào một vector hay mảng, gọi mask số lượng dãy bit đó.

Xét dp[i][j][k] với \(i\) là hàng thứ \(i\), \(j\) là dãy bit thứ \(j\) sẽ được sử dụng, và \(k\) là tổng số quân vua được sử dụng. Ta có công thức truy hồi như sau:

for(int i=2;i<=n;++i)
for(int j=0;j<m;++j)
for(p=0;p<=k;++p) {
if(p<cnt[j]) continue;
pp=p-cnt[j];
for(u=0;u<m;++u)
if(check(gay[j],gay[u])) dp[i][j][p]+=dp[i-1][u][pp];
}

Ý tưởng nói chung là với dãy bit thứ \(j\), ta sẽ xem xem có bao nhiêu cách đạt được trạng thái này với \(k\) con vua. Số cách đạt được trạng thái dp[i][j][k] chính là bằng tổng số cách đạt được các trạng thái dp[i-1][u][k - số bit 1 của dãy thứ j] với \(u\) là dãy bit thứ \(u\) của hàng \(i-1\) mà không xung đột với dãy thứ \(j\) của hàng \(i\).

Kết quả sẽ là tổng dp[N][i][K] với \(i \in [1..mask]\).

Độ phức tạp là \(O(N \times M^2 \times K)\) với \(N\) là số hàng của bàn cờ, \(M\) là số bitmask, \(K\) là số lượng quân vua.


Bình luận


  • -2
    naniore    9:08 p.m. 9 Tháng 5, 2023 ← đã chỉnh sửa

    sol xamlon quá + gay vl


    • 0
      PY2GCaoVanAnhKiet    8:45 a.m. 5 Tháng 7, 2023

      bạn có nghĩ ra ko mà xamlon =)


      • 1
        naniore    6:28 a.m. 7 Tháng 7, 2023

        Bạn thấy format code khó chịu không


    • 0
      shiba    11:09 a.m. 10 Tháng 5, 2023

      thế bạn muốn sol phải như thế nào mới ko xamlon :Đ


      • 0
        naniore    12:14 p.m. 10 Tháng 5, 2023

        mình chỉ hơi tức việc format code thôi nên bạn thông cảm (mà tên biến sú quá)

      3 bình luận nữa