Đề 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
Speak Your Mind