Complete The Word - Codeforces 716B (Div. 2)

Đề 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 hiện đúng 1 lần. Nhiệm vụ của bạn là tìm xem có cách nào điền chữ cái ‘A’->’Z’ vào dấu ? trong xâu ban đầu để xâu đó tồn tại một xâu con là xâu đẹp hay không?

Nếu có hãy in ra một xâu bất kì. nếu không tồn tại ghi ra -1.

Input

Gồm 1 dòng duy nhất là xâu ban đầu

Output

Ghi ra xâu con thỏa mãn hoặc -1 nếu ko tồn tại

Examples

input

ABC??FGHIJK???OPQR?TUVWXY?

1	ABC??FGHIJK???OPQR?TUVWXY?

output

ABCDEFGHIJKLMNOPQRZTUVWXYS

1	ABCDEFGHIJKLMNOPQRZTUVWXYS

input

WELCOMETOCODEFORCESROUNDTHREEHUNDREDANDSEVENTYTWO

1	WELCOMETOCODEFORCESROUNDTHREEHUNDREDANDSEVENTYTWO

output

-1

-1

input

??????????????????????????

1	??????????????????????????

output

MNBVCXZLKJHGFDSAQPWOEIRUYT

1	MNBVCXZLKJHGFDSAQPWOEIRUYT

input

AABCDEFGHIJKLMNOPQRSTUVW??M

1	AABCDEFGHIJKLMNOPQRSTUVW??M

output

-1

-1

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;
}

#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;

}

Complete The Word – Codeforces 716B (Div. 2)

1. Đề bài Codeforces 716B

Input

Output

Examples

2. Ý tưởng giải quyết

3. Code Codeforces 716B

Bài viết liên quan

Trả lời Hủy