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 18 ! (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 0
  • Trang:
  • << < 1 2 > >>
CHỦ ĐỀ - C11 Contest Round 18 !
#68337
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
C11 Contest Round 18 ! 8 năm, 1 tháng trước   (+0)
Cuộc thi đã kết thúc, lần này độ khó các bài được dàn khá đều. Nên đa số đều có thể làm dc, vấn đề chỉ là cẩn thận trong lúc code mà thôi .
Lời giải sẽ dc up sau.
Các thảo luận và đóng góp ý kiến về vòng 18 ở đây nhe
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#68339
vietthaitink21 (Thành viên)
vietthaitink21-
Đã code là AC
Bài viết: 85
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 18 ! 8 năm, 1 tháng trước   (+0)
Cho em hỏi bài QHROAD, mỗi lần loại bỏ một cạnh ta đi đếm số tp liên thông phải không ạ, em làm vậy được có 87.không biết thuật toán tốt hơn là gì ạ
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#68340
iamquang95 (Thành viên)
Nhắm mắt code không bug
Bài viết: 295
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 18 ! 8 năm, 1 tháng trước   (+0)
Dùng disjoin-set bạn ạ
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#68341
vietthaitink21 (Thành viên)
vietthaitink21-
Đã code là AC
Bài viết: 85
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 18 ! 8 năm, 1 tháng trước   (+0)
iamquang95 viết:
QUOTE:
Dùng disjoin-set bạn ạ :D

đó là thuật toán gì thế hả anh, em mới nghe lần đầu , không biết có thể xem ở đâu ạ
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#68342
sirdat_LS (Thành viên)
tranquocdat+26
Không code nữa rồi
Bài viết: 351
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 18 ! 8 năm, 1 tháng trước   (+0)
Cái đó là ctdl không phải thuật toán bạn ạ, bạn có thể gg, nó không khó kiếm
 
Đã lưu IP Đã lưu IP  
 
Cầu trời mai đề dễ chịu với con
  Đã khóa chức năng gửi bài.
#68343
fanchelseavip (Thành viên)
trumchepcode-
Đã biết code đệ quy
Bài viết: 18
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 18 ! 8 năm, 1 tháng trước   (+0)
bài QHROADS em làm dijsjont set, làm ngược lại, lần lượt bỏ cạnh vào ,làm xong sub luônm chủ quan không test, chỉ dc 36% số điểm , huhuhu, từ nay xin chừa.

bài LGAME em làm thuật toán N^2*S, ai có thuật toán tốt hơn là gì ạ ?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#68344
shiningstar_193 (Thành viên)
shiningstar193+3
Nhắm mắt code không bug
Bài viết: 222
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 18 ! 8 năm, 1 tháng trước   (+2)
Bài LGAME mình cài O(N*S) bằng cách đầu tiên:
Gọi L[i,j] là số lần xuất hiện của a[j] trong phân tích i bằng các số từ 1->i. tính L[i,j]tương tự bài đếm số cách phân tích N ra một số cách số tự nhiên <=j. với i=1..N, j=1..M
Sau đó mình duyệt ngược lại với i=N->1 gọi p[i,j]là đếm số lần xuất hiện của a[j] trong phân tích i bằng các số từ i->N đồng cập nhật luôn res[i]:=res[i]+p[i,j]*l[M-i,j-1];
Và tất nhiên bạn có thể dùng ngay chính mảng l để thay cho mảng p sẽ không ảnh hưởng đến kết quả.
 
Đã lưu IP Đã lưu IP  
 
Dù chỉ là 1 ngôi sao nhỏ, không thể sánh bằng ánh trăng rực rỡ ở bên cạnh, nhưng cũng không vì thế mà cam chịu cuối đầu, vẫn ngày ngày vươn mình chiếu sáng khắp nhân gian
  Đã khóa chức năng gửi bài.
#68345
xuanthuyvp (Thành viên)
xuanthuyvp+6
Biết code binary-indexed tree
Bài viết: 20
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 18 ! 8 năm, 1 tháng trước   (+0)
Nó được ứng dụng trong thuật toán kruskal.
 
Đã lưu IP Đã lưu IP  
 
_BXT_
  Đã khóa chức năng gửi bài.
#68349
Nguyen_Duy_Khanh (Thành viên)
songuku95+25
Không code nữa rồi
Bài viết: 374
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 18 ! 8 năm, 1 tháng trước   (+2)
shiningstar_193 viết:
QUOTE:
Bài LGAME mình cài O(N*S) bằng cách đầu tiên:
Gọi L[i,j] là số lần xuất hiện của a[j] trong phân tích i bằng các số từ 1->i. tính L[i,j]tương tự bài đếm số cách phân tích N ra một số cách số tự nhiên <=j. với i=1..N, j=1..M
Sau đó mình duyệt ngược lại với i=N->1 gọi p[i,j]là đếm số lần xuất hiện của a[j] trong phân tích i bằng các số từ i->N đồng cập nhật luôn res[i]:=res[i]+p[i,j]*l[M-i,j-1];
Và tất nhiên bạn có thể dùng ngay chính mảng l để thay cho mảng p sẽ không ảnh hưởng đến kết quả.


Mình chưa hiểu cách của cậu lắm: L[i,j] là số lần xuất hiện của a[j] ... mà i=1..N và j=1..M + cả phần đằng sau tính res nữa

Cách mình thì chỉ dùng mảng 1 chiều:

F[i] là số cách tạo ra tổng i từ tất cả n số đã cho:
Code:
khởi tạo F[0]=1
For i:=1 to n do
For j:=S downto A[i] do F[j] := F[j] + F[j-A[i]]
res[i] là số các lần phải dùng A[i] INP 4 3 1 1 1 2 Sau đó hãy để ý. Khi chạy xong với i=n-1 (bắt đầu đến i=n) thì
Code:
F[0] = 1; F[1] = 3; F[2] = 3; F[3] = 1 ( chỉ dùng 3 số 1 đầu tiên )
res[n] = F[S-A[n]] => res[4] = F[3-2] = 3 Mảng F sau khi i=n là:
Code:
F[0] = 1; F[1] = 3; F[2] = 4; F[3] =4
Với số A[i] ta coi nó đứng cuối dãy. VD xét i=1, A[i]=1. Làm sao để từ mảng F tạo từ các số (1,1,1,2) trở về mảng F (trước khi xét số cuối) tạo từ các số (1,1,2). Sau khi trả lời được câu hỏi đó là xong rồi ( để các bạn nghĩ thêm )
Code:
res[i] = F[ S-A[i] ]
Tuy nhiên F[S-A[i]] bây giờ đã được tăng 1 lượng F[ S-2*A[i] ]
F[ S - A[2*i] ] bây giờ đã được tăng 1 lượng F[ S-3*A[i] ]
F[ S - A[3*i] ] bây giờ đã được tăng 1 lượng F[ S-4*A[i] ]
Nhưng F[ S mod A[i] ] thì vẫn được giữ nguyên
Tính res[1]: F' khi dãy có (1,1,2) từ dãy F (1,1,1,2). x=A[1]=1
Code:
F'[0] = F[0] = 1   
F'[1] = F[1] - F'[1-x] = 3-1 = 2
F'[2] = F[2] - F'[2-x] = 4-2 = 2
F'[3] = F[3] - F'[3-x] = 4-2 = 2
res[1] = F' [S-A[1]] = F'[2] = 2 
Code:
Procedure init;
Begin
  F[0]:=1;
  For i:=1 to n do
  For j:=m downto a[i] do
    F[j]:=(F[j]+F[j-A[i]]) mod e;
End;
 
Procedure xuly;
Begin
  For i:=1 to n do
  IF A[i]<=m then
    begin
      // cach 1:
//      For j:=0 to m do S[j]:=F[j];
//      For j:=A[i] to m do S[j]:=(F[j]-S[j-A[i]]+e) mod e;
 
      // cach 2 (nhanh hon):
      x:=m mod A[i];
      S[x]:=F[x];
      Repeat
        x:=x+A[i];
        S[x]:=(F[x]-S[x-A[i]]+e) mod e;
      Until x=m;
      Write(S[m-A[i]],' ');
    end
  Else Write(0,' ');
End;
 
Đã lưu IP Đã lưu IP  
 
Y!M: duy_khanh308
  Đã khóa chức năng gửi bài.
#68375
fxminhtri1995 (Thành viên)
fxminhtri1995-
Đã biết code đệ quy
Bài viết: 19
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 18 ! 8 năm, 1 tháng trước   (-1)
BÀI NÀY EM DÙNG ĐỆ QUY ĐỂ PHÂN TÍCH S THÀNH TỔNG CỦA CÁC SỐ THUỘC DÁY A.
SAO ĐÓ EM ĐẾM SỐ LẦN XUẤT HIỆN CỦA TỪNG SỐ. NHƯNG LẠI BỊ TLE.

CÁC ANH GIÚP EM VỚI!
Code:
const
  inf = '';
  ouf = '';
 
var
   a , x  : array [ 0..1000] of longint;
   t , d : array [0..1000] of longint;
   c : array [ 1..1000] of boolean;
   n,s : longint;
 
procedure doc;
  var
    f : text;
    i : integer;
  begin
     assign(f,inf);
     reset(f);
     readln(f,n,s);
     for i :=1 to n do
        read(f,a[i]);
     close(f);
  end;
 
procedure khoitao;
  begin
     x[0] := 1;
     t[0] := 0;
     fillchar(c,sizeof(c),true);
     fillchar(d,sizeof(d),0);
  end;
 
procedure sort(d,c : longint);
  var
    i,j,t,tam : longint;
  begin
    i := d;
    j := c;
    t := a[(i+j) div 2];
    repeat
      while a[i]<t do inc(i);
      while a[j]>t do dec(j);
      if i<=j then
         begin
           tam := a[i];
           a[i] := a[j];
           a[j] := tam;
           inc(i); dec(j);
         end;
    until i>j;
    if i<c then sort(i,c);
    if d<j then sort(d,j);
  end;
 
procedure xuat(k : integer);
  var
     i : integer;
  begin
    for i := 1 to k do
       inc(d[x[i]]);
  end;
 
procedure tim(i : integer);
  var  j : integer;
  begin
     for j := x[i-1] to n do
       if c[j] and (S>=t[i-1]+a[j]) then
          begin
            x[i] := j;
            t[i] := t[i-1] + a[j];
            if t[i] = s then
               xuat(i)
            else
              begin
                c[j] := false;
                tim(i+1);
                c[j] := true;
              end;
          end;
  end;
 
procedure kq;
  var i : integer;
  begin
    for i := 1 to n do
       write(d[i]:6);
  end;
 
begin
  doc;
  khoitao;
  sort(1,n);
  tim(1);
  kq;
end.
 
 
Đã 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
  • Trang:
  • << < 1 2 > >>
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