Xâu đảo ngược

Nguồn: CLUE OJ Độ khó: Dễ Hai đầu xâu Đổi chỗ

Đề bài

Cho một xâu $S$. Hãy in ra xâu đảo ngược của $S$, tức là các kí tự của $S$ viết theo thứ tự từ cuối về đầu.

Dữ liệu vào:

Một dòng duy nhất là xâu $S$ gồm các kí tự in được (chữ, số, dấu câu, dấu cách); xâu không bắt đầu và không kết thúc bằng dấu cách.

Kết quả:

In ra xâu đảo ngược của $S$.

Giới hạn:

• $1 \le |S| \le 10^6$

Subtask:

• Subtask 1 (50% số điểm): $|S| \le 1000$.
• Subtask 2 (50% số điểm): không có ràng buộc gì thêm.

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

redochnidhniv

Ví dụ 1 – output

vinhdinhcoder

Ví dụ 2 – input

Hom nay la thu bay

Ví dụ 2 – output

yab uht al yan moH

Nguồn: phỏng theo bài "XÂU ĐẢO NGƯỢC" – vinhdinhcoder.net (chủ đề Xâu kí tự).

Lời mở đầu

Đảo ngược xâu bằng cách đổi chỗ từng cặp kí tự đối xứng – kỹ thuật "hai đầu" sẽ còn gặp lại ở bài kiểm tra xâu đối xứng. Ghi chú: đề gốc chỉ nói xâu dài không quá 1 triệu, chứa kí tự in được; mình giữ $|S| \le 10^6$, xâu có thể có dấu cách nhưng không bắt đầu/kết thúc bằng dấu cách.

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

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test20 testÝ tưởngđổi chỗ s[i] ↔ s[n−1−i]Lời giảicode C++ / PythonCái bẫycách làm saiTổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 20 test, mỗi test đúng được 1 phần điểm như nhau. Test 1–10 ngắn, test 11–20 dài tới $10^6$ kí tự.

Test	Nội dung kiểm tra
1	Ví dụ của đề
2–10	Xâu ngắn: 1–2 kí tự, xâu đối xứng, xâu có dấu cách và dấu câu
11–20	Xâu ngẫu nhiên dài tới $10^6$ (có dấu cách) – thêm kí tự vào đầu xâu t = c + t bị quá thời gian

Ý tưởngĐổi chỗ hai đầu, tiến dần vào giữa

Với xâu dài $n$, kí tự s[i] sau khi đảo sẽ nằm ở vị trí n - 1 - i. Ta đổi chỗ s[0] ↔ s[n-1], s[1] ↔ s[n-2], … cho tới giữa xâu – tức là i chạy từ $0$ tới n / 2 - 1.

Chỉ đi tới nửa xâu

Nếu cho i chạy hết $n$ vòng, mỗi cặp bị đổi chỗ hai lần – xâu quay về như cũ!

Em nhập xâu rồi bấm Tiếp để xem từng cặp được đổi chỗ:

Xâu =

Ví dụ nhanh:

Lời giảiĐổi chỗ n / 2 cặp kí tự

Mình tự viết phép đổi chỗ bằng biến tạm t cho rõ (C++ có sẵn swap và cả reverse).

C++▶ Chạy tay từng dòng codeĐổi chỗ s[i] với s[n−1−i] cho i từ 0 tới n/2 − 1.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Python: s[::-1] – lát cắt với bước $-1$ đi từ cuối về đầu.
2. Cách "nối từng kí tự vào đầu xâu mới" (t = c + t) cho đúng kết quả nhưng mỗi lần phải chép lại cả xâu $t$, tổng cộng $O(n^2)$ – quá chậm với $n = 10^6$.

Không gian$O(|S|)$

Thời gian$O(|S|)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.025s. Bản Python đúng 20/20 test, chạy lâu nhất 0.028s. Full điểm.

Cái bẫyNhững cách làm sai hay gặp

Các cách làm sai mình đã chấm thử trên bộ test:

Cách làm sai	Đúng	Ghi chú
Đọc bằng cin >> s	8/20	sai test 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 19, 20
Nối vào đầu: t = c + t	13/20	sai test 13, 14, 15, 16, 17, 18, 19
Đổi chỗ đủ $n$ vòng (đảo hai lần)	3/20	sai test 1, 2, 4, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Đảo ngược thứ tự các từ	3/20	sai test 1, 2, 4, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
Lời giải chuẩn	C++	20/20	0.025s	Full điểm
	Python	20/20	0.028s	Full điểm
cin >> s	C++	8/20	–	Mất 12 test
t = c + t	C++	13/20	–	Mất 7 test
Đổi n lần	C++	3/20	–	Mất 17 test
Đảo từ	C++	3/20	–	Mất 17 test

Ghi chú của mình: kỹ thuật "hai đầu tiến vào giữa" (i từ trái, n−1−i từ phải) là nền tảng của bài xâu đối xứng và kỹ thuật hai con trỏ sau này.

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 😇