Editorial for Bedao Mini Contest 12 - BINARY
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:
Để thoả mãn cả ~3~ điều kiện thì ta có một cách dựng ~2~ số ~a~, ~b~ đơn giản như sau:
Xét một đoạn các bit ~1~ liên tiếp trong ~c~, gọi đoạn đó là đoạn ~[l, r]~. Vì ~2^{r+1} - 2^l = 2^l + 2^{l+1} + ... + 2^r~, nên ta chỉ cần thay đổi bit ~r + 1~ của ~a~ và bit ~l~ của ~b~ thành ~1~ ta sẽ thoả mãn điều kiện của đề bài.
Độ phức tạp: ~O(n)~
Code mẫu
#include <bits/stdc++.h> using namespace std; #define int long long #define fo(i, a, b) for(int i = a; i <= b; i++) #define _fo(i, a, b) for(int i = a; i >= b; i--) #define foa(i, a) for (auto &i : a) #define sz(a) ((int) a.size()) #define all(a) begin(a), end(a) #define fi first #define se second #define pb(x) push_back(x) #define mk(x, y) make_pair(x, y) typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vl; typedef pair<int, int> pii; typedef vector<int> vi; const int LOG = 22; const int MAX = 2e5+5; const int MOD = 1e9+7; const int SQRT = 400; const ll INF = 2e9; const ll lon = 1e18; int n; string c, a, b; vector<pii> segment; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> c; c = '0'+c; fo(i, 1, n-1) { if(c[i] == '0') continue; if(c[i-1] == '0') segment.pb(mk(i, i-1)); segment.back().se++; } a.assign(n, '0'); b.assign(n, '0'); foa(elem, segment) { a[elem.fi-1] = '1'; b[elem.se] = '1'; } cout << a << "\n" << b; }
Comments