Editorial for Bedao Mini Contest 18 - BINSEQ
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1: ~O(2^n \times n)~.
Ta duyệt quay lui để xem loại phần tử nào và giữ lại phần tử nào. Sau đó kiểm tra điều kiện trong ~O(n)~.
Subtask 2: ~O(n)~.
Xét xâu ~s~ có hai phần tử đầu là ab
. Ta luôn suy ra được phần tử thứ ~i~ ~(i \ge 2)~ của ~s~ là ~1 - s[i - 2]~. Sau khi biết được toàn bộ xâu ~s~, ta có thể tham lam để chọn ra tiền tố lớn nhất của xâu ~s~ là xâu con của xâu nhị phân ban đầu. Vì chỉ có ~4~ khả năng của ab
nên ta sẽ làm tham lam ~4~ lần.
Code mẫu
#include <bits/stdc++.h> using namespace std; #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); } string res; int ans = 0; void solve(string& a, vector<char> b) { while (b.size() < a.size()) { assert(b.size() >= 2); b.push_back('1' + '0' - b[(int)b.size() - 2]); } int run = 0; for (int i = 0; i < (int)a.size(); ++ i) { if (run < (int)b.size() && a[i] == b[run]) { ++ run; } } if (ans < run) { ans = run; res = ""; for (int i = 0; i < run; ++ i) { res += b[i]; } } } int main() { cin.tie(0)->sync_with_stdio(0); string a; cin >> a; solve(a, {'0', '0'}); solve(a, {'0', '1'}); solve(a, {'1', '0'}); solve(a, {'1', '1'}); cout << res; }
Comments