Hướng dẫn giải của Bedao Mini Contest 09 - CNTDIFF
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.
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ả:
Sử dụng một map để duy trì số lượng số trong một đoạn gồm ~k~ bông hoa. Với mỗi ~i~ ~(i \ge k + 1)~ ta sẽ thực hiện hai thao tác trừ đi số ở vị trí ~i - k~ và cộng map lên số ở vị trí ~i~. Với mỗi thao tác update, xét nếu số đó xuất hiện đúng ~1~ lần thì số lượng số khác nhau nhiều nhất tăng lên ~1~, hoặc ngược lại nếu số đó không còn tồn tại trong map.
Độ phức tạp: ~O(NlogN)~
Code mẫu
/*#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,fma")*/ #include <bits/stdc++.h> #define for1(i,a,b) for (int i = a; i <= b; i++) #define for2(i,a,b) for (int i = a; i >= b; i--) #define int long long #define sz(a) (int)a.size() #define pii pair<int,int> #define pb push_back /* __builtin_popcountll(x) : Number of 1-bit __builtin_ctzll(x) : Number of trailing 0 */ const long double PI = 3.1415926535897932384626433832795; const int INF = 1000000000000000000; const int MOD = 1000000007; const int MOD2 = 1000000009; const long double EPS = 1e-6; using namespace std; const int N = 3e5 + 5; int n, k, a[N]; set<int> se; map<int, int> mp; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen("cf.inp", "r", stdin); // freopen("cf.out", "w", stdout); cin >> n >> k; for1(i,1,n) cin >> a[i]; for1(i,1,k) { se.insert(a[i]); mp[a[i]]++; } int res = sz(se); for1(i,k + 1,n) { mp[a[i - k]]--; if (!mp[a[i - k]]) se.erase(a[i - k]); if (!mp[a[i]]) se.insert(a[i]); mp[a[i]]++; res = max(res, sz(se)); } cout << res; }
Bình luận