Cửa Hàng Số Học

Nguồn: Codeforces Group Độ khó: Dễ Xử lý chuỗi Nhận xét

Đề bài

Sắp tới là sinh nhật em Hạnh nên anh Hoàng quyết định tìm một món quà thật ý nghĩa. Biết Hạnh có đam mê với bộ môn nhị phân, Hoàng đến ngay cửa hàng số học tìm ra bộ nhị phân ưng ý. Nhưng cửa hàng chỉ bán dãy nhị phân $S$ có độ dài $N$ ($1 \le N \le 10^6$). Để lấy ra được bộ nhị phân ưng ý thì Hoàng cần phải chọn các cặp 10 bất kỳ trong dãy $S$ và xóa 1 trong 2 số.

Hãy giúp Hoàng tìm ra dãy có độ dài ngắn nhất sau khi xóa. Nếu có nhiều dãy có độ dài giống nhau thì hãy in ra dãy có thứ tự chữ cái nhỏ nhất. Dãy $A$ có thứ tự chữ cái nhỏ hơn $B$ nếu $A_1 = B_1,$ $A_2$ $= B_2,$ $A_3$ $= B_3,$ $\ldots,$ $A_i$ $\lt B_i,$ $\ldots$

Đầu vào

• Dòng đầu tiên là số tự nhiên $N$ ($1 \le N \le 10^6$).
• Dòng thứ hai là dãy $S$ có độ dài $N$ chỉ bao gồm số 1 hoặc 0.

Đầu ra: in ra một dãy nhị phân đẹp nhất mà Hoàng có thể tìm được sau khi thực hiện tất cả các bước xóa.

Input 1

10
0001111111

Output 1

0001111111

Input 2

4
0101

Output 2

001

Input 3

8
11001101

Output 3

01

Input 4

1
1

Output 4

1

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Mấu chốt: chuỗi dạng 1……0 luôn xoá được về đúng 1 số 0

Bài này thoạt nhìn phức tạp và tưởng là dạng xử lý bit, nhưng nếu đọc kỹ đề thì sẽ nhận ra đây chỉ là bài tập xử lý chuỗi đơn giản thôi.

Mấu chốt để giải quyết bài này là em phải nhìn ra quy tắc xoá mà đề bài đưa ra. Nếu với quy tắc xoá như vậy thì chỉ cần chuỗi có dạng 1………0, tức là đầu tiên là số 1 và cuối cùng là số 0, còn lại ở giữa tụi nó là gì tuỳ ý, thì với quy tắc xoá đề bài đưa ra, sau cùng kết quả chỉ là 0 (ví dụ em có thể thử với các trường hợp 1000000 hay 11111110 hay 1001100101010010 xem có đúng như anh nói không?).

Ví dụ với test 3, phần giữa 1100110 (bắt đầu bằng 1, kết thúc bằng 0) được xoá dần về 1 số 0 như sau (2 ô viền là cặp 10 được chọn, ô gạch là số bị xoá):

1100110

→

100110

→

10110

→

1110

→

110

→

10

→

0

Vì sao lại như vậy? (giải thích thêm)

Xoá được về "0": trong chuỗi bắt đầu bằng 1 và kết thúc bằng 0, chắc chắn có ít nhất 1 chỗ số 1 đứng ngay trước số 0. Nếu chuỗi còn số 1 nào khác ngoài số 1 đầu tiên, hoặc còn nhiều số 0, ta luôn chọn được 1 cặp 10 để xoá mà chuỗi vẫn giữ được dạng "đầu là 1, cuối là 0"; cứ thế đến khi còn 10 thì xoá số 1, còn lại đúng 0.

Không thể làm tốt hơn: các số 0 ở đầu chuỗi không có số 1 nào đứng trước nên không bao giờ nằm trong cặp 10, tương tự các số 1 ở cuối chuỗi không có số 0 nào đứng sau. Vậy khối 0 đầu và khối 1 cuối không thể bị xoá. Còn phần ở giữa (nếu có) thì ít nhất phải còn lại 1 số, và để thứ tự nhỏ nhất thì số còn lại đó nên là 0.

Em nhập một dãy nhị phân rồi bấm Tiếp để xem phần giữa bị xoá dần về một số 0 như thế nào:

Dãy S

Ví dụ nhanh:

Lời giải O(N)

Thì nếu đã nhìn ra điều đó thì giờ đây cách giải quyết bài này rất đơn giản:

1. Kiểm tra khúc đầu tiên của chuỗi, nếu là số 0 thì đếm xem có bao nhiêu số 0 liên tiếp (cnt0).
2. Kiểm tra khúc cuối cùng của chuỗi, nếu là số 1 thì đếm xem có bao nhiêu số 1 liên tiếp (cnt1).
3. Nếu 2 số lượng này cộng lại bằng đúng độ dài chuỗi ban đầu (chuỗi có dạng 000…0111…1, không có cặp 10 nào) thì kết quả xuất ra chuỗi ban đầu.
4. Ngược lại, xuất ra đủ cnt0 số 0 đầu tiên, sau đó xuất thêm một số 0 nữa là kết quả sau khi áp dụng quy tắc xoá với chuỗi ở giữa, cuối cùng xuất ra đủ cnt1 số 1 cuối cùng.

S	cnt0	Phần giữa	cnt1	Kết quả
0001111111	3	(rỗng)	7	0001111111
0101	1	10	1	001
11001101	0	1100110	1	01
1	0	(rỗng)	1	1

Độ phức tạp sẽ là $O(N)$ em nhé, với $N$ là độ dài chuỗi ban đầu. Code cho em tham khảo:

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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s;
    cin >> s >> s;
    int cnt0 = 0, cnt1 = 0;

    for(int i = 0; i < s.length(); ++i)
    {
        if(s[i] == '0')
            cnt0++;
        else
            break;
    }

    for(int i = s.length() - 1; i >= 0; --i)
    {
        if(s[i] == '1')
            cnt1++;
        else
            break;
    }

    if(cnt0 + cnt1 == s.length())
        cout << s;
    else
    {
        while(cnt0--)
            cout << "0";

        cout << "0";

        while(cnt1--)
            cout << "1";
    }

    return 0;
}

_ = input().strip()
s = input().strip()

cnt0 = 0
cnt1 = 0

for ch in s:
    if ch == '0':
        cnt0 += 1
    else:
        break

for ch in reversed(s):
    if ch == '1':
        cnt1 += 1
    else:
        break

if cnt0 + cnt1 == len(s):
    print(s)
else:
    print("0" * cnt0 + "0" + "1" * cnt1)

C++▶ Chạy tay từng dòng codeĐếm khối 0 ở đầu, khối 1 ở cuối; phần giữa (nếu có) thu gọn còn 1 số 0. O(N).

Dữ liệu vào (stdin) – sửa thoải mái4 0101

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main()

5{

6 ios::sync_with_stdio(0);

7 cin.tie(0);

8 string s;

9 cin >> s >> s;

10 int cnt0 = 0, cnt1 = 0;

11

12 for(int i = 0; i < s.length(); ++i)

13 {

14 if(s[i] == '0')

15 cnt0++;

16 else

17 break;

18 }

19

20 for(int i = s.length() - 1; i >= 0; --i)

21 {

22 if(s[i] == '1')

23 cnt1++;

24 else

25 break;

26 }

27

28 if(cnt0 + cnt1 == s.length())

29 cout << s;

30 else

31 {

32 while(cnt0--)

33 cout << "0";

34

35 cout << "0";

36

37 while(cnt1--)

38 cout << "1";

39 }

40

41 return 0;

42}

ChậmVừaNhanhRất nhanh

Lưu ý nhỏ: trong code C++, dòng cin >> s >> s; là đọc luôn số $N$ vào s rồi đọc đè chuỗi nhị phân lên, vì độ dài chuỗi lấy bằng s.length() nên không cần dùng tới $N$. Mình đã kiểm tra code với tất cả các chuỗi độ dài từ 1 đến 9 (và ngẫu nhiên đến 12) so với cách thử mọi cách xoá, đều cho đúng kết quả; với $N = 10^6$ cả 2 bản đều chạy rất nhanh.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇