مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

این صفحه فقط خواندنی است. شما می‌توانید متن صفحه را مشاهده کنید، اما نمی‌توانید آن را تغییر دهید. اگر فکر می‌کنید که مشکلی رخ داده است، مدیر ویکی را در جریان بگذارید.
====== داده‌ساختارها ======
در این قسمت داده‌ساختارهای موجود در کتابخانه استاندارد $C++$ را مرور می‌کنیم و داده‌ساختارهای لازم برای پیاده‌سازی الگوریتم‌ها را معرفی می‌کنیم.
===== انواع داده‌ای استاندارد =====
  * [[http://www.cplusplus.com/reference/vector/vector/|آرایه پویا]]
  * [[http://www.cplusplus.com/reference/queue/queue/|صف]]
  * [[http://www.cplusplus.com/reference/queue/priority_queue/|صف اولویت]]
  * [[http://www.cplusplus.com/reference/stack/stack/|پشته]]
  * [[http://www.cplusplus.com/reference/map/map/|دیکشنری (زوجهای کلید-مقدار)]]
  * [[http://www.cplusplus.com/reference/set/set/|مجموعه (ذخیره شده در درخت متوازن)]]
===== انواع داده‌ای کمکی =====

  * [[http://www.cplusplus.com/reference/utility/|زوج مرتب]]
  * [[http://www.cplusplus.com/reference/complex/|اعداد مختلط]]
  * [[http://www.cplusplus.com/reference/ratio/|اعداد کسری(دارای صورت و مخرج)]]
  * [[http://www.cplusplus.com/reference/tuple/|چندتایی مرتب]]
  * [[الگوریتم:پردازش_رشته|رشته]]
  * [[http://www.cplusplus.com/reference/valarray/valarray/|آرایه با عملیات یکسان روی همه‌ی اعضا]]
  * [[http://www.cplusplus.com/reference/bitset/bitset/|آرایه‌ای از بیت‌ها]]
===== مجموعه‌های مجزا =====
این داده‌ساختار همان‌طور که از نام آن پیداست مجموعه‌ای از تعدادی مجموعه‌ی مجزا است. دو عمل روی این مجموعه‌ها داریم:
  * ادغام دو مجموعه
  * پیدا کردن مجموعه‌ی شامل یک عضو
مزیت این ساختمان داده زمان کم آن برای عملیات گفته‌شده است که $O(\alpha(n))$ است که می‌توان در عمل آن را ثابت فرض کرد.

کاربرد این ساختمان داده در [[الگوریتم:درخت_پوشای_کمینه|الگوریتم کراسکال]] است.

[[http://fa.wikipedia.org/wiki/%D9%85%D8%AC%D9%85%D9%88%D8%B9%D9%87%E2%80%8C%D9%87%D8%A7%DB%8C_%D9%85%D8%AC%D8%B2%D8%A7_(%D8%B3%D8%A7%D8%AE%D8%AA%D9%85%D8%A7%D9%86_%D8%AF%D8%A7%D8%AF%D9%87)|مطالب بیشتر در مورد ساختمان داده‌ی مجموعه‌های مجزا]]
===== گراف =====
برای نگه‌داری گراف از داده‌ساختارهای زیر می‌توان استفاده کرد:
  * ماتریس مجاورت: آرایه دو بعدی که هر بعد آن به تعداد رأسها است و درایه‌ی $[i][j]$ آن وزن یال بین رأسهای $i$ و $j$ است و اگر چنین یالی وجود نداشته باشد مقداری مانند $-1$ است.
  * لیست مجاورت: آرایه‌ای از $vector$‌ها یا مانند آن به طول تعداد رأسها (یا یکی بیشتر در صورت شماره‌گذاری از ۱) که در هر درایه از آرایه، لیست رأسهای مجاور رأس متناظر آن درایه است.
  * لیست یالها: یک آرایه یا $vector$ که هر درایه‌ی آن یک $pair$ (زوج مرتب) است یا یک آرایه دوبعدی که بعد دوم آن دو عضو دارد. در هر درایه (یا سطر آرایه در روش دوم) شماره دو رأس متصل به هم نگه‌داری می‌شوند. برای نسخه‌ی وزن دار می‌توان یکی به بعد دوم آرایه اضافه کرد یا به جای زوج مرتب از چندتایی مرتب استفاده کرد.

گاهی لازم است قبل از ساخت این ساختمان داده‌ها، رأسها را به اعداد صحیح $0,...,n-1$ یا $1,...,n$ تصویر کنیم. (با استفاده از تابع $map$). همچنین گاهی لازم است بیشتر از یکی از این داده‌ساختارها را برای حل یک مسأله بسازیم.
===== مسایل نمونه از مجموعه‌های مجزا =====
۱-حسن $N\ (1\leq N \leq 100000)$ گاو دارد که خودشان را به صورت «گاوهای همسایه» گروه‌بندی می‌کنند. هر گاو در یک مختص یکتا در یک دستگاه مختصات متعامد در چراگاهی است که مختصات $X$ و $Y$ آن در بازه $1...1000000000$ قرار دارد. دو گاو همسایه‌اند، اگر حداقل یکی از این دو شرط را داشته باشند: ۱) اگر فاصله‌ی منهتن آنها حداکثر $C\ (1\leq C \leq 1000000000)$ باشد؛ ۲) اگر گاو $A$ و $B$ هر دو همسایه‌ی گاو $Z$ باشند، $A$ همسایه‌ی $B$ هم هست. مختصات گاوها و فاصله‌ی $C$ داده شده است، تعداد همسایگی‌ها و تعداد گاوها در بزرگترین همسایگی را مشخص کنید.

جواب: [[http://en.wikipedia.org/wiki/Taxicab_geometry|فاصله منهتن]] دو نقطه $(x_1,y_1)$ و $(x_2,y_2)$ برابر $|x_1-x_2|+|y_1-y_2|$ است. به ازای هر گاو یک عنصر در مجموعه‌های مجزا در نظر می‌گیریم. اگر دو گاو فاصله‌شان در شرط ۱ صدق کند، همسایگی آنها را ادغام می‌کنیم. شرط ۲ خود به خود به دلیل خاصیت مجموعه‌ای داده‌ساختار مجموعه‌های مجزا برقرار می‌شود. تعداد مجموعه‌ها (=تعداد رأسهای ریشه = تعداد رأسهایی که خودشان پدر خودشان هستند) و بیشینه‌ی تعداد اعضای هر مجموعه را که در آرایه‌ی سایز (برای تشخیص نحوه‌ی ادغام دو مجموعه) نگه داشتیم، برمی‌گردانیم.

۲-درختی با $N\ (1\leq N \leq 15000)$ رأس داده شده است، گراف کامل (گرافی که بین هر دو رأس آن یک یال است) با کمترین وزن را پیدا کنید که درخت داده شده، درخت پوشای کمینه‌ی منحصر به فرد آن باشد.

جواب: مجموعه‌ی رأسها را در داده‌ساختار مجموعه‌های مجزا می‌گذاریم و مشابه [[الگوریتم:درخت_پوشای_کمینه|الگوریتم کراسکال]]، یالهای درخت را اضافه می‌کنیم و ادغام انجام می‌دهیم. هر بار که یک یال را با یال دیگری ادغام می‌کنیم، باید سایر یالهای بین اعضای دو مجموعه از این مقدار بیشتر باشند، بنابراین مقدار آنها را به این مقدار افزایش می‌دهیم. در پایان چون الگوریتم کراسکال درخت پوشای کمینه را برمی‌گرداند، جواب تغییری نمی‌کند. پایان الگوریتم وقتی است که همه‌ی رأسها در یک مجموعه قرار گرفته باشند.

۳- دنباله‌ی $A$ از $N\ (1\leq N\leq 100000)$ عدد صحیح نامنفی داده شده است. به $Q\ (1\leq Q \leq 100000)$ پرس‌و‌جو پاسخ دهید که در هر کدام سه عدد صحیح $v,a,b$ است. جواب تعداد زوج اعداد صحیح $i$ و $j$ است که $1\leq i \leq j \leq N$ و $a\leq j-i+1\leq b$ باشد و به ازای هر عدد صحیح $k$ بین $i$ و $j$ (شامل دو سر بازه) $A[k]\geq v$ باشد.

جواب: راهنمایی: به ازای هر پرس‌و‌جو یک داده‌ساختار مجموعه‌های مجزا بسازید و بر اساس قیدهای داده شده به آن یال اضافه کنید.

[[http://activities.tjhsst.edu/sct/lectures/1314/union_find_12_13_13.pdf|منبع سوالات]]
مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

ابزار کاربر

ابزار سایت

ابزار صفحه
