Hướng dẫn giải của Bedao Regular Contest 01 - ZSTRING


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.

Tác giả: bedao

Đầu tiên để có thể tạo được một chuỗi ta cần có những điều kiện sau:

  • Chuỗi có ~1~ phần tử thì phần tử đầu luôn luôn là 'z'
  • Chuỗi được tạo ra thì các ký tự luôn có thứ tự từ điển bé hơn hoặc bằng 'z'lớn hơn hoặc bằng 'a'
  • Nếu ~A_1~ = ~1~ và ~2~ ~\leq~ n thì ta không thể tạo được chuỗi nào phù hợp

Bằng phương pháp tham lam ta có thể tạo được chuỗi có thứ tự từ điển nhỏ nhất khi :

  • Đối với ~i~ lẻ ta rút ra nhận xét rằng với từ đầu tiên được thêm vào dãy trong lúc xử lý thì từ đó phụ thuộc vào thứ tự từ điển từ cuối cùng của lần xét ~i-1~ trước trừ đi cho ~1~ và ~A_i-1~ phần tử còn lại là một dãy ký tự giảm dần liên tiếp có kết thúc là ký tự 'a' ( luôn thỏa mãn ký tự đứng sau có thứ tự từ điển bé hơn ký tự đứng trước )

Vậy việc cần làm của chúng ta đối với lần xét i lẻ ta chỉ cần thêm ký tự đầu tiên vào dãy theo quy luật bằng phần tử cuối của lần xử lý ~i-1~ trừ ~1~ và sao đó ta duyệt ~A_i-1~ lần thêm lần lượt các ký tự từ 'a'+~A_i-2~ đến 'a' ( vì đã thêm ~1~ ký tự và đây là chuỗi liên tiếp có ~A_i-1~ phần tử có thứ tự từ điển giảm dần và có kết thúc tại 'a' ) và điều kiện để chuỗi đó thỏa mãn là 'a'+~A_i-2~ luôn có thứ tự từ điển bé hơn phần tử đầu tiên được thêm vào.

  • Đối với ~i~ chẵn ta rút ra nhận xét rằng đây chỉ là là dãy liên tiếp tăng dần với từ đầu tiên luôn bằng 'b' vì ta luôn có từ cuối của dãy sau khi xét ~i~ lẻ là 'a'. Ta chỉ cần duyệt ~A_i~ lần và mỗi lần lặp ta thêm lần lượt các ký tự tăng dần bắt đầu từ 'b' ( luôn thỏa mãn ký tự đứng sau có thứ tự từ điển lớn hơn ký tự đứng trước ) và ta cần xét xem các thứ tự từ điển của ký tự đấy có nằm trong đoạn từ 'a' đến 'z' hay không.

Lưu ý: Ta phải quan tâm với phần tử cuối sau khi xét thì kiểm tra xem từ đó có lớn hơn hoặc bằng ~A_{i+1}+~ 'a' hay không ( mục đích tạo thêm tiếp ~A_{i+1}~ ký tự có quy luật được ). Nếu có thì giữ nguyên còn nếu không thì thay ký tự đó bằng ký tự có thứ tự từ điển là ~A_{i+1}~+ 'a' .

Code mẫu

#include <bits/stdc++.h>
using namespace std;
int T, n, a[20010];
string s;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("ZSTRING.INP", "r", stdin);
    //freopen("ZSTRING.OUT", "w", stdout);
    cin >> T;
    for (int iTest = 1; iTest <= T; iTest++) {
        cin >> n;
        bool oce = 1;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            if (a[i] >= 27)
                oce = 0;
        }
        if (a[1] == 1 && n == 1) {
            cout << "z\n";
            continue;
        }
        if (a[1] == 1 || oce == 0) {
            cout << -1 << '\n';
            continue;
        }
        s = "z";
        a[1]--;
        int pos = 24;
        for (int i = 1; i <= n; i++) {
            if (i % 2 == 0) {
                pos = 1;
                int d = 1;
                while (d < a[i]) {
                    if (pos < 0 || pos > 25) {
                        oce = 0;
                        break;
                    }
                    s += ('a' + pos);
                    pos++;
                    d++;
                }
                if (i < n)
                    pos = max(pos, a[i+1]);
                if (pos < 0 || pos > 25) {
                        oce = 0;
                        break;
                    }
                s += ('a' + pos);
            }
            else {
                pos = a[i] - 1;
                int d = 1;
                while (d <= a[i]) {
                    if (pos < 0 || pos > 25) {
                        oce = 0;
                        break;
                    }
                    s += ('a' + pos);
                    pos--;
                    d++;
                }
            }
            if (oce == 0) break;
        }
        if (oce == 0) cout << -1 << '\n';
        else cout << s << '\n';
    }
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.