Hướng dẫn cho Dãy số (Contest Practice VNOI 2021 Round 6)
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Subtask 2: \(n \le 2000\)
Ta duyệt qua \(O(n^2)\) đoạn con. Để đếm số lần xuất hiện của một đoạn con, ta sử dụng hash. Lúc này, một đoạn liên tiếp đã trở thành một số. Hai đoạn con (có khả năng cao) sẽ giống nhau nếu giá trị hash của chúng bằng nhau. Để tăng tính chính xác có thể dùng hash với nhiều modulo.
Độ phức tạp \(O(n^2log_2(n))\)
Subtask 3: \(a_i \in \{0,1\}\)
- TH 1: có một giá trị xuất hiện nhiều lần hơn giá trị còn lại.
Đáp án là vị trí cuối cùng của giá trị xuất hiện nhiều lần hơn. Thật vậy, nếu đoạn con chứa cả giá trị 0 và 1 thì số lần xuất hiện của nó tối đa cũng là số lần xuất hiện của giá trị có tần số thấp hơn. Nếu đoạn con chỉ chứa một giá trị duy nhất thì nó sẽ xuất hiện nhiều lần nhất nếu độ dài đúng bằng 1. - TH đặc biệt: \(n\) chẵn, các số 0 và 1 đứng xen kẽ nhau.
Chỉ trong trường hợp này thì đáp án là \(L = n-1, R = n\). Tần số là \(n/2\)
Subtask 4:
Từ quan sát ở subtask 3, ta tổng quát lên thuật toán của subtask 4.
Đầu tiên, để tiện xử lý ta ánh xạ các giá trị trong dãy a về phạm vi \([1,n]\) (nén số).
Sau đó, đếm tần số (số lần xuất hiện) của mỗi giá trị trong a.
Nếu có một giá trị nào đấy có tần số lớn hơn hẳn mọi giá trị khác, đáp án chính là vị trí cuối cùng chứa giá trị đấy.
Ngược lại : đặt \(t\) là tần số lớn nhất. Ta cần xét mọi đoạn con xuất hiện đúng \(t\) lần.
Vì đoạn con này xuất hiện \(t\) lần nên mọi giá trị trong nó đều phân biệt.
Giả sử giá trị \(x\) đứng liền trước giá trị \(y\) trong đoạn con cần tìm, như vậy thì trong cả \(t\) lần xuất hiện của đoạn con ta phải có giá trị \(x\) đứng liền trước giá trị \(y\) → lưu danh sách các vị trí xuất hiện trong mảng a (theo thứ tự tăng) của một giá trị \(v\) bất kì để kiểm tra.
Lúc này, chỉ cần quan tâm \(i\) là các vị trí xuất hiện cuối cùng của những giá trị có tần số là \(t\). Bằng vài thao tác đơn giản, ta có thể biết được với một vị trí \(i\) bất kì thì độ dài lớn nhất của đoạn con xuất hiện đúng \(t\) lần, bắt đầu từ vị trí \(i (L = i)\) là bao nhiêu. Tất cả được thực hiện trong thời gian \(O(n)\).
Độ phức tạp \(O(nlog_2(n))\) (chi phí sắp xếp).
Source code:
// Flower_On_Stone
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 10;
int n;
int a[MAX_N], cnt[MAX_N], par[MAX_N];
pair<int, int> Line[MAX_N];
vector<int> pos[MAX_N];
int find_par(int u)
{
if (par[u] < 0)
{
{
return u;
}
}
par[u] = find_par(par[u]);
return par[u];
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef Flower_On_Stone
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // Flower_On_Stone
cin >> n;
vector<int> v;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
v.push_back(a[i]);
}
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
int ans = 0;
pair<int, int> res = make_pair(0, 0);
for (int i = 1; i <= n; i++)
{
int x = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
a[i] = x;
++cnt[x];
ans = max(ans, cnt[x]);
pos[x].push_back(i);
}
vector<int> candidates;
for (int i = 1; i <= n; i++)
{
if (cnt[i] == ans)
{
Line[i] = make_pair(pos[i][ans - 1], pos[i][ans - 1]);
if (res.first < pos[i][ans - 1])
{
res = make_pair(pos[i][ans - 1], pos[i][ans - 1]);
}
candidates.push_back(i);
}
}
for (int i = 1; i <= n; i++)
{
par[i] = -1;
}
sort(candidates.begin(), candidates.end(), [&](int a, int b)
{ return pos[a][0] < pos[b][0]; });
auto merge = [&](int u, int v) -> void
{
u = find_par(u), v = find_par(v);
if (u == v)
return;
if (par[u] > par[v])
swap(u, v);
Line[u].first = min(Line[u].first, Line[v].first);
Line[u].second = max(Line[u].second, Line[v].second);
if (Line[u].second - Line[u].first + 1 > res.second - res.first + 1)
{
res = Line[u];
}
else
{
if ((Line[u].second - Line[u].first + 1 == res.second - res.first + 1) && Line[u].first > res.first)
{
res = Line[u];
}
}
par[u] += par[v];
par[v] = u;
};
int s = candidates.size();
for (int i = 0; i < s - 1; i++)
{
int u = candidates[i], v = candidates[i + 1];
bool ok = true;
for (int j = 0; j < ans; j++)
{
ok &= (pos[u][j] + 1 == pos[v][j]);
}
if (ok)
merge(u, v);
}
cout << res.first << " " << res.second;
return 0;
}
Bình luận