|
|
|
VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng trước
|
(+0)
|
|
Mọi người vào cùng nhau thảo luận cách giải nhé.
|
|
|
|
 Đã 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. |
|
|
|
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng 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
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng 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
|
|
|
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. |
|
|
|
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng 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
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng 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
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng 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
|
|
|
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng 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
|
|
|
Đã khóa chức năng gửi bài. |
iamquang95 (Thành viên)
Nhắm mắt code không bug
Bài viết: 295
 
|
|
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:
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
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng 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
|
|
|
Đã khóa chức năng gửi bài. |
|
|
|
Trả lời: VO13 - day_1 - Thảo luận thuật toán 8 năm, 1 tháng 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
|
|
|
Đã khóa chức năng gửi bài. |
|
Được ưa thích: 1
