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
C11 contest round 15 (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 0
CHỦ ĐỀ - C11 contest round 15
#67603
hieult (Thành viên)
hieult+9
Đã biết code đệ quy
Bài viết: 15
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: C11 contest round 15 8 năm, 2 tháng trước   (+0)
Anh cây khung cho mỗi trạng thái của các nhóm được ghép vs nhau mất 2^k nhân cây khung rồi khi tính kết quả với mỗi trạng thái duyệt hết các tập con mất 3^k nữa
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#67604
alex_pythagore (Thành viên)
alex_pythagore+38
Super fast coder
Bài viết: 51
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: C11 contest round 15 8 năm, 2 tháng trước   (+0)
hieult viết:
QUOTE:
Siuvit làm bài "Nhà thông thái" như nào mà time 0.00 khủng vậy

Em cũng cài thuật giống anh 3^k thôi . Tại e sinh test nên biết trick của nó nên, thời gian mới nhanh vậy :-p.

Bài đó anh Xuân Khánh cài đúng thuật ròi. Mà chẳng biết thế nào lại TLE.

Không biết bài NKMAGE có thuật nào tốt hơn không mọi ngừoi ?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#67605
pirate (Admin)
khanhptnk+108
Admin
Bài viết: 868
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: C11 contest round 15 8 năm, 2 tháng trước   (+0)
@Huy: sao khi anh chuyển về mảng thì đến giờ vẫn không hiểu sao sai, cho anh xin test 2 với...
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#67606
alex_pythagore (Thành viên)
alex_pythagore+38
Super fast coder
Bài viết: 51
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: C11 contest round 15 8 năm, 2 tháng trước   (+0)
Anh Khanh bi sai test voi K=1
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#67613
vodanh9x (Thành viên)
vodanh9x+14
Nhắm mắt code không bug
Bài viết: 233
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: C11 contest round 15 8 năm, 2 tháng trước   (+0)
R_R_ viết:
QUOTE:
Bài C11FBR mình thấy cách của bạn vodanh9x có thể bỏ chiều i đi đc, từ đó giảm đc độ phức tạp đi 30 lần, chắc là đủ để acc :D (cụ thể: biểu thức (1-->j) tách thành (1-->j' ) + (j'..j))

vậy anh tính (j'->j) kiểu gì ạ? em thử làm vậy rồi nhưng kq sai ạ
ban đầu em cũng nghĩ (j'->j) hoặc là k có ngoặc hoặc 1 ngoặc bao hết (vì trường hợp k bao hết sẽ đc xét trước đó rồi) nhưng k nghĩ đến nó bao hết, nhưng trong đó lại có thêm ngoặc nữa, thành ra bị sai ạ. Anh có cách cải tiến nào k ạ? em cải tiến chút 60% 0.02s nhưng k thể ăn thêm đc @@
 
Đã lưu IP Đã lưu IP  
 
Hahaha
  Đã khóa chức năng gửi bài.
#67618
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: C11 contest round 15 8 năm, 2 tháng trước   (+0)
Bài nkmage em cũng duyệt hết 2^k cây khung, nhưng tới phần tình kq thì lại làm 2^2k nên tle. Làm ơn giải thích giùm em là tại sao sinh hết các tập con lại mất 3^k ạ? (em cảm ơn)
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#67619
alex_pythagore (Thành viên)
alex_pythagore+38
Super fast coder
Bài viết: 51
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: C11 contest round 15 8 năm, 2 tháng trước   (+2)
Xét dãy bit 011010. Do chỉ có 3 phần tử (3 bit 1). Nên số lựong tập con của nó là 2^3=8.

Xét tổng quát dãy bit độ dài N có K bit 1 :
- Số lựong dãy bit dài N có K bit 1 là : C(N,K) (chính là số cách chọn K trong N bit)
- Số lựong tập con của dãy bit đó là 2^k.
--> có tổng cộng là C(N,K) * 2^K tập con của tất cả các dãy bit có độ dài N và K bit 1.

Vậy tổng tất cả lại (khi cho K chạy từ 0 --> N) :
sum( C(N,K) * 2^K ) với 0<=K<=N.

Nhận thấy đây chính là khai triển ra của (2+1)^N, nên :
sum( C(N,K) * 2^K ) = (2+1)^N = 3^N.

Mà trong bài toán này N là tham số K đề bài cho.

thêm về khai triển nhị thức : http://en.wikipedia.org/wiki/Binomial_theorem .
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#67620
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: C11 contest round 15 8 năm, 2 tháng trước   (+0)
Dạ vâng. Em cảm ơn ạ.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#67623
flashmt (Admin)
flash_mt+99
Admin
Bài viết: 417
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: C11 contest round 15 8 năm, 2 tháng trước   (+2)
Có thể giải thích đơn giản hơn bằng cách viết dưới hệ cơ số 3. Chữ số thứ i > 0 nghĩa là i nằm trong tập đang xét, chữ số thứ i = 2 nghĩa là i nằm trong tập con đang xét

Vd: 011202 nghĩa là ta xét tập (2,3,4,6) và tập con là (4,6)

Dễ thấy mỗi cách sẽ tương ứng với 1 và chỉ 1 số trong hệ cơ số 3, từ đó suy ra có 3^k cách.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#67629
pirate (Admin)
khanhptnk+108
Admin
Bài viết: 868
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: C11 contest round 15 8 năm, 2 tháng trước   (+2)
Code:
 
int subset = set;
while (subset > 0) subset = (subset - 1) & set;
Chắc là bạn cũng cần đoạn code trên, nó sinh ra tất cả subset của "set" (lưu ý dấu '&' tức là 'and' trong pascal).
 
Đã 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