Đề bài:
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:
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. |
Speak Your Mind