Editorial for Ba dải ruy-băng

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.

Gợi ý 1 - Tổng số sao phải chia hết cho 3

Hai nhát cắt tạo ra ba đoạn có cùng số sao, nên tổng số sao trên cả dải phải chia hết cho 3. Gọi số sao mỗi đoạn cần có là T/3.

Gợi ý 2 - Biến mỗi cách cắt thành hai vị trí tiền tố

Gọi P_i là số sao trong i ô đầu tiên. Hai nhát cắt sau các ô i và j hợp lệ khi P_i=T/3 và P_j=2T/3. Hãy đếm các cặp này khi quét từ trái sang phải.

Lời giải đầy đủ

Trường hợp không có sao

Nếu tổng số sao bằng 0, mọi cách chọn hai ranh giới cắt đều hợp lệ. Có N-1 ranh giới giữa các ô, nên đáp án là (N-1)(N-2)/2.

Trường hợp có sao

Nếu tổng số sao không chia hết cho 3, không thể chia đều. Ngược lại, đặt T = total/3.

Quét độ dài tiền tố i từ 1 đến N-1. Biến ways lưu số vị trí cắt trước đó có đúng T sao. Khi tiền tố hiện tại có 2T sao, mọi vị trí đã lưu ghép với nó thành một cách cắt hợp lệ. Sau đó, nếu tiền tố hiện tại có T sao thì thêm vị trí này vào ways.

Ta xử lý 2T trước khi thêm T, để hai nhát cắt luôn ở hai vị trí khác nhau.

Nếu N là độ dài chuỗi:

  • Thời gian: O(N).
  • Bộ nhớ: O(1) ngoài chuỗi đầu vào.
Code C++17
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    string s;
    cin >> n >> s;

    int total = 0;
    for (char c : s) total += (c == '1');

    if (total % 3 != 0) {
        cout << 0 << '\n';
        return 0;
    }

    if (total == 0) {
        cout << 1LL * (n - 1) * (n - 2) / 2 << '\n';
        return 0;
    }

    int target = total / 3;
    int prefix = 0;
    long long ways = 0;
    long long answer = 0;

    for (int i = 1; i < n; ++i) {
        prefix += (s[i - 1] == '1');
        if (prefix == 2 * target) answer += ways;
        if (prefix == target) ++ways;
    }

    cout << answer << '\n';
    return 0;
}

Loading...