LLQQDD - Tin hoc trẻ tỉnh Bắc Giang
Xem PDFTrường THPT Chuyên Lê Quý Đôn đang tổ chức một cuộc thi giải mã thu hút rất nhiều sự quan tâm của các bạn học sinh, đặc biệt là các bạn có đam mê với lập trình. Đề bài của vòng đầu tiên được ban tổ chức đưa ra như sau:
Ban đầu, hệ thống mã hoá sinh ra một xâu gồm \(3 \times k\) ký tự, đầu tiên là \(k\) ký tự L, tiếp theo là \(k\) ký tự Q và cuối cùng là \(k\) ký tự D. Sau đó, hệ thống sẽ thêm một số ký tự L, Q hoặc D vào những vị trí bất kỳ trong xâu cho đến khi xâu có độ dài \(n\). Sau đó, hệ thống sẽ cho người dùng biết \(n\), \(k\) và xâu sau khi đã biến đổi. Người giải mã cần chọn ra một xâu con gồm các ký tự liên tiếp và đếm số lượng ký tự cần xoá ít nhất để thu được xâu ban đầu mà hệ thống sinh ra. Nếu kết quả của người chơi trùng khớp với kết quả của hệ thống thì người đó sẽ được xem là hoàn thành vòng thi và nhận được tấm vé đến vòng tiếp theo.
Là một người đã có nhiều kinh nghiệm với lập trình, liệu bạn có thể giành được tấm vé này chứ?
Input
- Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) \((3 \leq n \leq 10^{7}, 1 \leq k \leq \lfloor \dfrac{n}{3} \rfloor)\).
- Dòng tiếp theo chứa một xâu độ dài \(n\) chỉ gồm các ký tự
L,QvàD.
Output
- Một dòng duy nhất chứa một số nguyên là kết quả của bạn. Trường hợp đặc biệt: nếu không thể chọn ra xâu con nào để thu được xâu ban đầu mà hệ thống sinh ra, bạn cần in ra
-1
Scoring
- Subtask \(1\) (\(20\%\) số điểm): \(n \leq 21\).
- Subtask \(2\) (\(30\%\) số điểm): \(n \leq 3 \times 10^{3}\).
- Subtask \(3\) (\(30\%\) số điểm): \(n \leq 2 \times 10^{5}\).
- Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.
Example
Input
10 2
LLDLQDQDDLOutput
2Note
Chọn xâu con LDLQDQDD, bỏ ký tự thứ \(2\) và \(5\) tính từ trái qua sẽ thu được xâu LLQQDD là xâu ban đầu mà hệ thống sinh ra.
Bình luận
help
include<bits/stdc++.h>
using namespace std;
define ll long long
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,k;string s;
cin>>n>>k>>s;
s=' '+s+' ';
int d[n+5]={0},l[n+5]={0},q[n+5]={0};
for (int i=1;i<=n;i++){
l[i]=l[i-1];
d[i]=d[i-1];
q[i]=q[i-1];
if (s[i]=='L') l[i]++;
else if (s[i]=='Q') q[i]++;
else d[i]++;
}
int el=1,eq=1,ed=1,ans=1e9;
for (int i=1;i<=n;i++){
while(l[el]-l[i-1]<k){
el++;
if (el==n+1) break;
}
eq=max(eq,el);
while(q[eq]-q[el-1]<k) {
eq++;
if (eq==n+1) break;
}
ed=max(eq,ed);
while(d[ed]-d[eq-1]<k) {
ed++;
if (ed==n+1) break;
}
if (ed==n+1||eq==n+1||el==n+1) break;
ans=min(max({el,eq,ed})-i-3*k+1,ans);
}
if (ans==1e9) cout<<-1;
else cout<<ans;
}
code c++
Bài này làm như thế nào vậy ạ