مسابقه تمام شد!
امیدواریم از سوالا خوشتون اومده باشه 😉
راه حل سوالات در ادامه مطلب
مبنای شونزده
کافی است ، اولین رقم (از سمت راست) غیرِ F عدد رو پیدا کنیم ، این رقم یکی زیاد میشه ، ارقام سمت راست این رقم(که منطقا همگی F بوده اند) ، صفر می شوند و بقیه رشته بی تغییر می ماند .
تنها باید حالتی که کل رشته F باشد هم جدا بررسی شود .
پیچیدگی : O(n)
C++ Code By Sa1378
C++ Code By Navick
حرکت روی ظروف
در انتها قرار است میانگین مقدار آب سه ظرف در هر ظرف قرار گیرد .
سه حالت متصور است .
1) هر سه ظرف مقدار یکسانی آب داشته باشند که به وضوح پاسخ صفر است .
2)یکی از ظروف مقدار میانگین سه ظرف را داشته باشد ، بدیهی است که در این حالت پاسخ مسئله یک است چرا که با برابر کردن مقدار دو ظرف دیگر ، هر سه یکسان می شوند .
3)هیچ یک از حالات بالا نباشد ، که در این حالت جواب 2 است (قطعا نمی تواند پاسخ صفر یا یک باشد)
اکنون کافی است ، روشی ارائه دهیم که با دو حرکت شرایط برقرار شود : ابتدا دو ظرف با مقدار آب بیشتر را در نظر میگیریم و یکی را میانگین می کنیم ،سپس این ظرف را کنار گذاشته و دو ظرف دیگر را در نظر گرفته و آن ها را نیز باهم برابر می کنیم .
پیچیدگی : O(1)
C++ Code By Sa1378
C++ Code By Navick
اکبرجوجه
از راس یک در درخت dfs می زنیم .
مقدار dp[i] رو برابر جواب مسئله برای زیردرخت راس i در نظر بگیرید ، بنابر این تعریف پاسخ مسئله برابر dp[1] می باشد .
می خواهیم مقدار dp[i] ، را محاسبه کنیم .
حالات زیر را در نظر میگیریم .
1)راس i خود در مجموعه باشد : در این صورت هیچ راس دیگری نمی توانیم انتخاب کنیم (دقیقا یک حالت)
2)راس i در مجموعه نباشد : اکنون زیر درخت های بچه های راس i ، کلا تاثیری بر روی یکدیگر ندارند ، پس در این حالت پاسخ مسئله برابر ضرب dp[j] هاست که j بچه i باشد .
پس این مقدار براحتی محاسبه می شود .
پیچیدگی : O(n)
C++ Code By Sa1378
C++ Code By Navick
درخت کسرا
کسر \frac {a} {b} را در نظر بگیرید. پدر او یکی از کسر های زیر میتواند باشد:
\frac {a-b} {b} , \frac {a} {b-a}
که بسته به این که کدام یکی از a و b بزرگتر است یکی منفی و دیگری مثبت میشود. پس یکتا تعیین میشود.
حال فرض کنید b \le a باشد. تا وقتی که b \le a بماند a منهای b میشود.
پس از کسر \frac {a} {b} به کسر \frac {a \mod b} {b} میرسیم.
با بررسی هر دو حالت به این نتیجه میرسیم که از کسر \frac {a} {b} به کسر \frac {a \mod b} {b \mod a} با طی کردن max( \frac{a}{b} , \frac{b}{a}) یال میرسیم.
انقدر این کار را انجام میدهیم تا a=b بشود که به راس ریشه رسیده ایم.
پیچیدگی: O(Q\times(\log{p_{i}}+\log{q_{i}}))
C++ Code By AmSen
C++ Code By Sa1378
دنباله ولایی
میدانیم که عدد اول دنباله باید ناصفر باشد. حال فرض کنیم تعداد اعداد مثبت آرایه بجز عدد اول p باشد، میدانیم که جمع اعداد آرایه بجز عدد اول برابر به p+1 است، پس بجز عدد اول، در بقیه اعداد یک عدد 2 داریم و بقیه اعداد مثبت 1 اند. همچنین p\leq3 زیرا اگر p>3 باشد آنگاه عدد 1، سه بار تکرار شده که نتیجه میدهد a_{1} برابر با 3 است که خلاف فرض است.
حال روی p حالت بندی میکنیم.
به ازای p=1 تنها حالت رشته‌ی 2,0,2,0 است.
به ازای p=2 هم رشته‌ها 1,2,1,0 و 2,1,2,0,0 اند.
به ازای p=3 رشته به صورت X,2,1,0,0,...,0,1,0,0,0 است که تعداد صفر های بین دو عدد 1، برابر با X-3 است.
پیچیدگی : O(n)
C++ Code By Sa1378
تابع
فرض کنید a_{i} ارتفاع ساختمان i باشد.
f(l,r) برابر با ماکسیمم بنر بین ساختمان های l تا r میشود.
حال عدد a_{i} را در نظر بگیرید. فرض کنید این عدد در بازه [L,R] مینیمم باشد. طول ماکسمیم بنری که ارتفاعش a_{i} باشد برابر ماکسیمم اشتراک [l_{i},r_{i}] ها با [L,R] است. که با O(n\log^2{n}) به دست می آید.
برای حل سوال با O(n\log{n}) ابتدا باید بین بازه هایی که l_{i}\le L هست ماکسیمم r_{i} را بدست آورد. فرض کنید این عدد x باشد. تمام بازه هایی که r_{i} آنها در بازه (x,R] هست l_{i} آنها بزرگترمساوی L است.
برای بدست آوردن x میتوان با پارشیال ماکسیمم با O(1) به دست آورد و برای ماکسیمم طوله بقیه بازه ها میتوان با سگمنت ، ماکسیمم طوله بازه هایی که r_{i} اشان بین (x,R] هست بدست آورد. و در کل با O(n\log{n}) حل میشود.
پیچیدگی: O(n\log{n})
C++ Code By AmSen
عدد بوگندوی رشته‌ی خفن
درخواست ها را ذخیره کرده و آنها را آفلاین جواب میدهیم.
تابع solve(xl,xr) را میسازیم و mid را \frac {xl+xr} {2} تعریف میکنیم. تابع solve(xl,xr) که درخواست هایی که l آنها از mid کمتر، و r آنها از mid بیشترمساوی است را جواب میدهد و سپس solve(xl,mid) و solve(mid,xr) را صدا میزند.
برای جواب دادن درخواست ها برای بازه‌ی [mid,xr) به ازای تمام prefix هایش OR رشته هارا در bitset ذخیره میکنیم و همچنین برای بازه‌ی [xl,mid) هم به ازای تمام suffix هایش این کار را انجام میدهیم.
حال هر درخواست که خاصیتی که در ابتدا گفتیم را داشت را میتوان با OR گرفتن دوتا از bitset ها جواب داد.
پیچیدگی : O(qlgn+qk/32+nklgn/32)
C++ Code By Sa1378
C++ Code By Navick
