Hướng dẫn giải của Bedao Mini Contest 18 - BALANCE
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ả:
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