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
Trả lời: VO13 - day_1 - Thảo luận thuật toán (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Ủ ĐỀ - Trả lời: VO13 - day_1 - Thảo luận thuật toán
#69202
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: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng trước   (+1)
Hy vọng là các anh cố gắng làm 1 bản pdf solution giống PreVOI Hải Phòng cho mọi người tham khảo Cám ơn các anh rất nhiều
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69204
linuxpro (Thành viên)
linuxpro-
Biết code binary-indexed tree
Bài viết: 25
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: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng trước   (+0)
baolaptrinh viết:
QUOTE:
Bạn lấy abs(f[n]) đi vì nó có thể âm đó.Mình sửa đó và AC:D

Với bài của mình thì f[n] không thể âm dc do f[i]<= s[i] với mọi i
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69205
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: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng trước   (+0)
linuxpro viết:
QUOTE:

Với bài của mình thì f[n] không thể âm dc do f[i]<= s[i] với mọi i


Bạn share code mình xem thử sao!
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69210
pe_nhok_su (Thành viên)
pe_nhok_su-
Biết code binary-indexed tree
Bài viết: 22
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: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng trước   (+0)
khanhsuphu12 viết:

QUOTE:
Bài VOCACTUS mình dùng dijkstra để tìm đường đi vs time ngắn nhất từ s -> t. Nếu số đỉnh là lẻ -> exit và writefile. Nếu ko có đường đi thì exit -> -1. Nếu số đỉnh là chẵn thì loại bỏ từng đường đi trong đường đi ấy và tìm đường đi ngắn nhất từ s->t (lại kiểm tra nhưng những bước đã nói ở trên) :)
Và nếu không tìm được bằng các biện pháp trên thì exit -1


Bài VOCACTUS em làm theo ý tưởng này nhưng nộp lên chỉ được 5đ. Rất mong các anh chị chỉ dùm em chỗ sai để em sửa lại, em là coder mới mong được giúp đỡ

Code:
program VOCACTUS;
 
const fin='';
      fon='';
 
type cung=record
     v,w,link:longint;
     end;
 
var d,trace,head:array[0..10000] of longint;
    adj:array[0..10000] of cung;
    avail:array[0..10000] of boolean;
    n,m,s,f,dem,ts:longint;
 
procedure enter;
  var i,u:longint;
  begin
    dem:=0;
    fillchar(head,sizeof(head),0);
    readln(n,m,s,f);
    for i:=1 to m do
        begin
 
        inc(dem);
        read(u,adj[dem].v,adj[dem].w);
        adj[dem].link:=head[u];
        head[u]:=dem;
 
        inc(dem);
        adj[dem].v:=u;
        adj[dem].w:=adj[dem-1].w;
        adj[dem].link:=head[adj[dem-1].v];
        head[adj[dem-1].v]:=dem;
        end;
    dem:=1;
  end;
 
procedure relax(u,v,w:longint);
  begin
    if d[v]>(d[u]+w) then
       begin
       d[v]:=d[u]+w;
       trace[v]:=u;
       end;
  end;
 
procedure dijkstra;
  var u,v,i:longint;
  begin
    repeat
      u:=0;
      for v:=1 to n do
           if (avail[v]=true) and (d[v]<d[u]) then
               u:=v;
      if (u=0) or (u=f) then break;
      avail[u]:=false;
      i:=head[u];
      while i<>0 do
          begin
          relax(u,adj[i].v,adj[i].w);
          i:=adj[i].link;
          end;
     until false;
  end;
 
procedure truyvet;
  begin
    if d[f]=10000000 then writeln(-1)
    else
       begin
         ts:=d[f];
         while f<>s do
            begin
            inc(dem);
            f:=trace[f];
            end;
       end;
  end;
 
procedure delete;
  begin
    d[f]:=0;
    while f<>s do
      begin
      f:=trace[f];
      d[f]:=0;
      end;
  end;
 
procedure solve;
  var i:longint;
  begin
    for i:=0 to n do d[i]:=10000000;
    d[s]:=0;
    fillchar(avail[1],n*sizeof(avail[1]),true);
    dijkstra;
    truyvet;
    if (dem mod 2 <> 0) then
       begin
       writeln(ts);
       exit;
       end
    else
      begin
      delete;
      fillchar(avail[1],n*sizeof(avail[1]),true);
      dijkstra;
      truyvet;
      end;
    writeln(-1)
  end;
 
BEGIN
  assign(input,fin);
  reset(input);
  assign(output,fon);
  rewrite(output);
  enter;
  solve;
  close(input);
  close(output);
END.
 
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69229
linuxpro (Thành viên)
linuxpro-
Biết code binary-indexed tree
Bài viết: 25
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: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng trước   (+0)
HelloSirius viết:
QUOTE:
linuxpro viết:
QUOTE:

Với bài của mình thì f[n] không thể âm dc do f[i]<= s[i] với mọi i


Bạn share code mình xem thử sao! :D

Mình sửa được rồi . không phải lỗi đó, cũng không biết sai ở đâu nữa. Mình chỉ sửa lại cái cây cho giảm bộ nhớ đi thì AC
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69242
iamnhvt (Thành viên)
iamnhvt123-
Super fast coder
Bài viết: 68
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: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng trước   (+0)
pe_nhok_su viết:
QUOTE:
khanhsuphu12 viết:

QUOTE:
Bài VOCACTUS mình dùng dijkstra để tìm đường đi vs time ngắn nhất từ s -> t. Nếu số đỉnh là lẻ -> exit và writefile. Nếu ko có đường đi thì exit -> -1. Nếu số đỉnh là chẵn thì loại bỏ từng đường đi trong đường đi ấy và tìm đường đi ngắn nhất từ s->t (lại kiểm tra nhưng những bước đã nói ở trên) :)
Và nếu không tìm được bằng các biện pháp trên thì exit -1


Bài VOCACTUS em làm theo ý tưởng này nhưng nộp lên chỉ được 5đ. Rất mong các anh chị chỉ dùm em chỗ sai để em sửa lại, em là coder mới mong được giúp đỡ :)

Code:
program VOCACTUS;
 
const fin='';
      fon='';
 
type cung=record
     v,w,link:longint;
     end;
 
var d,trace,head:array[0..10000] of longint;
    adj:array[0..10000] of cung;
    avail:array[0..10000] of boolean;
    n,m,s,f,dem,ts:longint;
 
procedure enter;
  var i,u:longint;
  begin
    dem:=0;
    fillchar(head,sizeof(head),0);
    readln(n,m,s,f);
    for i:=1 to m do
        begin
 
        inc(dem);
        read(u,adj[dem].v,adj[dem].w);
        adj[dem].link:=head[u];
        head[u]:=dem;
 
        inc(dem);
        adj[dem].v:=u;
        adj[dem].w:=adj[dem-1].w;
        adj[dem].link:=head[adj[dem-1].v];
        head[adj[dem-1].v]:=dem;
        end;
    dem:=1;
  end;
 
procedure relax(u,v,w:longint);
  begin
    if d[v]>(d[u]+w) then
       begin
       d[v]:=d[u]+w;
       trace[v]:=u;
       end;
  end;
 
procedure dijkstra;
  var u,v,i:longint;
  begin
    repeat
      u:=0;
      for v:=1 to n do
           if (avail[v]=true) and (d[v]<d[u]) then
               u:=v;
      if (u=0) or (u=f) then break;
      avail[u]:=false;
      i:=head[u];
      while i<>0 do
          begin
          relax(u,adj[i].v,adj[i].w);
          i:=adj[i].link;
          end;
     until false;
  end;
 
procedure truyvet;
  begin
    if d[f]=10000000 then writeln(-1)
    else
       begin
         ts:=d[f];
         while f<>s do
            begin
            inc(dem);
            f:=trace[f];
            end;
       end;
  end;
 
procedure delete;
  begin
    d[f]:=0;
    while f<>s do
      begin
      f:=trace[f];
      d[f]:=0;
      end;
  end;
 
procedure solve;
  var i:longint;
  begin
    for i:=0 to n do d[i]:=10000000;
    d[s]:=0;
    fillchar(avail[1],n*sizeof(avail[1]),true);
    dijkstra;
    truyvet;
    if (dem mod 2 <> 0) then
       begin
       writeln(ts);
       exit;
       end
    else
      begin
      delete;
      fillchar(avail[1],n*sizeof(avail[1]),true);
      dijkstra;
      truyvet;
      end;
    writeln(-1)
  end;
 
BEGIN
  assign(input,fin);
  reset(input);
  assign(output,fon);
  rewrite(output);
  enter;
  solve;
  close(input);
  close(output);
END.
 
mình nghĩ có thể bị quá thời gian,giới hạn n đến 10^5 lận mà.. bài này bắt buộc phải cài heap thôi
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69578
tink9 (Thành viên)
tuanrint+1
Đã biết code đệ quy
Bài viết: 14
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: VO13 - day_1 - Thảo luận thuật toán 8 năm trước   (+0)
vodanh9x viết:
QUOTE:

bài VOBOARD: gọi b[i] là số lượng lần nâng hàng i, c[i] là số lần nâng cột i
=> đk thỏa mãn là (b[i]+c[j]+a[i,j]) mod k = 0 vs mọi i=1..m,j=1..n;
lại thấy b[i],c[j]<K
từ đó for giá trị của b[1] (0->k-1) rồi tính các c[j],b[i] trong O(m+n) => đpt là K*(M+N) (70%) :D
:S


cái c[j],b[i] tính là mình tăng c[j] lên rồi lại tăng b[i] lên từng cái hay răng anh?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69625
ubergeek (Thành viên)
ubergeek+1
Biết code binary-indexed tree
Bài viết: 41
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: VO13 - day_1 - Thảo luận thuật toán 8 năm trước   (+0)
iamquang95 viết:
QUOTE:

Code:
6 8 1 6
1 2 1
2 5 1
5 6 1
1 5 20
1 6 10
2 3 1
3 4 1
4 2 1
hình như test này không phải là đồ thị xương rồng, có canh (1,2) và (2,5) thuộc 2 chu trinhg (1-2-5-1) và (1-2-5-6-1) đúng không?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69632
perfwill (Thành viên)
perfwill
Biết code binary-indexed tree
Bài viết: 44
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: VO13 - day_1 - Thảo luận thuật toán 8 năm trước   (+0)
Bài VOCACTUS mình AC với thuật toán như sau, vẫn chưa thấy ai đưa ra thuật toán này:
- Xác định các chu trình trong đồ thị, cạnh nào thuộc chu trình nào
- Duyệt bắt đầu từ S, xử lí chu trình đầu tiên chứa đỉnh S, cứ gặp 1 cạnh thuộc chu trình mới, ta xét chu trình bắt đầu từ đỉnh u được gặp đầu tiên đó.
Tại mỗi lần duyệt 1 chu trình: cập nhật đường đi ngắn nhất theo 2 chiều tương ứng với 2 cạnh nối với u trong chu trình, khi vẽ ra có thể hiểu là "chiều kim đồng hồ" và "ngược chiều kim đồng hồ" . Đường đi ngắn nhất gồm đường đi lẻ dl[v] và đường đi chẵn dc[v], trong đó:
dl[v]=min(dl[v], dc[p]+c[v, p])
dc[v]=min(dc[v], dl[p]+c[v, p])
Với p là đỉnh cha của v trong chiều đang xét.
Khi duyệt hết chu trình thì ta có đường đi cần tìm là dl[T] .
Tính đúng đắn: do các tính chất đặc biệt của đồ thị xương rồng .
 
Đã 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