Cửa Hàng Số Học
Đề 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.
10
000111111100011111114
01010018
11001101011
11Lờ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ày chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesMấ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á):
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:
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:
- 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). - 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). - 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. - Ngược lại, xuất ra đủ
cnt0số 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 đủcnt1số 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)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.
Nhận xét
Đăng nhận xét