Hướng dẫn giải của Bedao Mini Contest 14 - OPERATION
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ả:
Gọi ~mi_a~ là giá trị nhỏ nhất của mảng ~a~, ~ma_a~ là giá trị lớn nhất của mảng ~a~, ~x~ là giá trị cần tạo.
Nhận xét: Nếu ~mi_a \le x \le ma_a~ thì ta sẽ tạo được số ~x~ từ mảng ~a~.
Chứng minh: Sau khi thực hiện ~n - 1~ thao tác, ta cần đạt được ~mi_a = ma_a = x~. Ta chứng minh được sau mỗi thao tác, ~mi_a~ sẽ không giảm và ~ma_a~ sẽ không tăng, ta sẽ chia ra ~2~ trường hợp sau:
~x < mi_a~ hoặc ~ma_a < x~: Vì ~mi_a~ sẽ không giảm và ~ma_a~ sẽ không tăng sau mỗi thao tác nên điều kiện ~mi_a = ma_a = x~ sẽ không thể đạt được.
~mi_a \le x \le ma_a~: Ta có thể thực hiện tạo số ~x~ bằng cách sau: Chọn ~2~ số tương ứng với ~mi_a~ và ~ma_a~, xóa ~2~ số đi, thêm ~x~ vào. Sau đó, ở ~n - 2~ thao tác còn lại, chọn số ~x~ và một số bất kỳ trong mảng, xóa ~2~ số này và tiếp tục thêm số ~x~ vào. Dễ thấy, số còn lại trong mảng luôn là ~x~.
Độ phức tạp: ~O(n + q)~.
Code mẫu
//TrungNotChung #include <bits/stdc++.h> #define pii pair<int , int> #define fi first #define se second #define BIT(x,i) (1&((x)>>(i))) #define MASK(x) (1LL<<(x)) #define CNT(x) __builtin_popcountll(x) #define task "tnc" using namespace std; const int N = (int)1e5+228; const int INF = (int)1e9+7; int n, q, a[N]; void solve() { cin >> n >> q; for(int i=1; i<=n; ++i) cin >> a[i]; int mi = INF, ma = -INF; for(int i=1; i<=n; ++i) { mi = min(mi, a[i]); ma = max(ma, a[i]); } while(q--) { int x; cin >> x; if(x < mi || x > ma) cout << "No\n"; else cout << "Yes\n"; } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #ifndef ONLINE_JUDGE freopen(task".inp","r",stdin); freopen(task".out","w",stdout); #endif // ONLINE_JUDGE solve(); return 0; }
Bình luận