Hướng dẫn giải của Bedao Mini Contest 18 - BALANCE


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ả: bedao

Subtask 1: ~O(n^2)~.

Ta duyệt hai vòng để chọn ra đoạn con, đồng thời duy trì thông tin về số lượng số chẵn và lẻ để kiểm tra.

Subtask 2: ~O(n \times \sqrt{n} \times \log(n))~.

Có ~N \ge O \ge E^2 + 7 > E^2~. Do đó ~\sqrt{n} > E~, nghĩa là ta chỉ cần quan tâm tối đa ~\sqrt{n}~ số chẵn liên tiếp.

Ta cố định ~i~ và duyệt qua ~\sqrt{n}~ số chẵn sau ~i~. Gọi ~pos_j~ là vị trí của số chẵn thứ ~j~. Ta sẽ đếm số vị trí ~pos_j \le t < pos_{j + 1}~ sao cho đoạn ~[i, t]~ thoả mãn đề bài. Lưu ý trường hợp ~pos_1 > i~ và ~pos_1 = i~.

Ta cần phải có ít nhất ~x = j * j + 7~ số lẻ để đoạn ~[i, t]~ thoả mãn. Do vậy ta có thể chặt nhị phân để tìm phần tử đầu tiên sau ~i~ có đủ số lượng ~x~ số lẻ. Gọi ví trí đó là ~p~. Nếu ~p \ge pos_{j + 1}~, không có ~t~ nào thoả mãn. Ngược lại, tất cả ~t~ trong đoạn ~[max(p, pos_j), pos_{j + 1} - 1]~ sẽ thoả mãn đề bài. Và ta dễ dàng cộng vào đáp án số lượng.

Subtask 3: ~O(n \times \sqrt{n})~.

Nhận thấy chặt nhị phân không thực sự tối ưu. Vì ta biết được ~x~ nên ta có thể dùng công thức ~O(1)~ để tìm được ~p~.

Code mẫu

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define print_op(...) ostream& operator<<(ostream& out, const __VA_ARGS__& u)
#define db(val) "["#val" = "<<(val)<<"] "
#define CONCAT_(x, y) x##y
#define CONCAT(x, y) CONCAT_(x, y)
#ifdef LOCAL   
#   define clog cerr << setw(__db_level * 2) << setfill(' ') << "" << setw(0)
#   define DB() debug_block CONCAT(dbbl, __LINE__)
    int __db_level = 0;
    struct debug_block {
        debug_block() { clog << "{" << endl; ++__db_level; }
        ~debug_block() { --__db_level; clog << "}" << endl; }
    };
#else
#   define clog if (0) cerr
#   define DB(...)
#endif
template<class U, class V> print_op(pair<U, V>) {
    return out << "(" << u.first << ", " << u.second << ")";
}
template<class Con, class = decltype(begin(declval<Con>()))>
typename enable_if<!is_same<Con, string>::value, ostream&>::type
operator<<(ostream& out, const Con& con) { 
    out << "{";
    for (auto beg = con.begin(), it = beg; it != con.end(); ++it)
        out << (it == beg ? "" : ", ") << *it;
    return out << "}";
}
template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) {
    if constexpr(i == tuple_size<T>::value) return out << ")"; 
    else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); 
}
template<class ...U> print_op(tuple<U...>) {
    return print_tuple_utils<0, tuple<U...>>(out, u);
}

const int N = 3e5 + 5;

int n, a[N];
vector<int> even;
int odd[N];

void solve() {
    even.push_back(0);
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i];
        if (a[i] % 2 == 0) {
            even.push_back(i);
        }
        odd[i] = odd[i - 1] + (a[i] & 1);
    }
    even.push_back(n + 1);
    ll res = 0;
    for (int i = 1, start = 0; i <= n; ++ i) {
        while (start + 1 < (int)even.size() && even[start] < i) {
            ++ start;
        }
        if (even[start] > i) {
            res += max(0, even[start] - i - 6);
        }
        int j = 0, k = start;
        for (; j * j < n && k + 1 < (int)even.size(); ++ j, ++ k) {
            int need = max(0, (j + 1) * (j + 1) + 7 - (odd[even[k]] - odd[i - 1]));
            int nxt = even[k] + need;
            if (nxt >= even[k + 1]) continue;
            res += even[k + 1] - nxt;            
        }   
        // sum += j;
    }
    // cout << sum << endl;
    cout << res << endl;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
#ifdef LOCAL
    freopen("main.out", "w", stdout);
#endif
    solve();
    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


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