Hướng dẫn cho Giáo Sư Ba Lô

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: Giáo Sư Ba Lô

Phân tích

Với mỗi số \( N \):

Chuyển \( N \) sang chuỗi nhị phân \( S \)
Xét mọi đoạn con của \( S \)

Một đoạn được gọi là "cân bằng" nếu:

Độ dài chẵn
Chia đôi ra:
Số lượng '1' bên trái = số lượng '1' bên phải

Nhận xét quan trọng

Giả sử đoạn con có dạng:

\[ S[l..r], \quad \text{độ dài } = 2k \]

Gọi:

\( left = S[l..l+k-1] \)
\( right = S[l+k..r] \)

Điều kiện:

\[ \text{count\_1}(left) = \text{count\_1}(right) \]

Ý tưởng chính

Dùng prefix sum:

\[ pref[i] = \text{số lượng '1' từ } 1 \rightarrow i \]

Khi đó:

\[ \text{count\_1}(l \rightarrow r) = pref[r] - pref[l-1] \]

Sub 1 (50%): \( T \le 1000 \)

Cách làm brute force

Sinh tất cả đoạn con
Chỉ xét đoạn có độ dài chẵn
Kiểm tra điều kiện

Độ phức tạp:

\[ O(n^3) \]

Với \( n \le 20 \) (vì \( N \le 10^6 \)) nên vẫn chạy được

Code C++ (Sub 1)

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        string s = "";
        while (n > 0) {
            s += char((n % 2) + '0');
            n /= 2;
        }
        reverse(s.begin(), s.end());

        int len = s.size();
        bool ok = false;

        for (int l = 0; l < len; l++) {
            for (int r = l; r < len; r++) {
                int length = r - l + 1;
                if (length % 2 != 0) continue;

                int mid = (l + r) / 2;

                int c1 = 0, c2 = 0;
                for (int i = l; i <= mid; i++)
                    if (s[i] == '1') c1++;

                for (int i = mid + 1; i <= r; i++)
                    if (s[i] == '1') c2++;

                if (c1 == c2) ok = true;
            }
        }

        if (ok) cout << "YES\n";
        else cout << "NO\n";
    }
}

Sub 2 (100%): \( T \le 10^6 \)

Tối ưu

Nhận xét:

Độ dài chuỗi nhị phân tối đa ~ 20
Không thể \( O(n^3 \cdot T) \)

=> Tối ưu bằng prefix sum

Cách làm

Tạo prefix sum
Duyệt đoạn chẵn
Tính nhanh số lượng '1'

Độ phức tạp mỗi test:

\[ O(n^2) \]

Tổng:

\[ O(T \cdot n^2) \approx 10^6 \cdot 400 \Rightarrow OK \]

Code C++ (Full)

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        string s = "";
        while (n > 0) {
            s += char((n % 2) + '0');
            n /= 2;
        }
        reverse(s.begin(), s.end());

        int len = s.size();

        vector<int> pref(len + 1, 0);
        for (int i = 0; i < len; i++) {
            pref[i + 1] = pref[i] + (s[i] == '1');
        }

        bool ok = false;

        for (int l = 0; l < len; l++) {
            for (int r = l; r < len; r++) {
                int length = r - l + 1;
                if (length % 2 != 0) continue;

                int mid = (l + r) / 2;

                int c1 = pref[mid + 1] - pref[l];
                int c2 = pref[r + 1] - pref[mid + 1];

                if (c1 == c2) {
                    ok = true;
                    break;
                }
            }
            if (ok) break;
        }

        if (ok) cout << "YES\n";
        else cout << "NO\n";
    }
}

Code Python

Python

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    s = bin(n)[2:]

    len_s = len(s)
    pref = [0] * (len_s + 1)

    for i in range(len_s):
        pref[i+1] = pref[i] + (s[i] == '1')

    ok = False

    for l in range(len_s):
        for r in range(l, len_s):
            length = r - l + 1
            if length % 2 != 0:
                continue

            mid = (l + r) // 2

            c1 = pref[mid+1] - pref[l]
            c2 = pref[r+1] - pref[mid+1]

            if c1 == c2:
                ok = True
                break
        if ok:
            break

    print("YES" if ok else "NO")

Code Java

Java

import java.util.*;

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

        while (t-- > 0) {
            int n = sc.nextInt();
            String s = Integer.toBinaryString(n);

            int len = s.length();
            int[] pref = new int[len + 1];

            for (int i = 0; i < len; i++) {
                pref[i + 1] = pref[i] + (s.charAt(i) == '1' ? 1 : 0);
            }

            boolean ok = false;

            for (int l = 0; l < len; l++) {
                for (int r = l; r < len; r++) {
                    int length = r - l + 1;
                    if (length % 2 != 0) continue;

                    int mid = (l + r) / 2;

                    int c1 = pref[mid + 1] - pref[l];
                    int c2 = pref[r + 1] - pref[mid + 1];

                    if (c1 == c2) {
                        ok = true;
                        break;
                    }
                }
                if (ok) break;
            }

            System.out.println(ok ? "YES" : "NO");
        }
    }
}

Bình luận (1)

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