BITMARKS:
(BIT MANIPULATION)
Xử lí bit là 1 pp rất hữu hiệu để giải quyết các bài toán tối ưu về không gian rất tốt, đồng thời cũng giải quyết dc vấn đề về thởi gian của chương trình khi thưc hiện
Bit được lưu trong 1 kiểu số nguyên, ví dụ như là byte (8 bit), integer(16 bit), longint(32 bit), và kiểu int64(64 bit)
Trong đó, (n - 1) bit đầu là những bit dương, bit cuối cùng là bit để biểu thị mối quan hệ âm dương
Các phép toán trên bit :
AND : 156 AND 235 = 136
OR : 156 OR 235 = 255
XOR : 156 XOR 235 = 119
NOT : NOT 156 = -157
Note 1 : quan sát thì ta thấy dc khi not 1 số x, thì ta dc số đối của số đó - 1, cho nên tha vì gán x = -x, ta có thể gán NOT (x - 1)
Note 2 : khi xor 1 số, nếu tần xuất xor 1 số là lẻ thì luôn ra chính nó : a xor a xor a = a
Note 3 : ta cần pp biệt 1 vấn đề đó là vị trí của bit và thứ tự của bit :
Bit thứ 8 có :
Vị trí của bit : 0,1,2,3,4,5,6,7
Thứ tự của bit : 1,2,3,4,5,6,7,8
Qua ví dụ cho thấy bit cuối cùng của vị trí bit là 7 chứ hok là 8 như thứ tự bit. Trong toán học cũng như lập luận của đa phần sách, bit đầu tiên luôn đánh dấu là 0 chứ không phải là 1, việc chọn 1 chỉ là cách hiểu để dễ dàng diễn giải trong các thuật toán
Để dễ dàng thể hiện tính đúng đắn cũng như thói quen dùng của nhiều người, tài liệu này sẽ biểu thị bit được biểu diễn bằng vị trí của bit :D
Phép dịch chuyển bit trái, phải :
Ta có phép shl (phép dịch chuyển sang trái) và phép shr (phép dịch chuyển sang phải) :
Ví dụ : 12 shl 1 = 24
12 shr 1 = 6
ngoài ra, 1 tính chất quan trọng là shl = *2k , shr = div 2k
shl k, shr k có thể viết thành << k, >> k
tính chất quan trọng của phép toán này là tất cả các phép toán về bit đều tập trung vào tính chất của phép dịch chuyển bit này :D
Thao tác trên bit :
xem bit thứ k của bit x: vitri = (x shr k) and 1
gán bit c vào vị trí k của bit x :
if c = 1 then x = x or (x shr k)
else x = x and (not (x shr k))
phép chuyển bit : x xor (1 shl k)
note : ngoài ra còn có:
phép bật, tắt bit : bật bit là gán bit = 1, tắt bit là gán bit = 0
để thuận tiện cho việc mở/ tắt bit ta dùng 1 mãng hằng để lưu giá trị
bitcost = array[0..63] = (1,2,4,8,16,…)
debug :
Để check lại 1 cách nhanh chóng và hiệu quả, ta thường viết 1 function chuyển từ cơ số 10 ra cơ số 2
LTPMSEQ vn.spoj.pl/problems/LTPMSEQ
CHESSCBG vn.spoj.pl/problems/CHESSCBG
LEM2 vn.spoj.pl/problems/LEM2
NTSHEEP vn.spoj.pl/problems/NTSHEEP
GIRD :
Gird là 1 pp vét mảng
Gird là 1 p, kĩ năng khá quan trong các bài toán vét cơ bản và cũng như là những bài toán tối ưu phức tạp (phụ thuộc vào cách cài đặt đúng dắn và hiệu quả)
Thao tác này thực hiện trực tiếp trên mảng
Ta có các thao tác cơ bản sau đây :
Tính tổng của mảng 1 chiều : a[i]
S[0] := 0;
For I := 1 to n do s[i] := s[I – 1] + a[i];
// ghi tổng từ I = 2 j = 7
I := 2;j := 7;
Res := s[j] – s[I – 1];
Note :
Với tính chất trên, ta còn có 1 cách tăng 1 dãy (i…j) thêm k giá trị :
S[i] := s[i] + k;s[j + 1] := s[j + 1] – k;
sau khi hoàn thành tất cả các thao tác trên, ta phải :
for I := 1 to n do s[i] := s[I – 1] + s[I];
lưu ý rất lớn là s[] mảng dc gán gái trị ban đầu là 0.
Tính tổng trên mảng 2 chiều : f[m,n]
For j := 2 to n do f[1,j] := f[1,j] + f[1,j – 1]
For I := 2 to m do
Begin
For j := 1 to n do f[I,j] := f[I,j] + f[I,j - 1];
For j := 1 to n do f[I,j] := f[I,j] + f[I – 1,j];
End;
// ghi tổng từ [d1,c1] cho tới [d2,c2]:
Res := f[d2,c2] – f[d2,c1 – 1] – f[d1 – 1,c2] + f[d1 – 1,c1 – 1]
Phép chuyển mảng :
Chuyển từ mảng 1 chiều thành 2 chiều : a[k] thành b[I,j] // (c,d)
I := (k - 1) div c + 1;
If k mod c = 0 then j := c else j := k mod c;
B[I,j] := a[i];
Chuyển từ mảng 2 chiều thành 1 chiều : b[I,j] (d,c) thành a[k]
k := (I - 1) * c + j;
a[k] := b[I,j];
chuyển từ mảng 3 chiều thành 1 chiều : a[I,j,k] (ii,jj,kk) thành a[h]
h := (I - 1)*jj*kk + (j - 1)*kk + k;
a[h] := b[I,j,k];
chuyển từ mảng 1 chiều thành 3 chiều : a[h] thành a[I,j,k] (ii,jj,kk)
I := (h - 1) div (jj*kk) + 1;
C := (I - 1)*jj*kk;
J := (h - 1 – c) div kk + 1;
If (h - c) mod kk = 0 then k := kk else k := (h - c) mod kk;
Pp nén mảng :
khi phần tử liên tiếp của mảng trùng nhau 1 giá trị , ta có thể nén các gía trị ấy trong 1 mảng b[]
Nếu có 256 phần tử cùng có 1 gía trị là k thì :
If (n mod 256 = 0) then b[n div 256] := k;
Problem :
CVJETICI – [You must be registered and logged in to see this link.] (dùng pp nén mảng)
FORWARD STAR :
CTDL dạng này chủ yếu lưu giá trị của các cặp phân tử liên hệ lẫn nhau như là đồ thị
Mối liên hệ càng ít thì bộ nhớ sử dụng càng ít
Tuy nhiên để truy xét 1 cặp đối ngẫu bất kì thì ta phải duyệt hết tất cả các giá trị só thể có
Dạng này có thể cài dưới dạng con trỏ
STACK + QUEUE :
Stack : hoạt động theo cơ chế FILO
Queue : hoạt động theo cơ chế FIFO
Ngoài ra, 1 số cơ chế quan trọng có thể nói như sau :
deque - Double Ended Queue : là 1 pp kết hợp giữa stack và queue
Piority queue : cài đặt dựa trên dang sách vòng
Piority stack : đây là 1 pp khá hay, áp dụng khá nhiều trong nhiều bài tập khó và sáng tạo, và đây cũng là 1 dạng bài tập về pp CLDL phải hiểu rõ bản chất.
pp:
1 trong cách phổ biến là dùng biến left[] và right[] để cập nhật vị trí cưc trái và cực đại
left[] và right[] dc cập nhật bằng cách :
left[i] := left[left[i] – 1]
right[i] := right[right[i] +1]
note :
pp dc nêu trên chủ yếu làm trong phần init, thực hiện trong vòng lặp.
áp dụng tốt cho dạng bài tìm cực của pt mảng (vd : bài KAGAIN)
Problem :
MINK [You must be registered and logged in to see this link.] (dùng DEQUE – nhớ cập nhật biến front sau khi writeln ra vị trí nhỏ nhất)
KAGAIN [You must be registered and logged in to see this link.] (dùng piority stack)
CHEAT [You must be registered and logged in to see this link.]
TTRAVEL [You must be registered and logged in to see this link.]
(BIT MANIPULATION)
Xử lí bit là 1 pp rất hữu hiệu để giải quyết các bài toán tối ưu về không gian rất tốt, đồng thời cũng giải quyết dc vấn đề về thởi gian của chương trình khi thưc hiện
Bit được lưu trong 1 kiểu số nguyên, ví dụ như là byte (8 bit), integer(16 bit), longint(32 bit), và kiểu int64(64 bit)
Trong đó, (n - 1) bit đầu là những bit dương, bit cuối cùng là bit để biểu thị mối quan hệ âm dương
Các phép toán trên bit :
AND : 156 AND 235 = 136
OR : 156 OR 235 = 255
XOR : 156 XOR 235 = 119
NOT : NOT 156 = -157
Note 1 : quan sát thì ta thấy dc khi not 1 số x, thì ta dc số đối của số đó - 1, cho nên tha vì gán x = -x, ta có thể gán NOT (x - 1)
Note 2 : khi xor 1 số, nếu tần xuất xor 1 số là lẻ thì luôn ra chính nó : a xor a xor a = a
Note 3 : ta cần pp biệt 1 vấn đề đó là vị trí của bit và thứ tự của bit :
Bit thứ 8 có :
Vị trí của bit : 0,1,2,3,4,5,6,7
Thứ tự của bit : 1,2,3,4,5,6,7,8
Qua ví dụ cho thấy bit cuối cùng của vị trí bit là 7 chứ hok là 8 như thứ tự bit. Trong toán học cũng như lập luận của đa phần sách, bit đầu tiên luôn đánh dấu là 0 chứ không phải là 1, việc chọn 1 chỉ là cách hiểu để dễ dàng diễn giải trong các thuật toán
Để dễ dàng thể hiện tính đúng đắn cũng như thói quen dùng của nhiều người, tài liệu này sẽ biểu thị bit được biểu diễn bằng vị trí của bit :D
Phép dịch chuyển bit trái, phải :
Ta có phép shl (phép dịch chuyển sang trái) và phép shr (phép dịch chuyển sang phải) :
Ví dụ : 12 shl 1 = 24
12 shr 1 = 6
ngoài ra, 1 tính chất quan trọng là shl = *2k , shr = div 2k
shl k, shr k có thể viết thành << k, >> k
tính chất quan trọng của phép toán này là tất cả các phép toán về bit đều tập trung vào tính chất của phép dịch chuyển bit này :D
Thao tác trên bit :
xem bit thứ k của bit x: vitri = (x shr k) and 1
gán bit c vào vị trí k của bit x :
if c = 1 then x = x or (x shr k)
else x = x and (not (x shr k))
phép chuyển bit : x xor (1 shl k)
note : ngoài ra còn có:
phép bật, tắt bit : bật bit là gán bit = 1, tắt bit là gán bit = 0
để thuận tiện cho việc mở/ tắt bit ta dùng 1 mãng hằng để lưu giá trị
bitcost = array[0..63] = (1,2,4,8,16,…)
debug :
Để check lại 1 cách nhanh chóng và hiệu quả, ta thường viết 1 function chuyển từ cơ số 10 ra cơ số 2
- Code:
function coso2(i : integer) : string;
var s : string;
begin
s := '';
if i = 0 then s := '0' else
repeat
if i mod 2 = 0 then s := '0' + s else s := '1' + s;
i := i div 2;
until i = 0;
coso2 := s;
end;
ứng dụng :
xử lí bit được dùng nhiều nhất trong cái bài toán về xử lí trạng thái, lớp bài toán quy hoạch động về trạng thái
dùng làm CTDL cho các bài toán tối ưu mảng :D
LTPMSEQ vn.spoj.pl/problems/LTPMSEQ
CHESSCBG vn.spoj.pl/problems/CHESSCBG
LEM2 vn.spoj.pl/problems/LEM2
NTSHEEP vn.spoj.pl/problems/NTSHEEP
GIRD :
Gird là 1 pp vét mảng
Gird là 1 p, kĩ năng khá quan trong các bài toán vét cơ bản và cũng như là những bài toán tối ưu phức tạp (phụ thuộc vào cách cài đặt đúng dắn và hiệu quả)
Thao tác này thực hiện trực tiếp trên mảng
Ta có các thao tác cơ bản sau đây :
Tính tổng của mảng 1 chiều : a[i]
S[0] := 0;
For I := 1 to n do s[i] := s[I – 1] + a[i];
// ghi tổng từ I = 2 j = 7
I := 2;j := 7;
Res := s[j] – s[I – 1];
Note :
Với tính chất trên, ta còn có 1 cách tăng 1 dãy (i…j) thêm k giá trị :
S[i] := s[i] + k;s[j + 1] := s[j + 1] – k;
sau khi hoàn thành tất cả các thao tác trên, ta phải :
for I := 1 to n do s[i] := s[I – 1] + s[I];
lưu ý rất lớn là s[] mảng dc gán gái trị ban đầu là 0.
Tính tổng trên mảng 2 chiều : f[m,n]
For j := 2 to n do f[1,j] := f[1,j] + f[1,j – 1]
For I := 2 to m do
Begin
For j := 1 to n do f[I,j] := f[I,j] + f[I,j - 1];
For j := 1 to n do f[I,j] := f[I,j] + f[I – 1,j];
End;
// ghi tổng từ [d1,c1] cho tới [d2,c2]:
Res := f[d2,c2] – f[d2,c1 – 1] – f[d1 – 1,c2] + f[d1 – 1,c1 – 1]
Phép chuyển mảng :
Chuyển từ mảng 1 chiều thành 2 chiều : a[k] thành b[I,j] // (c,d)
I := (k - 1) div c + 1;
If k mod c = 0 then j := c else j := k mod c;
B[I,j] := a[i];
Chuyển từ mảng 2 chiều thành 1 chiều : b[I,j] (d,c) thành a[k]
k := (I - 1) * c + j;
a[k] := b[I,j];
chuyển từ mảng 3 chiều thành 1 chiều : a[I,j,k] (ii,jj,kk) thành a[h]
h := (I - 1)*jj*kk + (j - 1)*kk + k;
a[h] := b[I,j,k];
chuyển từ mảng 1 chiều thành 3 chiều : a[h] thành a[I,j,k] (ii,jj,kk)
I := (h - 1) div (jj*kk) + 1;
C := (I - 1)*jj*kk;
J := (h - 1 – c) div kk + 1;
If (h - c) mod kk = 0 then k := kk else k := (h - c) mod kk;
Pp nén mảng :
khi phần tử liên tiếp của mảng trùng nhau 1 giá trị , ta có thể nén các gía trị ấy trong 1 mảng b[]
Nếu có 256 phần tử cùng có 1 gía trị là k thì :
If (n mod 256 = 0) then b[n div 256] := k;
Problem :
CVJETICI – [You must be registered and logged in to see this link.] (dùng pp nén mảng)
FORWARD STAR :
CTDL dạng này chủ yếu lưu giá trị của các cặp phân tử liên hệ lẫn nhau như là đồ thị
Mối liên hệ càng ít thì bộ nhớ sử dụng càng ít
Tuy nhiên để truy xét 1 cặp đối ngẫu bất kì thì ta phải duyệt hết tất cả các giá trị só thể có
Dạng này có thể cài dưới dạng con trỏ
- Code:
(dùng mảng)
var n,m,i,j,u,v,vv: integer;
head : array[1..maxn + 1] of longint;
adj : array[1..maxn] of longint;
begin
readln(n,m);
fillchar(head,sizeof(head),0);
for i := 1 to m do
begin
readln(u,v);
inc(head[u]);
end;
for i := 2 to n do head[i] := head[i] + head[i - 1];
readln(n,m);
for i := 1 to m do
begin
readln(u,v);
adj[head[u]] := v;
dec(head[u]);
end;
head[n + 1] := m;
for u := 1 to n do
for vv := head[u] + 1 to head[u + 1] do
begin
v := adj[vv];
writeln(u,' ',v);
end;
end.
STACK + QUEUE :
Stack : hoạt động theo cơ chế FILO
Queue : hoạt động theo cơ chế FIFO
Ngoài ra, 1 số cơ chế quan trọng có thể nói như sau :
deque - Double Ended Queue : là 1 pp kết hợp giữa stack và queue
Piority queue : cài đặt dựa trên dang sách vòng
Piority stack : đây là 1 pp khá hay, áp dụng khá nhiều trong nhiều bài tập khó và sáng tạo, và đây cũng là 1 dạng bài tập về pp CLDL phải hiểu rõ bản chất.
pp:
1 trong cách phổ biến là dùng biến left[] và right[] để cập nhật vị trí cưc trái và cực đại
left[] và right[] dc cập nhật bằng cách :
left[i] := left[left[i] – 1]
right[i] := right[right[i] +1]
note :
pp dc nêu trên chủ yếu làm trong phần init, thực hiện trong vòng lặp.
áp dụng tốt cho dạng bài tìm cực của pt mảng (vd : bài KAGAIN)
Problem :
MINK [You must be registered and logged in to see this link.] (dùng DEQUE – nhớ cập nhật biến front sau khi writeln ra vị trí nhỏ nhất)
KAGAIN [You must be registered and logged in to see this link.] (dùng piority stack)
CHEAT [You must be registered and logged in to see this link.]
TTRAVEL [You must be registered and logged in to see this link.]