2. Ý tưởng giải quyết
- Đầu tiên bạn tạo mảng 1 chiều lưu lại số lần xuất hiện của kí tự trong xâu con a[0]->a[25]
- sau đó bạn đếm xem có bao nhiêu chữ cái trong đó xuất hiện trên 1 lần. (đặt tên là biến dem)
- sau đó bạn dựa vào dem để tính, và xác định xem đoạn con đó có khả năng là xâu con đẹp ko? nếu không thì bạn cứ tịnh tiến cái phạm vi thống kê số lần xuất hiện dần hết xâu a đồng thời cập nhật biến dem, nếu chỗ nào thỏa mãn (dem==0) thì bạn xử lí thôi.
Nhận xét: nếu độ dài xâu a < 26 -> không tồn tại
Độ phức tạp O(|s|)
3. Code Codeforces 716B
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | #include <stdio.h> #include <iostream> #include <string.h> using namespace std; char a[50001]; long dd[50001],leng; void xuli() { long i,j,dem=0; //init for (i=0; i<=25; i++) dd[i]=0; //exit if (leng<26) { cout << "-1"<<endl; return; } // tinh trc for (i=0; i<=25; i++) if (a[i]!='?') dd[a[i]-65]++; //update dem for (i=0; i<=25; i++) if (dd[i]>1) dem++; for (i=0; i<=leng-26; i++) { if ( (a[i-1]!='?') && (i!=0)) { if (dd[a[i-1]-65]==2) dem--; dd[a[i-1]-65]--; } if ( (a[i+25]!='?') && (i!=0)) { if (dd[a[i+25]-65]==1) dem++; dd[a[i+25]-65]++; } if (dem==0) { long k=0; for (j=0; j<=i-1; j++) if (a[j]!='?') cout <<a[j]; else cout << "A"; for (j=i; j<=i+25; j++) if (a[j]!='?') cout <<a[j]; else { while (dd[k]>0) k++; cout << (char)(k+65); k++; } for (j=i+25+1; j<=leng-1; j++) if (a[j]!='?') cout <<a[j]; else cout <<"A"; cout << endl; return; } } cout << "-1"<<endl; } int main() { cin>>a; leng=strlen(a); xuli(); return 0; } |
Bài viết liên quan
- A. Two Substrings – Codeforces 306 (Div. 2)
- P146SUMF spoj PTIT – Dãy số kì diệu
- Giải đề thi Lập trình hướng đối tượng UIT – Đề HK2 2016-2017
- [UpCoder] LOGIN_UP2 – Xác nhận Upcoder 2
- Phân tích một số bài tập Nhập môn lập trình C++
- [C++] Đọc số thành chữ – hàng triệu
- Spoj PTIT PTIT016C – ACM PTIT 2016 C – Chẵn lẻ
- P167PROD spoj PTIT – ROUND 7D – ABC
- NKH spoj – Tách Từ
- P156SUME spoj PTIT – ROUND 6E – Ước chung của chuỗi