مخزن جامع المپیاد کامپیوتر - الگوریتمهای گراف و دادهساختارهای پیشرفته
معرفی مخزن
این مخزن آموزشی ویژه دانشپژوهان المپیاد کامپیوتر و علاقهمندان به برنامهنویسی رقابتی در دبیرستان استعدادهای درخشان علامه حلی ملارد گردآوری شده است. تمرکز کدهای این مخزن بر تحلیل مرتبه زمانی بهینه، پیادهسازی تمیز در شرایط مسابقه و رعایت استاندارد ++C20 میباشد.
سرفصلهای اصلی مخزن:
- ساختارهای داده پیشرفته:
- درخت سگمنت (Segment Tree) با انتشار تنبل (Lazy Propagation)
- جدول استی (Sparse Table) برای پرسوجوی مینیمم بازهای (RMQ) در زمان $O(1)$
- ساختار داده اتحاد-پیدا کردن (Disjoint Set Union) با بهینهسازی رتبه و فشردهسازی مسیر
- الگوریتمهای بهینه گراف:
- الگوریتم دایکسترا با صف اولویت استاندارد و تحلیل $O((V+E)\log V)$
- الگوریتم تارجان (Tarjan) برای یافتن مولفههای قویاً همبند (SCC) و پلها
- الگوریتم دینیک (Dinic) برای مسئله جریان بیشینه (Max-Flow) در زمان $O(V^2 E)$
جدول مقایسه مرتبه زمانی دادهساختارها
| ساختار داده |
زمان ساخت |
پرسوجو (Query) |
بهروزرسانی (Update) |
کاربرد اصلی |
| Segment Tree |
$O(N)$ |
$O(\log N)$ |
$O(\log N)$ |
جمع و مینیمم بازهای پویا |
| Sparse Table |
$O(N \log N)$ |
$O(1)$ |
$O(N)$ |
پرسوجوی ایستا RMQ و GCD |
| Fenwick (BIT) |
$O(N)$ |
$O(\log N)$ |
$O(\log N)$ |
جمع پیشوندی با کدنویسی کم |
| DSU |
$O(N)$ |
$O(\alpha(N))$ |
$O(\alpha(N))$ |
بررسی همبندی و الگوریتم کروسکال |
پیادهسازی استاندارد درخت سگمنت با پایتون ۳
class SegmentTree:
def __init__(self, data):
self.n = len(data)
self.tree = [0] * (4 * self.n)
if self.n > 0:
self._build(data, 1, 0, self.n - 1)
def _build(self, data, node, start, end):
if start == end:
self.tree[node] = data[start]
return
mid = (start + end) // 2
self._build(data, 2 * node, start, mid)
self._build(data, 2 * node + 1, mid + 1, end)
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
def query(self, node, start, end, l, r):
if r < start or end < l:
return 0
if l <= start and end <= r:
return self.tree[node]
mid = (start + end) // 2
p1 = self.query(2 * node, start, mid, l, r)
p2 = self.query(2 * node + 1, mid + 1, end, l, r)
return p1 + p2
نکته المپیادی: در مسائل مرحله دوم، همواره ثابت زمانی حافظه و پدیده Cache Locality را مد نظر قرار دهید؛ بردار خطی معمولاً تا ۳ برابر سریعتر از ماتریس دو بعدی اشارهگری پردازش میشود.
برای دانلود کدهای کامل ++C و تستکیسهای مرجع، از بخش فایلهای پیوست بالای صفحه اقدام فرمایید.
دیدگاهها، پرسشها و نظرات دانشآموزان (3)