Constructive Algorithms

Điều kiện cần

Trước khi cố xây, hỏi: nếu có đáp án thì nó phải thỏa gì? Có thể là tính chẵn lẻ của một tổng, đại lượng không đổi qua các phép, giới hạn trên của một đại lượng, hay đơn giản là thử $n = 1, 2, 3$ bằng tay.

Điều kiện cần tìm được thường chính là điều kiện đủ. Khi đó nửa còn lại của bài là xây một đáp án cho mọi trường hợp thỏa điều kiện. Nếu không xây được cho một trường hợp, hoặc điều kiện chưa đủ, hoặc mẫu chưa đúng: thử trường hợp đó bằng vét cạn.

Ví dụHai Nửa Cân Bằng

Đề. Với $n$ chẵn ($n \le 2 \cdot 10^5$), in $n$ số dương khác nhau: $n/2$ số chẵn trước, $n/2$ số lẻ sau, hai nửa có tổng bằng nhau; không được thì in NO.

Lời giải. Đặt $h = n/2$. $h$ lẻ thì vô nghiệm như câu hỏi trên. $h$ chẵn: lấy các số chẵn $2, 4, \dots, 2h$, tổng $h(h + 1)$, và các số lẻ $1, 3, \dots, 2h - 3$, tổng $(h - 1)^2$. Số lẻ cuối cùng bù phần thiếu: $h(h + 1) - (h - 1)^2 = 3h - 1$. Nó lẻ vì $h$ chẵn, và lớn hơn $2h - 3$ nên không trùng số nào. Với $n = 12$, $h = 6$, số cuối là 17.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll T;
    cin >> T;
    while (T--) {
        ll n;
        cin >> n;
        ll h = n / 2;
        if (h % 2) {
            cout << "NO\n";
            continue;
        }
        cout << "YES\n";
        for (ll i = 1; i <= h; i++) cout << 2 * i << ' ';
        for (ll i = 1; i < h; i++) cout << 2 * i - 1 << ' ';
        cout << 3 * h - 1 << '\n';
    }
}

ChạyInput3
12
14
16

OutputYES
2 4 6 8 10 12 1 3 5 7 9 17
NO
YES
2 4 6 8 10 12 14 16 1 3 5 7 9 11 13 23

Một công thức

Khi đáp án là vài con số, hãy thử biểu diễn chúng qua dữ liệu vào bằng một công thức, thường là những bội đơn giản. Viết công thức ra rồi kiểm từng điều kiện của đề một cách riêng rẽ: đẳng thức, chia hết, khác nhau, nằm trong miền. Điều kiện nào hỏng ở trường hợp biên (một tham số bằng 1, hai số trùng nhau) thì hoặc đó là trường hợp vô nghiệm, hoặc phải tách riêng.

Ví dụBộ Ba Chia Hết

Đề. Số “loại I” chia hết cho $AB$, số “loại II” chia hết cho $A$ nhưng không chia hết cho $AB$. Tìm ba số dương khác nhau $x + y = z$, đúng một số loại I và hai số loại II; không có thì in NO. $A, B \le 10^6$.

Lời giải. $B = 1$ thì mọi bội của $A$ đều chia hết cho $AB = A$, không có số loại II: vô nghiệm. $B \ge 2$: lấy $x = AB$, $y = A(B - 1)$, $z = A(2B - 1)$. Đẳng thức đúng. $x$ loại I. $y$ và $z$ chia hết cho $A$; $B - 1$ và $2B - 1 \equiv -1$ không chia hết cho $B$ khi $B \ge 2$, nên chúng là loại II. Ba số khác nhau vì $B - 1 < B < 2B - 1$. Mọi số không quá $2 \cdot 10^{12}$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll T;
    cin >> T;
    while (T--) {
        ll a, b;
        cin >> a >> b;
        if (b == 1) cout << "NO\n";
        else cout << "YES\n" << a * b << ' ' << a * (b - 1) << ' ' << a * (2 * b - 1) << '\n';
    }
}

ChạyInput3
9 1
6 4
11 7

OutputNO
YES
24 18 42
YES
77 66 143

Xếp theo lớp

Điều kiện kiểu “hai phần tử kề nhau không hơn kém đúng 1” hay “hiệu hai số kề nằm trong $[2, 4]$” gợi ý chia các số thành lớp theo chẵn lẻ (hay theo số dư): trong cùng một lớp, hai số liên tiếp đã cách nhau 2.

Xếp hết một lớp rồi tới lớp kia. Việc còn lại là kiểm chỗ nối giữa hai lớp, thường cần chọn khéo hai đầu nối. Trường hợp nhỏ không đủ chỗ cho chỗ nối thì kiểm bằng tay hay vét cạn: chúng thường là các trường hợp vô nghiệm.

Ví dụMa Trận Không Kề Nhau

Đề. Điền $1..n^2$ vào ma trận $n \times n$ ($n \le 100$) sao cho hai ô chung cạnh không chứa hai số liên tiếp; không được thì in $-1$.

Lời giải. $n = 2$: mỗi ô kề hai ô khác, số 2 có hai láng giềng phải tránh 1 và 3 nhưng chỉ còn ô chéo, vô nghiệm. Với $n \ne 2$, điền theo từng hàng các số lẻ $1, 3, 5, \dots$ rồi tiếp các số chẵn $2, 4, \dots$. Hai ô kề ngang cùng lớp hơn kém 2; hai ô kề dọc cùng lớp hơn kém $2n$. Ô lẻ cạnh ô chẵn chỉ xảy ra ở chỗ nối, nơi số lẻ gần $n^2$ còn số chẵn gần 2, hơn kém nhiều khi $n \ge 3$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll T;
    cin >> T;
    while (T--) {
        ll n;
        cin >> n;
        if (n == 2) {
            cout << -1 << '\n';
            continue;
        }
        ll cur = 1;
        for (ll i = 0; i < n; i++) {
            for (ll j = 0; j < n; j++) {
                cout << cur << ' ';
                cur += 2;
                if (cur > n * n) cur = 2;
            }
            cout << '\n';
        }
    }
}

ChạyInput4
1
2
3
4

Output1
-1
1 3 5
7 9 2
4 6 8
1 3 5 7
9 11 13 15
2 4 6 8
10 12 14 16

Bất biến

Có điều kiện nhìn phức tạp nhưng tương đương một điều kiện toàn cục đơn giản. “XOR các vị trí lẻ bằng XOR các vị trí chẵn” tương đương “XOR cả mảng bằng 0”, vì $u = v$ khi và chỉ khi $u \oplus v = 0$. “Tổng hai nửa bằng nhau” là “tổng có dấu bằng 0”.

Khi đó chọn tự do gần hết các phần tử, rồi dùng vài phần tử cuối để bù cho bất biến đúng. Phần khó là bảo đảm phần tử bù không trùng các phần tử đã chọn, thường bằng cách cho nó mang những bit cao mà các phần tử khác không có.

Ví dụCân Bằng XOR Theo Vị Trí

Đề. Với $n \le 2 \cdot 10^5$, in $n$ số không âm khác nhau nhỏ hơn $2^{31}$ có XOR các vị trí lẻ bằng XOR các vị trí chẵn.

Lời giải. Cần XOR cả mảng bằng 0. Lấy $1, 2, \dots, n - 3$, tất cả nhỏ hơn $2^{20}$; thêm $2^{20}$, $2^{21}$, và phần tử cuối là XOR của mọi số đã có. Phần tử cuối có cả bit 20 lẫn bit 21, nên khác mọi số trước: các số nhỏ không có bit 20, còn $2^{20}$ và $2^{21}$ chỉ có một trong hai bit. XOR cả mảng bằng 0 theo cách chọn phần tử cuối.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll T;
    cin >> T;
    while (T--) {
        ll n, x = 0;
        cin >> n;
        for (ll i = 1; i <= n - 3; i++) {
            cout << i << ' ';
            x ^= i;
        }
        ll p = 1 << 20, q = 1 << 21;
        cout << p << ' ' << q << ' ' << (x ^ p ^ q) << '\n';
    }
}

ChạyInput3
3
4
6

Output1048576 2097152 3145728
1 1048576 2097152 3145729
1 2 3 1048576 2097152 3145728

Đẩy về cực đại

Khi đề cho phép tăng (hay thêm, hay bật) tùy ý, hãy xét đáp án cực đại: tăng mọi thứ tới mức lớn nhất còn có thể hợp lệ. Thường đáp án cực đại hoặc đúng, hoặc nếu nó sai thì mọi đáp án khác cũng sai.

Chẳng hạn trên lưới, ô có giá trị $k > 0$ cần $k$ láng giềng dương, nên $k$ không vượt số ô chung cạnh của nó. Có ô vượt thì vô nghiệm. Không có ô nào vượt thì đặt mọi ô bằng đúng số ô chung cạnh: mọi ô đều dương nên điều kiện đúng với dấu bằng.

Vét cạn tìm quy luật

Khi không đoán được mẫu, viết một chương trình vét cạn trên kích thước nhỏ ($n \le 8$, xâu dài $\le 12$), in ra mọi đáp án hay đáp án tốt nhất, rồi nhìn. Các đáp án có chung hình dạng gì? Đại lượng tối ưu tăng theo quy luật nào?

Từ đó phát biểu một mẫu, chứng minh nó, và giữ chương trình vét cạn để so với lời giải trên nhiều test ngẫu nhiên. Một quy luật hay gặp: tích của nhiều thừa số lớn nhất khi tổng cố định thì các thừa số đều nhau, hơn kém nhau không quá 1.

Ví dụXâu Ngắn Nhất Nhiều Dãy Con

Đề. Cho $k \le 10^{16}$. In xâu ngắn nhất có ít nhất $k$ dãy con bằng codeforces.

Lời giải. Vét cạn trên $k$ nhỏ cho thấy đáp án tốt nhất luôn có dạng: chữ thứ $i$ của codeforces lặp $c_i$ lần liền nhau, theo đúng thứ tự. Số dãy con khi đó là $c_1 c_2 \cdots c_{10}$, độ dài là tổng các $c_i$. Với tổng cố định, tích lớn nhất khi các $c_i$ hơn kém nhau không quá 1; nên bắt đầu với mọi $c_i = 1$ và lần lượt tăng $c_1, c_2, \dots$ vòng tròn tới khi tích đạt $k$. Mỗi lần tăng thêm 1 ký tự và tích tăng nhanh nhất có thể. Với $k = 12$, tăng bốn chữ đầu cho tích 16.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll k, c[10];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> k;
    string s = "codeforces";
    for (ll i = 0; i < 10; i++) c[i] = 1;
    for (ll i = 0;; i = (i + 1) % 10) {
        ll prod = 1;
        for (ll j = 0; j < 10; j++) prod *= c[j];
        if (prod >= k) break;
        c[i]++;
    }
    for (ll i = 0; i < 10; i++) cout << string(c[i], s[i]);
    cout << '\n';
}

ChạyInput12

Outputccooddeeforces