02/10/2018, 14:28
Complete The Word – Codeforces 716B (Div. 2)
1. Đề bài Codeforces 716B Đề bài cho bạn 1 xâu có độ dài <= 50000 kí tự, bao gồm ‘A’->’Z’ và dấu ‘?’. Người ta định nghĩa 1 xâu đẹp là xâu có 26 kí tự, các kí tự bao gồm ‘A’->’Z’ và mỗi chữ cái chỉ xuất ...
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
#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;
}
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; } |
