Hướng dẫn cho Cắt xâu (TS10 LQĐ, Đà Nẵng 2018)

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

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: SPyofgame

`Spoiler Alert`

Hint 1

Nhận vào từng kí tự, ngắt xâu khi đã tồn tại kí tự trước đó

Gọi \(res\) là số lần xâu con, khởi tạo là \(1\)

Mình dùng một mảng đánh dấu các phần tử, khi phần tử đã tồn tại ta ngắt đi và reset lại mảng

Reference AC code | \(O(n)\) time | \(O(n)\) auxiliary space | String

C++

int main()
{
    string s;
    cin >> s; /// Nhan xau

    int res = 1;
    vector<bool> mark(256, false);
    for (char c : s) {         /// Duyet tung ki tu
        if (mark[c] == true) { /// Neu ton tai phan tu truoc do  
            res++;             /// Ngat xau
            fill(mark.begin(), mark.end(), false); /// Reset mang
        }
        mark[c] = true; /// Danh dau phan tu
    }

    cout << res; /// Xuat ket qua
    return 0;
}

Another Approach

Online Solving: Ta có thể không cần lưu xâu

Reference AC code | \(O(n)\) time | \(O(1)\) auxiliary space | Online Solving, String

C++

inline bool isLowerLatin(char c) { return 'a' <= c && c <= 'z'; }
int main()
{
    int res = 1;
    vector<bool> mark(256, false);
    for (char c; isLowerLatin(c = getchar()); ) {
        if (mark[c]) { /// Neu ton tai
            res++;     /// Ngat xau
            for (char t = 'a'; t <= 'z'; ++t) mark[t] = false; /// Reset mang
        }

        mark[c] = true; /// Danh dau
    }

    cout << res; /// Xuat ket qua
    return 0;
}

Bình luận

Tải bình luận...

Không có bình luận nào.