# Ý tưởng ban đầu
Vì bài chỉ yêu cầu xác định ĐÚNG k nhóm,
nên chúng ta có thể kiểm tra sơ bộ đầu tiên bằng cách tính tổng cả dãy (gọi là x),
và xem thử liệu nó có chia hết cho k không.
Nếu không, chúng ta xuất ra "ze".
# Thuật đệ quy
Gọi a và places lần lượt là mảng gốc và mảng lưu vị trí.
Gọi used[i] là để đánh dấu sử dụng phần tử.
Gọi f là biến lưu giá trị x // k.
Ta thực hiện như sau:
- Ở khởi đầu, gọi dff(0, 0), ý nghĩa: tìm bộ con đầu tiên (bộ thứ 0) và tổng xác định là 0.
- Ở trong, duyệt các phần tử chưa dùng và đánh dấu sử dụng, cũng như xếp chúng vào places[i] = cnt.
- Với mỗi phần tử thế, chúng ta thêm nó vào summ và giữ nguyên cnt, gọi lại đệ quy để tìm những phần tử còn lại.
Base cases:
Nếu summ == f, xảy ra hai trường hợp:
- Đã tìm đủ, tức thêm điều kiện cnt == k-1, lúc này ta thoát đệ quy và return true.
- Xác định được một bộ thỏa mãn, lúc này ta 'reset' summ về 0 và tăng cnt, tìm bộ tiếp theo.
Nếu summ > f, tức là bộ đó không thể nào thỏa, ta return false.
# Kết quả cuối cùng
Ta xét giá trị của lần gọi khởi đầu (dff(0, 0)) trong driver code, nếu nó là true,
thì ta xuất ra các vị trí trong places, chú ý mỗi phần tử +1.
Nếu nó là false, ta xuất ra "ze".
# Code mẫu
```
#include <stdio.h>
#include <bits/stdc++.h>
#include <iostream>
#define ll long long
using namespace std;
int n, k, x, f;
vector<int> places, a;
vector<bool> used;
bool dff(int cnt, int summ) {
// base
if (summ > f) return false;
if (summ == f) {
if (cnt == k-1) return true;
if (dff(cnt+1, 0)) return true;
}
// rec
for (int i=0; i<n; i++) {
if (used[i]) continue;
used[i] = true;
places[i] = cnt;
if (dff(cnt, summ+a[i])) return true;
// revert
used[i] = false;
}
return false;
}
void solve() {
if (div(x, k). rem > 0) {
cout << "ze"; return;
}
f = div(x, k).quot;
if (dff(0, 0)) {
for (int i=0; i<n; i++) cout << places[i]+1 << " ";
return;
}
cout << "ze";
return;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> k;
a.resize(n, 0);
places.resize(n, 0);
used.resize(n, false);
for (int i=0; i<n; i++) {
cin >> a[i];
x += a[i];
}
solve();
return 0;
}
```
phucnh529
Created at
6 likes