Hướng dẫn cho Đụng hàng bản lật

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: Prototype

Hướng dẫn giải bài: Đụng hàng bản lật

1. Phân tích bài toán

Bài toán yêu cầu chọn đúng k số có 2 chữ số sao cho tổng bằng S, với điều kiện:

Không chọn các số có 2 chữ số giống nhau (như 11, 22).
Nếu chọn một số thì không được chọn số đảo ngược của nó (chọn 12 thì cấm 21).

Từ 10 đến 99 có 90 số. Ta loại 9 số kép (11, 22...), còn 81 số.
Chia 81 số này thành các nhóm:

Nhóm độc lập: Số có bản đảo ngược không nằm trong khoảng 10-99 (ví dụ 10, 20). Nhóm này chỉ có 1 phần tử.
Nhóm cặp: Các cặp số đảo ngược nhau (ví dụ {12, 21}). Ta chỉ được chọn tối đa 1 số từ mỗi nhóm này.

2. Subtask 1 (50% điểm): k <= 4, S <= 350

Vì k rất nhỏ (chỉ chọn tối đa 4 số), bạn có thể dùng thuật toán quay lui (Backtracking) để thử chọn các số hợp lệ từ tập hợp. Khi đủ k số, kiểm tra tổng xem có bằng S không. Để tối ưu, nếu tổng hiện tại đã vượt quá S thì dừng nhánh đệ quy đó.

3. Subtask 2 (50% điểm): k <= 40, S <= 3500

Bài toán trở thành Quy hoạch động (DP) trên tập các nhóm số đã phân loại.
Gọi dp[i][j][s] là số cách chọn j số từ i nhóm đầu tiên để đạt tổng s.
Với mỗi nhóm:

Không chọn số nào từ nhóm.
Chọn 1 số bất kỳ có trong nhóm (1 phần tử hoặc 1 trong 2 phần tử của cặp).
Công thức chuyển trạng thái: dp[j][s] = (dp[j][s] + dp[j - 1][s - v]) % 1000000007 (với v là giá trị đang xét chọn trong nhóm).

Code C++ (Sub 2 - Full AC)

C++

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;
ll dp[45][3505];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int k, S; cin >> k >> S;
    vector<vector<int>> g;
    bool u[105] = {0};

    for (int i = 10; i <= 99; ++i) {
        if (u[i] || i % 11 == 0) continue;
        int r = (i % 10) * 10 + i / 10;
        if (r < 10 || r == i) {
            g.push_back({i});
            u[i] = 1;
        } else {
            g.push_back({i, r});
            u[i] = u[r] = 1;
        }
    }

    dp[0][0] = 1;
    for (auto &x : g) {
        for (int j = k; j >= 1; --j) {
            for (int s = S; s >= 0; --s) {
                for (int v : x) {
                    if (s >= v) {
                        dp[j][s] = (dp[j][s] + dp[j - 1][s - v]) % 1000000007;
                    }
                }
            }
        }
    }

    cout << dp[k][S];
    return 0;
}

Code Python (Sub 2 - Full AC)

Python

import sys

def solve():
    k, S = map(int, sys.stdin.readline().split())
    g = []
    u = [0] * 105

    for i in range(10, 100):
        if u[i] or i % 11 == 0: continue
        r = (i % 10) * 10 + (i // 10)
        if r < 10 or r == i:
            g.append([i])
            u[i] = 1
        else:
            g.append([i, r])
            u[i] = u[r] = 1

    dp = [[0] * (S + 5) for _ in range(k + 5)]
    dp[0][0] = 1

    for x in g:
        for j in range(k, 0, -1):
            for s in range(S, -1, -1):
                for v in x:
                    if s >= v:
                        dp[j][s] = (dp[j][s] + dp[j - 1][s - v]) % 1000000007

    print(dp[k][S])

solve()

Code Java (Sub 2 - Full AC)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int S = sc.nextInt();

        List<int[]> g = new ArrayList<>();
        boolean[] u = new boolean[105];

        for (int i = 10; i <= 99; i++) {
            if (u[i] || i % 11 == 0) continue;
            int r = (i % 10) * 10 + i / 10;
            if (r < 10 || r == i) {
                g.add(new int[]{i});
                u[i] = true;
            } else {
                g.add(new int[]{i, r});
                u[i] = u[r] = true;
            }
        }

        long[][] dp = new long[k + 5][S + 5];
        dp[0][0] = 1;

        for (int[] x : g) {
            for (int j = k; j >= 1; j--) {
                for (int s = S; s >= 0; s--) {
                    for (int v : x) {
                        if (s >= v) {
                            dp[j][s] = (dp[j][s] + dp[j - 1][s - v]) % 1000000007;
                        }
                    }
                }
            }
        }

        System.out.println(dp[k][S]);
    }
}

Bình luận

Tải bình luận...

Không có bình luận nào.