Minh Vu

Link:  https://codeforces.com/group/FLVn1Sc504/contest/274518/problem/W Tags: dp, dijkstra, shortest path Difficulty: ez++ Tóm tắt: Cho đồ thị gồm n đỉnh đánh số từ 1 đến n. Cần tìm tổng số đường đi ngắn nhất từ 1 đến n. Ý tưởng: Sử dụng thuật toán dijkstra tìm đường đi ngắn nhất như bình thường, tuy nhiên ta đặt thêm mảng dp[i] với ý nghĩa dp[i] là số đường đi ngắn nhất từ đỉnh 1 đến đỉnh i. Ta vừa dijkstra vừa update như sau: Giả sử ta đang ở đỉnh u và đỉnh tiếp theo là v, và trọng số cạnh giữa u và v là w: Nếu dist[v] > dist[u] + w thì dist[v] = dist[u] + w và dp[v] = dp[u] Nếu dist[v] == dist[u] + w thì dp[v] += dp[u] Khởi tạo dp[1] = 1 vì luôn có 1 đường đi từ đỉnh 1 đến chính nó. Code:  https://ideone.com/XxdyLB

★ Today's tune:  https://youtu.be/TLVK0iTDev0 ★ Link: https://codeforces.com/problemset/problem/1462/E2 ★ Tags: binary search, combinatorics, modulo inverse ★ Difficulty: 1700 ★ Tóm tắt (khuyến khích không nên đọc vì đọc xong sẽ không hiểu): Cho dãy a[] gồm N số. Yêu cầu đếm số cách để chọn ra một dãy có m phần tử, và chênh lệch giữa số lớn nhất và số nhỏ nhất trong dãy tìm được nhỏ hơn hoặc bằng k , lấy dư với 10^9 + 7 . ★ Nhận xét: Dãy tìm được không mất tính tổng quát khi so sánh giá trị giữa phần tử lớn nhất và nhỏ nhất trong dãy. Ví dụ: giả sử chọn được 3 số a[1], a[2], a[3] và a[1] là số lớn nhất, a[3] là số nhỏ nhất. Từ đó suy ra max(a[1], a[2], a[3]) = a[1] và min(a[1], a[2], a[3]) = a[3]. Nếu thay đổi vị trí 3 số này trở thành a[2], a[3], a[1] thì số lớn nhất vẫn là a[1] và số nhỏ nhất vẫn là a[3] -> không đổi. Suy ra dãy cần tìm không bị ràng buộc theo thứ tự vị trí. Ta chỉ cần đếm cách chọn m số trong đoạn từ [x, x + k]. Có thể sắp xếp lại và dùng tổ...

★ Link:  https://codeforces.com/group/FLVn1Sc504/contest/274496/problem/M ★ Difficulty: ezpz ★ Tags: deque ★ Kiến thức:  https://vnoi.info/wiki/algo/data-structures/deque-min-max.md ★ Tóm tắt: Cho dãy số a[] với n phần tử. Ta cần tìm giá trị k = a[i] * (ri - li + 1) là lớn nhất với a[i] = min(a[li], a[li+1],.., a[ri]). Nói cách khác a[i] là phần tử nhỏ nhất trong đoạn a[li...ri]. ★ Ý tưởng: sử dụng deque cơ bản. Gọi L[i] là vị trí xa nhất về bên trái đối với phần từ a[i] thoả điều kiện a[L[i]...i-1] đều lớn hơn hoặc bằng a[i]. Gọi R[i] là vị trí xa nhất về bên phải đối với phần tử a[i] thoả điều kiện a[i+1...R[i]] đều lớn hơn hoặc bằng a[i]. Để tìm các vị trí L[i] và R[i] như trên ta sẽ dùng deque. Các bạn xem code và đọc tài liệu bên trên sẽ rõ. ★ Code:  https://ideone.com/bsCxZe