|
|
|
Trả lời: De contest 2 8 năm trước
|
(+0)
|
|
Tại sao các bài trong kì thi lần này không chia ra các Subtask để thí sinh dễ dàng tìm thuật toán hơn ạ ^^
|
|
|
|
 Đã lưu IP
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: De contest 2 8 năm trước
|
(+0)
|
Bài 2 mình làm O(2^N). 
Duyệt tất cả 2^N tổng. Với mỗi tổng S kiểm tra có tồn tại tổng S/2 không, nếu có => cập nhật kq.
Bài 1 quy hoạch động O(N^2)
Gọi F[i,j] là độ dài cạnh hình vuông thõa mãn là bàn cờ lớn nhất khi xét đến ô (i,j).
| Code: | F[i,j]:=min(F[i-1,j-1],F[i,j-1],F[i-1,j])+1; |
Sau đó với mỗi loại bàn cờ mình đếm trên mảng này.  |
|
|
|
Đã lưu IP
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: De contest 2 8 năm trước
|
(+0)
|
blackstart viết:
QUOTE:
khanh duy sau rom viết:
QUOTE:
Cho mình hỏi bài 2 là chạy O( 3 ^ (n/2) ), có nhân thêm với log của nó k?
à có. mình dùng heap để đếm nên là 3^(n/2)*log((3^(n/2))
minhtuan_a0 viết:
QUOTE:
ý tưởng qhđ bài 3 của bạn như thế nào vậy?
à không. là K*N^2 chứ không phải N^3.
| Code: |
f[i,j] là chọn i thằng và đến thằng thứ j
sẽ cập nhật lên f[i+1,k]=f[i,j]+l[j+1,k]
cái l[i,j] này có thể tính trong n^2 |
Nhưng nếu làm thế này thì bạn đã tính chiều về chưa? Chiều Nam-Bắc ý?
|
|
|
|
Đã lưu IP
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: De contest 2 8 năm trước
|
(+0)
|
|
bài của mình
bài 1:
gọi f[i,j,k] là ô vuông thỏa mãn như bàn cờ mà ô ở i,j có giá trị k(k=0,1);
f[i,j,1]=min(f[i-1,j,0],f[i,j-1,0],f[i-1,j-1,1]+1;
f[i,j,0]=min(f[i-1,j,1],f[i,j-1,1],f[i-1,j-1,0]+1;
dựa vào mảng trên để lấy kq.O(n2);
bài 2:
-chia thành 2 phân.
-sort 1 phần.
-với mỗi gt của phần còn lại, tìm rồi cập nhật kq.
đpt:O(3^(n/2)*log(3^(n/2))
|
|
|
|
Đã lưu IP
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: De contest 2 8 năm trước
|
(+0)
|
HelloSirius viết:
QUOTE:
Bài 2 mình làm O(2^N). :D
Duyệt tất cả 2^N tổng. Với mỗi tổng S kiểm tra có tồn tại tổng S/2 không, nếu có => cập nhật kq.
Bài 1 quy hoạch động O(N^2)
Gọi F[i,j] là độ dài cạnh hình vuông thõa mãn là bàn cờ lớn nhất khi xét đến ô (i,j).
| Code: | F[i,j]:=min(F[i-1,j-1],F[i,j-1],F[i-1,j])+1; |
Sau đó với mỗi loại bàn cờ mình đếm trên mảng này. :x
Bạn duyệt tất cả 2^N tổng, là mất 2^N rồi, vậy kiểm tra có S/2 không chỉ tốn O(1) ak?
|
|
|
|
Đã lưu IP
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: De contest 2 8 năm trước
|
(+0)
|
|
Dùng mảng đánh dấu 960*10^6 phần tử. Giới hạn mã nguồn là hơn 1500MB mà
|
|
|
|
Đã lưu IP
|
|
|
Đã khóa chức năng gửi bài. |
bosuavina (Thành viên)
Đã biết code đệ quy
Bài viết: 6
 
|
|
Trả lời: De contest 2 8 năm trước
|
(+0)
|
|
Nếu bạn dùng đánh dấu thì làm sao bạn chắc chắn là cái tổng đã tồn tại trước đó ko có phần tử nào trùng với cái tổng đang xét ??? :-?
|
|
|
|
Đã lưu IP
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: De contest 2 8 năm trước
|
(+0)
|
|
Mình khuyên bạn ko nên dùng bộ nhớ quá lớn. Vì kì thi mục đích tập trung cho thi qg, mà thi quốc gia ko biết dc là dc dùng bao nhiêu bộ nhớ, nên nếu bây h bạn quen xài thoải mái thì tới lúc thi khổ lắm.
|
|
|
|
Đã lưu IP
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: De contest 2 8 năm trước
|
(+0)
|
khanh duy sau rom viết:
QUOTE:
Bạn duyệt tất cả 2^N tổng, là mất 2^N rồi, vậy kiểm tra có S/2 không chỉ tốn O(1) ak?
Tham lam.
|
|
|
|
Đã lưu IP
|
|
|
Đã khóa chức năng gửi bài. |
|
Được ưa thích: 1
