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
Xem đầy đủ

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
Xem đầy đủ

Topcoder Vietnam

HạngThành viênĐiểm
Diễn đàn
Forum
Forum Thi cử Các kỳ thi trực tuyến
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Ủ ĐỀ - VO13 - day_1 - Thảo luận thuật toán
#69055
quandum (Thành viên)
quandum+14
Nhắm mắt code không bug
Bài viết: 261
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
VO13 - day_1 - Thảo luận thuật toán 8 năm trước   (+0)
Mọi người vào cùng nhau thảo luận cách giải nhé.
 
Đã lưu IP Đã lưu IP  
 
Nhất trường, nhất tỉnh làm chi?
Cũng là con ếch ngồi lì giếng hôi...
  Đã khóa chức năng gửi bài.
#69056
R_R_ (Admin)
mr_invincible+213
Admin
Bài viết: 745
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   (+1)
Lời giải bài VOBOARD của rockman9x_94:
Mình copy nguyên từ đoạn chat của mình, nên nhiều chỗ hơi qua quýt

"Gọi a1, a2 .. là số bước biến đổi hàng i nhé
b1, b2 .. -> cột
bh xét a1
-> tính đc tất cả các a2, .., b1, b2..
và các giá trị này luôn thỏa mãn ?
-> update kết quả
bh giả sử a1++
-> b1--, b2--, b3--, ....
-> a2++, a3++, a4++, ..
Duyệt hết các giá trị có thể có của a1 (có O(MN) giá trị), mỗi giá trị của a1 thì tính kq trong O(1)."
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69057
quandum (Thành viên)
quandum+14
Nhắm mắt code không bug
Bài viết: 261
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 để cử thuật toán sau:
- Tính F[u] là đường đi ngắn nhất từ S->u, và T[u] là đường đi ngắn nhất từ T->u. Đồng thời lưu số đỉnh đi kèm. Ta có thể tính F[] và T[] trong 2 lần dijistra + heap.

- Duyệt tìm kq là min(F[v]+T[v]) sao cho từ s->...->v->...->t là số đỉnh lẻ là đường đi ngắn nhất từ T->u. Đồng thời lưu số đỉnh đi kèm. Ta có thể tính F[] và T là đường đi ngắn nhất từ T->u. Đồng thời lưu số đỉnh đi kèm. Ta có thể tính F[] và T[] trong 2 lần dijistra + heap.

- Duyệt tìm kq là min(F[v]+T[v]) sao cho từ s->...->v->...->t là số đỉnh lẻ là đường đi ngắn nhất từ T->u. Đồng thời lưu số đỉnh đi kèm. Ta có thể tính F[] và T[] trong 2 lần dijistra + heap.

- Duyệt tìm kq là min(F[v]+T[v]) sao cho từ s->...->v->...->t là số đỉnh lẻ.

Dễ nhận thấy nếu không có đường đi thì kq luôn có giá trị là khoảng vô cực.
 
Đã lưu IP Đã lưu IP  
 
Nhất trường, nhất tỉnh làm chi?
Cũng là con ếch ngồi lì giếng hôi...
  Đã khóa chức năng gửi bài.
#69058
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: VO13 - day_1 - Thảo luận thuật toán 8 năm trước   (+0)
R_R_ viết:
QUOTE:
Lời giải bài VOBOARD của rockman9x_94:
Mình copy nguyên từ đoạn chat của mình, nên nhiều chỗ hơi qua quýt :D

"Gọi a1, a2 .. là số bước biến đổi hàng i nhé
b1, b2 .. -> cột
bh xét a1
-> tính đc tất cả các a2, .., b1, b2..
và các giá trị này luôn thỏa mãn ?
-> update kết quả
bh giả sử a1++
-> b1--, b2--, b3--, ....
-> a2++, a3++, a4++, ..
Duyệt hết các giá trị có thể có của a1 (có O(MN) giá trị), mỗi giá trị của a1 thì tính kq trong O(1)."


Các giá trị cộng/trừ trong mod K.
Vấn đề ở đây là lấy giá trị trong O(1).
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69059
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 trước   (+1)
Bài VOCACTUS mình làm như sau, không biết đúng không nhỉ?

Gọi:
- D[u,0] là đường đi ngắn nhất từ s tới u và qua 1 số chẵn đỉnh.
- D[u,1] là đường đi ngắn nhất từ s tới u và qua 1 số lẻ đỉnh.
Ban đầu mình gán D[s,1]:=0 rồi tính D bằng Dijkstra Heap.
Kết quả là D[t,1].
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69060
blackstart (Thành viên)
blackstart+40
Không code nữa rồi
Bài viết: 362
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   (+1)
bài VOCARD cõ lẽ sẽ là QHĐ + Dequeue >D
với
Code: 
f[i] là vị trí quân bài đen gần nhất từ i->n
 
Đã lưu IP Đã lưu IP  
 
"Nothing is impossible; impossible itself says "I m possible"..."


Là Nam Nhi gõ phím bình thiên hạ...
Thân Anh Hùng click chuột định giang sơn...
  Đã khóa chức năng gửi bài.
#69061
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: VO13 - day_1 - Thảo luận thuật toán 8 năm trước   (+0)
bài VOCARD của mình:
-gọi sum[i] là tổng số là bài màu đen từ 1->i.
-gọi f[i] là số tiến lớn nhất mà người đi trước nhận được nếu xét bộ bài từ 1->i.
-f[i]=min(sum[j-1]-f[j-1]+sum[i]-sum[j-1]);j=i-k+1..i-1;
-xét f[n] để đưa ra kết quả.
-->đpt:O(n2);
có thể dùng IT như bài qmax để cái tiến-->đpt(nlogn).(nhưng mà mình làm k kịp )
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69062
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: VO13 - day_1 - Thảo luận thuật toán 8 năm trước   (+0)
HelloSirius viết:
QUOTE:
Bài VOCACTUS mình làm như sau, không biết đúng không nhỉ?

Gọi:
- D[u,0] là đường đi ngắn nhất từ s tới u và qua 1 số chẵn đỉnh.
- D[u,1] là đường đi ngắn nhất từ s tới u và qua 1 số lẻ đỉnh.
Ban đầu mình gán D[s,1]:=0 rồi tính D bằng Dijkstra Heap.
Kết quả là D[t,1]. :)


Bài bạn bị sai khi có chu trình lẻ
Bạn có thể thử test này
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
Bài VOCARD có thể dùng dequeue để giảm đpt :-?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69063
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 trước   (+0)
iamquang95 viết:
QUOTE:
HelloSirius viết:
QUOTE:
Bài VOCACTUS mình làm như sau, không biết đúng không nhỉ?

Gọi:
- D[u,0] là đường đi ngắn nhất từ s tới u và qua 1 số chẵn đỉnh.
- D[u,1] là đường đi ngắn nhất từ s tới u và qua 1 số lẻ đỉnh.
Ban đầu mình gán D[s,1]:=0 rồi tính D bằng Dijkstra Heap.
Kết quả là D[t,1]. :)


Bài bạn bị sai khi có chu trình lẻ :)
Bạn có thể thử test này
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
Bài VOCARD có thể dùng dequeue để giảm đpt :-?
kq=21? Cho mình thêm xin thên một vài test nữa được không? Test của bạn mình chạy ra 21. >D
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69064
fire_from_hell (Thành viên)
Đã biết code đệ quy
Bài viết: 12
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ạn thử test này xem:
6 6 1 6
1 2 1
2 3 1
3 4 1
4 5 1
3 5 1
3 6 1

ra -1
 
Đã 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