🦑-[SUSHI]-🍣

--- title: "🦑-[SUSHI]-🍣" tags: [algorithm, competitive-programming, solution] author: "**Phạm Minh Quân**" created: "**14/03/2025**" --- # 📌 **Đề bài** 🔗 **[Xem đề bài tại đây](https://drive.google.com/file/d/1fwF_rQPaDxhaipVECDuguQpIVsvgizV_/view)** Cho dãy sushi gồm **n** miếng (**`1`**: 🐟 cá ngừ, **`2`**: 🐍 lươn). Tìm đoạn con liên tiếp **dài nhất** thỏa mãn: - ✅ **Chỉ có hai loại sushi**. - ✅ **Số lượng mỗi loại bằng nhau**. - ✅ **Nửa đầu chỉ chứa một loại sushi**. --- # 📖 **Mục lục** [TOC] --- # 🏆 **Các Subtasks** ## 🔹 **Subtask 1: Bruteforce** 🛠️ - **Ràng buộc**: $N \leq 10^3$ - **Ý tưởng**: 📌 Ta sẽ duyệt qua **tất cả các đoạn con** của mảng. **Tính chất quan trọng:** - 🔹 Độ dài của đoạn **luôn chẵn** ✅ - 🔹 Nửa đầu đoạn chứa **toàn bộ một loại cá** - 🔹 Nửa sau đoạn chứa **toàn bộ loại cá còn lại** 🔥 **Nhận xét:** Nếu độ dài lẻ ❌, khi chia đôi sẽ có **một phần tử dư**, dẫn đến mất cân bằng. **Ví dụ:** - ✅ **Dãy hợp lệ:** `2 2 1 1` (độ dài **chẵn**). - ❌ **Dãy không hợp lệ:** 1 2 2 1 (Hai nửa **không cùng một loại**) - ❌ **Dãy không hợp lệ:** `2 1 1 2 1` (độ dài **lẻ**, có một số dư khiến dãy mất cân bằng). ⟶ **Độ dài đoạn cần tìm luôn là số chẵn**. --- ### 📌 Cách thực hiện Gọi **độ dài đoạn** là `len`, ta chia đoạn thành **hai phần bằng nhau**: - **Nửa đầu**: `[i → i + mid - 1]` - **Nửa sau**: `[i + mid → i + len - 1]` Trong đó, `mid = len / 2`. - Ta sẽ dùng mảng 2 mảng prefix để lưu lại số lượng 2 loại Sushi Ta có **2 trường hợp** có thể xảy ra - TH1: **Nửa đầu** toàn **sushi 1**, **nửa sau** toàn **sushi 2** - TH2: **Nửa đầu** toàn **sushi 2**, **nửa sau** toàn **sushi 1** --- ### 📜 **Cài đặt thuật toán với độ phức tạp $O(N^2)$** ```cpp #include <bits/stdc++.h> #define int long long #define name "SUSHI" using namespace std; const int N = 2e6 + 9; int a[N], pre0[N], pre1[N]; void file() { ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); freopen(name ".inp", "r", stdin); freopen(name ".out", "w", stdout); } int32_t main() { file(); int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; pre0[i] = (a[i] == 1) ? pre0[i - 1] + 1 : pre0[i - 1]; pre1[i] = (a[i] == 2) ? pre1[i - 1] + 1 : pre1[i - 1]; } int maxx = 0; for (int len = 2; len <= n; len += 2) { for (int i = 1; i <= n - len + 1; i++) { int mid = len / 2; int sl1_1 = pre0[i + mid - 1] - pre0[i - 1]; int sl2_1 = pre1[i + len - 1] - pre1[i + mid - 1]; int sl1_2 = pre1[i + mid - 1] - pre1[i - 1]; int sl2_2 = pre0[i + len - 1] - pre0[i + mid - 1]; if ((sl1_1 == sl2_1 && sl1_1 + sl2_1 == len) || (sl2_2 == sl1_2 && sl1_2 + sl2_2 == len)) { maxx = max(maxx, len); } } } cout << maxx; } ``` ## 🔹 **Subtask 2: 🦾DSU**⚡ - **Ràng buộc**: $N \leq 10^5$ - **Ý tưởng**: 📌 Ta sẽ thừa kế ý tưởng của bài trước và sẽ cải tiến lên thành **DSU - Disjoint Set Union** **Tìm hiểu thêm về DSU** - 🔹 🔗 **[Xem tại đây](https://wiki.vnoi.info/algo/data-structures/disjoint-set-union)** --- ### 💡Giải thuật tìm độ dài lớn nhất của đoạn hợp lệ ### 1️⃣ Kết nối các số liền kề Chúng ta sẽ **kết nối tất cả các số liền kề** tại vị trí $i$ nếu giá trị của chúng bằng $i$. Tức là nối các số trong hai đoạn: - **$[i \rightarrow i+1]$** - **$[i-1 \leftarrow i]$** Sau khi nối xong, chúng ta sẽ có: - **Mảng `par`**: Chứa thông tin về gốc của mỗi đoạn. - **Mảng `sz`**: Chứa số lượng phần tử trong đoạn đã nối. **Ví dụ:** ```plaintext Dãy ban đầu: [2, 2, 2, 1, 1, 2, 2] Mảng parent: [1, 1, 1, 2, 2, 3, 3] Mảng sz: [3, 3, 3, 2, 2, 2, 2] ``` --- ### 2️⃣ Xác định độ dài đoạn hợp lệ Giả sử chúng ta có đoạn số $A$ và $B$ nằm cạnh nhau: ```phaintext= A: 2 2 2 | B: 1 1 ``` Quy tắc xác định độ dài đoạn hợp lệ: - Độ dài hợp lệ = min(độ dài A, độ dài B) 📌Vì sao lại lấy $\min$? > Nếu một đoạn lớn nhưng đoạn còn lại nhỏ, thì độ dài tối đa chỉ có thể là đoạn nhỏ nhân đôi. > Ví dụ: Nếu đoạn $A$ có 3 số 2, đoạn $B$ có 2 số 1, thì ta chỉ có thể tạo được đoạn 2 2 | 1 1, không thể mở rộng thêm. --- ### 3️⃣ Lưu ý quan trọng ❌ Không thể nối cả hai bên cùng lúc Khi nối hai số 1, ta chỉ có thể nối qua trái hoặc phải, chứ không thể nối cả hai bên. - Ví dụ sai ❌: ```plaintext= 2 2 1 1 2 2 (không hợp lệ) ``` - **Lý do**: Nếu nối cả hai bên mà số lượng phần tử không đồng đều, đoạn nối sẽ bị lỗi. → **Giải pháp**: Chỉ xét một phía **(trái hoặc phải)**. --- ### 4️⃣ Tóm tắt thuật toán 🔹 **Bước 1**: 🏗️ **Khởi tạo DSU** - Tạo mảng `parent` và `sz` để quản lý các tập hợp số liên tiếp. 🔹 **Bước 2**: 🔍 **Duyệt qua từng đoạn số** và tìm độ dài hợp lệ theo công thức: 🎯 **Công thức**: - 📏 min(sz[A], sz[B]) × 2 🔹 **Bước 3**: 📊 **Tìm max_length** - Duyệt toàn bộ dãy số để tìm giá trị **lớn nhất** của đoạn hợp lệ. --- ### 📜 **Cài đặt thuật toán với độ phức tạp $O(NlogN)$** ```cpp= #include <bits/stdc++.h> #define int long long #define name "SHUSHI" using namespace std; const int N = 1e5 + 9; int a[N], par[N], sz[N]; void file() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); freopen(name ".inp", "r", stdin); freopen(name ".out", "w", stdout); } void make_set(int n) { for (int i = 1; i <= n; i++) { par[i] = i; sz[i] = 1; } } int find_p(int v) { if (par[v] == v) return v; return par[v] = find_p(par[v]); } void uni(int u, int v) { u = find_p(u); v = find_p(v); if (u == v) return; if (sz[u] < sz[v]) swap(u, v); par[v] = u; sz[u] += sz[v]; } int32_t main() { file(); int n; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; make_set(n); for (int i = 1; i <= n; i++) { if (i > 1 && a[i] == a[i - 1]) uni(i, i - 1); if (i < n && a[i] == a[i + 1]) uni(i, i + 1); } vector<int> q; q.push_back(0); for (int i = 1; i <= n; i++) { if (i < n && find_p(i) != find_p(i + 1)) { int minn = min(sz[find_p(i)], sz[find_p(i + 1)]); q.push_back(minn); } if (i > 1 && find_p(i) != find_p(i - 1)) { int minn = min(sz[find_p(i)], sz[find_p(i - 1)]); q.push_back(minn); } } cout << *max_element(q.begin(), q.end()) * 2; return 0; } ```