Dãy xâu
Xem PDF
Điểm:
200 (p)
Thời gian:
1.0s
Bộ nhớ:
1023M
Input:
bàn phím
Output:
màn hình
Cho một dãy gồm \(n\) xâu \(s_1,s_2,…, s_n\) và một số nguyên dương \(k\). Một cặp hai xâu \(s_i\) và \(s_j\) trong dãy được gọi là tương thích với nhau nếu thỏa mãn:
- \(0 < j-i \le k\)
- Hai xâu \(s_i\) và \(s_j\) có cùng độ dài.
Yêu cầu: Hãy xác định số cặp các xâu tương thích với nhau trong dãy các xâu đã cho.
Input
- Dòng đầu chứa hai số nguyên \(n\) và \(k\) (\(3 \leq n \leq 3 \times 10^5; 1 \leq k \leq n\)).
- \(n\) dòng tiếp theo mỗi dòng chứa một xâu có độ dài từ 2 đến 20 kí tự gồm các chữ cái tiếng Anh in hoa.
Output
- Một dòng duy nhất là kết quả của bài toán.
Scoring
- Subtask #1 (\(40\%\) số điểm): \(n\leq 5000\)
- Subtask #2 (\(60\%\) số điểm): Không có ràng buộc gì thêm
Example
Test 1
Input
4 2
OTN
ABC
THA
HUNOutput
5Test 2
Input
6 3
CFETHIA
LLOYD
STEVIE
KEVIN
MALCABC
DABNEYOutput
2Nguồn: 2019 CBH-H.Nam
Bình luận
sol: https://ideone.com/hxvIAi
include<bits/stdc++.h>
using namespace std;
long long i,n,d;
string s;
int main (){
d=0;
cin>>s;
if(s[0]=='-')
s.erase(0,1);
while(s!=""){
s.erase(0,1);
d++;
}
cout<<d;
return 0;
}
Đếm phân phối + sliding window
Bài này cũng hay nè. Mình viết editorial sau nhé ^^