Đảo ngược xâu con
Xem PDF
Điểm:
200 (p)
Thời gian:
1.0s
Bộ nhớ:
640M
Input:
bàn phím
Output:
màn hình
Cho một xâu \(S\) có độ dài \(l\) gồm các chữ cái thường. Cho \(Q\) thao tác, mỗi thao tác chỉ gồm một số nguyên dương \(x\), yêu cầu đảo ngược xâu con từ vị trí \(x\) đến vị trí \(l−x+1\). Chú ý: xâu kí tự được đánh số từ 1 đến \(l\).
Input
- Dòng đầu tiên gồm một xâu \(S\) \((1 \leq l \leq 2 \times 10^5)\);
- Dòng thứ hai gồm một số nguyên dương \(Q\) là số thao tác đảo ngược \((Q \leq 10^5)\).
- Dòng thứ ba gồm \(Q\) số nguyên \(x_i\) \((1 \leq x_i \leq l )\)
Output
- In ra xâu cuối cùng, sau khi thực hiện \(Q\) thao tác.
Example
Test 1
Input
tinteen
3
1 1 3 Output
tietnenNote
- Truy vấn 1: đảo ngược từ vị trí 1 đến 7: neetnit.
- Truy vấn 2: đảo ngược từ vị trí 1 đến 7: tinteen.
- Truy vấn 3: đảo ngược từ vị trí 3 đến 5: tietnen.
Bình luận
Mình sẽ chia sẻ hướng làm của mình: ở bài này thứ tự đảo chuỗi sẽ không làm ảnh hưởng kết quả, mà phải là số lần đảo
Đầu tiên chúng ta sẽ quy hết các giá trị x>s.size/2 về xi=s.size-xi+1. Như vậy lúc này việc đảo chuỗi con sẽ bắt đầu từ lõi (x lớn nhất) sẽ đc đặt = 1 biến head
chúng ta sẽ tạo hàm con để swap 2 kí tự.
sử dụng đếm phân phối m[xi] để biết số lần xuất hiện của xi
Chúng ta sẽ xử lý từ vị trí head theo nguyên tắc:
4.1 nếu Q%2 là chẵn thì ta gán Q-=m[i] và bỏ qua
4.2 Nếu Q%2 là lẻ, ta đảo ngược xâu con từ i->j ( j gần nhất >i ) và gán Q-=m[i]
NOTE: Riêng với vị trí head đầu tiên chúng ta sẽ swap từ head->s.size/2
đây là code cho các bạn alt + f4 :> cứ tưởng x<s.size lúc đầu nên sai liên tục :))))
ví dụ
input: abc
1
3.
ouput: cba
phải không ạ!
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Bài này chill phết