P145PROI - ROUND 5I - Mật khẩu

Link Sub: http://www.spoj.com/PTIT/problems/P145PROI/
Người Gửi: Dương Lee

• Problem:

Một xâu ký tự được gọi là mật khẩu “an toàn” nếu xâu có độ dài ít nhất bằng 6 và xâu chứa ít nhất một chữ cái in hoa , một chữ cái thường , một chữ số .  
Ví dụ, ‘a1B2C3’, ‘tinHoc6’ là hai mật khẩu “an toàn”. Còn ‘a1B2C’, ’a1b2c3’, ‘A1B2C3’, ‘tinHoc’ đều không phải là mật khẩu “an toàn”.
Một lần, Tí nhìn thấy một xâu S, chỉ gồm các loại ký tự: chữ cái in hoa, chữ cái thường và chữ số. Tí muốn tự kiểm tra khả năng đoán nhận mật khẩu bằng cách đếm xem có bao nhiêu cặp chỉ số (i, j) thỏa mãn điều kiện:  1 ≤ i < j ≤ length(S) và xâu con gồm các ký tự liên tiếp từ i đến j của S là mật khẩu “an toàn”.  
Cho xâu S, các hãy tính số lượng cặp chỉ số (i, j) thỏa mãn điều kiện nêu trên.
Input
Một dòng chứa xâu S có độ dài <= 10^6.

Output
In ra một số nguyên duy nhất là số cặp chỉ số (i, j) tìm được.

Example:

Input

abc3456789PQ

Output:

6

Input

abc123

Output:

0

• Solution:

- Quy hoạch xâu: Xây dựng mảng pass mà: + Với mỗi một vị trí xác định xem từ đầu xâu cho đến nó có bao nhiêu kí tự số, có bao nhiêu chữ thường, chữ hoa. - Tìm kiếm nhị phân: + Tại mỗi vị trí trên xâu, tìm vị trí gần nhất (VT) mà tại đó mật khẩu an toàn (check_safe) trên mảng pass mới quy hoạch. - Tính toán: + Với mỗi vị trí tìm thấy thì số lượng mật khẩu an toàn tạo được sẽ là +=(n-VT+1) (Vì khi mật khẩu đã an toàn rồi thì thêm bất kì kí tự nào nó vẫn an toàn :v) Độ phức tạp O(NlogN).

• Code:

C++:

https://ideone.com/LmEflP

#include <iostream>
#include <string>
using namespace std;

struct data
{
    int hv_1;
    int hv_A;
    int hv_a;
} typedef data;

data pass[1000006];

int check_safe (int begin, int end)
{
    int num_1=pass[end].hv_1-pass[begin-1].hv_1;
    int num_a=pass[end].hv_a-pass[begin-1].hv_a;
    int num_A=pass[end].hv_A-pass[begin-1].hv_A;
    if (num_1>0 && num_a>0 && num_A>0 && end-begin+1>=6) return 1;
    else return 0;
}

int BSearch (int begin, int front, int back)
{
    int vt=-1;
    while (front<=back && back-begin+1>=6)
    {
        int mid = (front+back)/2;
        if (check_safe (begin, mid)==1)
        {
            vt=mid;
            back=mid-1; 
        }
        else front=mid+1;
    }
    return vt;
}

int main ()
{
    string xau;
    cin>>xau;
    pass[0].hv_1=0;
    pass[0].hv_a=0;
    pass[0].hv_A=0;
    int n=xau.length();
    for (int i=1; i<=n; i++)
    {
        if (xau[i-1]>='0' && xau[i-1]<='9')
        {
            pass[i] = pass[i-1];
            pass[i].hv_1++; 
        }
        else if (xau[i-1]>='a' && xau[i-1]<='z')
        {
            pass[i] = pass[i-1];
            pass[i].hv_a++;
        }
        else if (xau[i-1]>='A' && xau[i-1]<='Z')
        {
            pass[i] = pass[i-1];
            pass[i].hv_A++;
        }
    }
    long long count=0;
    for (int i=1; i<=xau.length()-6+1; i++)
    {
        int VT = BSearch (i, i, n);
        if (VT!=-1)
        {
            count+=n-VT+1;
        } else break;
    }
    cout<<count;
    return 0;
}

JAVA:

Author : DL

Share this

Related Posts