Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1

Danh tiếng các thành viên

HạngThành viênĐiểm
1mr_invincible+213
2conankudo+149
3khuc_tuan+137
4tuananhnb93+129
5khanhptnk+108
6hphong+103
7flash_mt+99
8paulmcvn+71
9technolt+70
10hoangle+63

Topcoder Vietnam

HạngThành viênĐiểm
Diễn đàn
Forum
De contest 2 (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 1
CHỦ ĐỀ - De contest 2
#69650
thanghungkhi (Thành viên)
thanghungkhi+1
Biết code binary-indexed tree
Bài viết: 21
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69651
HelloSirius (Thành viên)
hellosirius+10
Nhắm mắt code không bug
Bài viết: 138
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69652
minhtuan_a0 (Thành viên)
minhtuan_a0+5
Đã biết code đệ quy
Bài viết: 11
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69653
giahuynd (Thành viên)
giahuynd-
Super fast coder
Bài viết: 58
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69654
khanh duy sau rom (Thành viên)
duy_sau_rom+2
Biết code binary-indexed tree
Bài viết: 30
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69655
mathias (Thành viên)
chlmathias+2
Biết code binary-indexed tree
Bài viết: 39
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69657
bosuavina (Thành viên)
Đã biết code đệ quy
Bài viết: 6
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69658
manhung95 (Thành viên)
askgfqf123+2
Super fast coder
Bài viết: 50
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69659
HelloSirius (Thành viên)
hellosirius+10
Nhắm mắt code không bug
Bài viết: 138
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69660
lady96 (Thành viên)
Biết code binary-indexed tree
Bài viết: 21
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: De contest 2 8 năm trước   (+0)
Cho em hỏi sao bài 3 lại ra 35 ạ @@ ngó mãi mà không hiểu sao ? ai có thể chỉ cụ thể cho em với
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
Bài viết trên cùng Gửi trả lời
Powered by FireBoardBài viết mới nhất từ diễn đàn cho các chương trình nhận tin RSS