1. Đề bài MTHCN spoj
bạn có thể submit tại:
http://www.spoj.com/THPTCBT/problems/MTHCN/
http://vn.spoj.com/problems/MTHCN/
Trong giờ học toán, Miticc cảm thấy rất chán nản với môn hình học,… Anh ta quyết định buông viết và làm 1 giấc, trong mơ Miticc đã gặp một chú bò, anh ta đã được chú bò giới thiệu một trò chơi hết sức thú vị.
Đầu tiên chú bò sẽ cho anh ta một bảng hình vuông có kích thước N*N ô, nhiệm vụ của Miticc là phải tính được diện tích của hình chữ nhật lớn nhất được tạo bởi các ô có phần tử là một số chính phương hoặc số đó là lập phương của một số nguyên tố.
Nhiệm vụ của Miticc là không quá khó khăn, và tất nhiên là anh ta làm được, trong lúc đang giải trò chơi của chú bò đưa ra, anh ta bị lũ bạn kế bên ghẹo phá, :’( chúng chụp hình dìm và đánh thức anh dậy, hù dọa sẽ đăng hình anh lên facebook :’( Anh ta rất bực bội vì đã bị lũ bạn trêu ghẹo, thêm vào đó là chưa kịp trả lời trò chơi của chú bò :’( Anh ta ấm ức rất nhiều.
Nhiệm vụ của bạn là hãy giúp anh ta giải trò chơi mà chú bò đưa ra, thật may mắn là anh ta vẫn còn chút kí ức về cái bảng mà chú bò đã đưa, Nhưng… chuyện không như là mơ… anh ta chỉ còn nhớ ở dòng thứ x nào đó trong bảng hình vuông sẽ tăng từ cột u đến cột v, k đơn vị. Và tất nhiên đầu tiên chiếc bảng phải bằng 0.
Bạn hãy giúp Miticc giải ra bài toán nhé.
Input
– dòng đầu tiên gồm 2 số N và M (N là kích thước ma trận hình vuông, M là số lượng truy vấn mà Miticc sẽ nói cho bạn biết). (N<=1000; M<=50000).
– M dòng tiếp theo là truy vấn có dạng Q(x,u,v,k); (0<=K<=50000);
Với mỗi truy vấn có dạng Q(x,u,v,k) ta tăng k đơn vị cho các phần tử từ vị trí u đến vị trí v trên dòng x.
Lưu ý: test luôn đảm bảo mỗi phần tử trong bảng không vượt quá 2^32.
Output
– Gồm một dòng duy nhất là kết quả bài toán.
Example
Input:
5 8
1 1 2 27
2 2 5 3
3 1 5 1
4 1 5 1
4 2 3 4912
4 5 5 9
5 1 4 1
5 1 1 1
Output:
9
giải thích:
2. Hướng dẫn thuât toán
bài này dựa trên bài BLGEN và QBRECT, hai bài của kỳ thi olympic 30/4/2014
– QHĐ + Sàng nguyên tố + chặt nhị phân + Stack
Hướng dẫn:
thời gian giới hạn của bài làm là khá nhỏ (0.009s-0.090s) vì vậy ở phần truy vấn mình không thể duyệt những dòng for được, mà phải sử dụng QHD.
– Một kiến thức mới: Để tăng k đơn vị từ vị trí u đến vị trí v, ở mỗi truy vấn mình chỉ cần thực hiện: A[u]:=a[u]+k; và a[v+1]:=a[v+1]-k; sau khi thực hiện xong Q truy vấn mình chỉ cần duyệt i từ 1 -> n: A[i]:=a[i-1]+a[i]; và trong bài toán này, bạn phải biết cách điều chỉnh cho mảng 2 chiều.
– bước tiếp theo sàng nguyên tố, với mỗi số nguyên tố tìm được, mình sẽ lập phương nó lên và bỏ vào một mảng nào đó. việc còn lại là viết hàm tìm kiếm nhị phân, để kiểm tra.
– Lọc các số trong mảng theo điều kiện đề bài, nếu thỏa thì cho a[i,j]=1 ngược lại a[i,j]=0.
– Bài toán đưa về vấn đề tìm hình chữ nhật lớn nhất, có thể sử dụng Stack giống QBRECT.
3. Code pascal tham khảo
const fi='';
fo='';
nmax=1000;
maxsang=997;
type data=longint;
var
f:text;
A:array[0..nmax+1,0..nmax+1] of longint;
n,m:data;
D,S,L,R:array[1..1000*1000] of longint;
ns:data;
dd:array[0..maxsang] of boolean;
spt:data;
snt:array[1..168] of data;
Ans:data;
function chinhphuong(x:data):boolean;
begin
exit(sqr(trunc(sqrt(x)))=x);
end;
function TKNP(x:data):boolean;
var l,r,mid:longint;
begin
l:=1;
r:=spt;
while l<=r do
begin
mid:=(l+r) div 2;
if snt[mid]=x then
exit(true)
else
if snt[mid]>x then
r:=mid-1
else
l:=mid +1;
end;
exit(false);
end;
procedure sangNT;
var i,j:data;
begin
fillchar(dd,sizeof(dd),true);
dd[1]:=false;
i:=2;
while i<=trunc(sqrt(maxsang)) do
begin
while not dd[i] do
inc(i);
for j:=2 to maxsang div i do
dd[i*j]:=false;
inc(i);
end;
spt:=0;
for i:=2 to maxsang do
if dd[i] then
begin
inc(spt);
SNT[spt]:=i*i*i;
end;
end;
procedure xuli;
var i,j,dientich:data;
begin
fillchar(d,sizeof(d),0);
for i:=1 to n do
begin
for j:=1 to n do
if a[i,j]<>1 then
d[j]:=i;
ns:=0; // ns la spt cua stack S;
for j:=1 to n do
begin
while (ns>0) and (d[s[ns]]<=d[j]) do
dec(ns);
if ns=0 then
L[j]:=0
else
L[j]:=s[ns]; // l]j] la bien trai
inc(ns); s[ns]:=j;
end;
ns:=0;
for j:=n downto 1 do
begin
while (ns>0) and (d[s[ns]]<=d[j]) do
dec(ns);
if ns=0 then
R[j]:=n+1
else
R[j]:=s[ns]; // r[j] la bien phai;
inc(ns); s[ns]:=j;
end;
for j:=1 to n do
begin
dientich:=(i-d[j])*(R[j]-L[j]-1);
if ans<dientich then
ans:=dientich;
end;
end;
assign(f,fo); rewrite(f);
writeln(f,ans);
close(f);
end;
procedure docfile;
var i,j,u,v,x:data;
k:data;
begin
assign(f,fi); reset(f);
readln(f,n,m);
for i:=0 to n+1 do
for j:=0 to n+1 do
A[i,j]:=0;
for i:=1 to m do
begin
readln(f,x,u,v,k);
A[x,u]:=a[x,u]+k;
A[x,v+1]:=a[x,v+1]-k;
end;
for i:=1 to n do
for j:=1 to n do
A[i,j]:=a[i,j-1]+a[i,j];
for i:=1 to n do
for j:=1 to n do
if chinhphuong(a[i,j]) or tknp(a[i,j]) then
A[i,j]:=1
else
A[i,j]:=0;
close(f);
end;
begin
sangnt;
docfile;
xuli;
end.
