Đề bài:

• http://vn.spoj.com/problems/C11STAR/

Thuật toán:

+ 20% test đầu với m, n ≤100:

– Với dữ liệu nhỏ như thế này ta có thể làm cách thô thiển là duyệt tất cả hình thỏa mãn là ngôi sao rồi tăng kết quả lên.

– Độ phức tạp: O((m*n)^2)

+ 30% test tiếp theo có m≤600, n ≤150:  

– Ở đây ta có thể tiếp cận bài toán theo hướng khác: đếm hình chữ nhật xiên 45 độ.

– Giờ ta nghĩ đến phương pháp quay sao cho quy bài toán về đếm hình chữ nhật, để ý là các ô thuộc cùng đường chéo thì có tổng X=i+j và hiệu Y=i-j giống nhau, từ đó ta có 1 phép biến đổi:

+ biến ô (i,j) thành ô (i+j,i-j) trong bảng mới.

Bây giờ ta có 1 bảng mới với kích thước (m+n)*(m+n) :

+ Gọi f[i][j][‘char’] là số cặp ký tự ‘char’ trong 2 cột i và j.

+ Duyệt O((m+n)^3) để tính mảng f, sau đó dùng O((m+n)^2) để cập nhật kết quả

→ kết quả là Sum(f[i][j][‘char’]*(f[i][j][‘char’]-1)/2);

+ Để ý là các ô có (i+j) mod 2=0. và (i+j) mod 2=1 không liên quan tới nhau, do đó ta có thể đưa về 2 bảng để giảm độ phức tạp 1 tý để ăn được subtask này.

– Độ phức tạp O((m+n)^3)

+ 50% test cuối có m≤3000, n ≤200:

– Ta có các nhận xét sau:

+ Bảng có tối đa (m+n) đường chéo

+ Hình ngôi sao to nhất cũng chỉ nằm trong phạm vi min(m,n)^2

Từ đó ta có cách giải:

+ Gọi f[i][j][‘char’] số cặp ký tự ‘char’ nằm trên 2 đường chéo i và j.

+ Duyệt m*n ô của bảng

+ Với mỗi ô ta duyệt min(m,n) ô cùng đường chéo với nó trở lên, nếu cùng ký tự:

→ tăng kết quả lên f[i][j][‘char’]

→ cập nhật f[i][j][‘char’]=f[i][j][‘char’]+1

– Độ phức tạp O(m*n*min(m,n))

Code:

• xem code trên ideone

const   fi      ='';
        fo      ='';
        maxM    =3000;
        maxN    =200;
 
var     f       :array['a'..'z',1..maxM+maxN,1..maxM+maxN] of integer;
        m, n    :longint;
        a       :array[0..maxM,0..maxN] of char;
 
procedure Optimize;
var     i, j,i1,j1    :longint;
        ans     :longint;
begin
        fillchar(f,sizeof(f),0);
        ans:=0;
        for i:=1 to m do
                for j:=1 to n do
                        if a[i,j]<>'.' then
                                begin
                                        i1:=i;j1:=j;
                                        while (i1<m) and (j1<n) do
                                                begin
                                                        inc(i1);inc(j1);
                                                        if a[i1,j1]=a[i,j] then
                                                                begin
                                                                        ans:=ans+f[a[i,j],i+j,i1+j1];
                                                                        inc(f[a[i,j],i+j,i1+j1]);
                                                                end;
                                                end;
                                end;
        writeln(ans);
end;
 
procedure run;
var     i, j    :longint;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(m, n);
        for i:=1 to m do
                begin
                for j:=1 to n do read(a[i,j]);
                readln;
                end;
        Optimize;
        close(input);close(output);
end;
 
begin
        run;
end.

Đề bài:

• http://vn.spoj.com/problems/DIFFSTR/

Thuật toán:

Solution ăn 60%:

Xét xâu S và dãy x[1..n] thỏa mãn 1 <= x[i] <= length(S) và x[i] > x[i – 1]. Với mỗi dãy x, ta thu được 1 xâu con của S: S[x[1]] S[x[2]] S[x[3]]… S[x[n]]

Để tạo ra được các xâu con phân biệt của S mà 2 phần tử liền kề khác nhau, ta chỉ xét đến những dãy x thỏa mãn điều kiện sau:

1. S[x[i]] != S[x[i – 1]]
2. Không tồn tại số k thỏa mãn x[i] < k < x[i + 1] và S[k] == S[x[i + 1]] (nói nôm na là nếu chọn ký tự ch nào đó để cho vào xâu con thì luôn chọn ký tự có chỉ số nhỏ nhất)

(cái đoạn in nghiêng này hình như không cần thiết :)))

 Gọi g[i][j] là số cách chọn dãy x[] có i phần tử mà x[i] = j.

 g[i][j] sẽ cập nhật cho g[i + 1][k] mà k là những giá trị mà khi thêm x[i + 1] = k thì vẫn đảm bảo điều kiện của dãy x[] ở trên (nhận xét là sẽ có không quá 26 giá trị của k)

g[i + 1][k] += g[i][j]

Cuối cùng, để tính kết quả bài toán:

Gọi:

• f[i][j][0] là số cách chọn dãy x[] có i phần tử mà x[i] = j và dãy x này tạo ra 1 xâu con bằng với xâu b[1..i]
• f[i][j][1] là số cách chọn dãy x[] có i phần tử mà x[i] = j và dãy x này tạo ra 1 xâu con lớn hơn xâu b

Với mỗi f[i][j][t], tìm các giá trị k thỏa mãn thêm x[i + 1] = k vẫn đảm bảo thỏa mãn điều kiện của x[]:

– Nếu t = 1 thì f[i + 1][k][1] += f[i][j]

– Nếu t = 0, S[x[k]] = b[i + 1] thì f[i + 1][k][0] += f[i][j]

– Nếu t = 0, S[x[k]] > b[i + 1] thì f[i + 1][k][1] += f[i][j]

– Nếu t = 0, S[x[k]] < b[i + 1] thì không làm gì hết

Kết quả bài toán = tổng f[i][j][1] + tổng f[length(b)][j][0]

Đpt ít hơn O(n * n * log(n)) n * n là mảng f, log(n) để tìm k, thực chất là không cần tính hết mảng f nên đpt sẽ nhỏ hơn khá nhiều

Solution ăn 100%:

QHĐ tương tự như trên, ta có thể tính được số xâu con của S[i..n] bắt đầu bằng ký tự ch bất kỳ mà thỏa mãn 2 ký tự liền kề khác nhau trong O(1)

Duyệt i từ đầu đến cuối xâu b, đến bước thứ i, đếm số xâu con trong S có dạng b[1..i – 1] + x với x là 1 xâu < S[i..m]. Số lượng xâu x = (số xâu con trong S[k..n] (k là vị trí kết thúc đầu tiên của xâu con b[1..i – 1] trong xâu S) bắt đầu bằng các ký tự < b[i]) + 1 (xâu rỗng)

Kết quả bài toán là tổng của các xâu trên – 1 (xâu rỗng)

Lưu ý là trong khi duyệt, nếu xâu b[1..i] không thỏa mãn điều kiện  2 ký tự liền kề khác nhau thì phải dừng duyệt ngay lập tức.

Solution O(N): của anh Nguyễn Tấn Sỹ Nguyên ( flash_mt )

Gọi F[i] là số cách chọn 1 subsequence ko có 2 phần tử kề nhau bằng nhau với S[i] là phần tử đầu tiên. Có thể tính F[] trong O(26N).

Sau đó ta đếm số lượng subsequence A thỏa A[1..k] = B[1..k] và A[k + 1] > B[k + 1]. Với mỗi giá trị k, xét A[k + 1] = c với c > B[k + 1], tìm vị trí u đầu tiên trong đoạn còn lại thỏa S[u] = c và tăng kết quả lên f[u]. Độ phức tạp của bước này là O(26(M + N)).

Code:

• (đang cập nhập)