لیته پس از این که در همکاری با فیته به موفقیت نرسید، تصمیم گرفت که از اینجا به بعد با…
- User
لیته پس از این که در همکاری با فیته به موفقیت نرسید، تصمیم گرفت که از اینجا به بعد با نیوفیته همکاری کند. نیوفیته از این اتفاق بسیار خرسند است اما برای این که کسی شک نکند ابتدا از لیته خواسته تا یک مسئلهی سخت را برایش حل کند، متاسفانه لیته با تمام مهارتی که در حل مسائل الگوریتمی دارد، این بار نیازمند کمکهای شایان شماست تا در همکاریاش با نیوفیته با شکست مواجه نشود.
در این مسئله دنبالهای از اعداد صحیح به طول n n به شما داده میشود و شما باید با حداقل تعداد عملیات ممکن همهی اعداد دنباله را تبدیل به صفر کنید. اعداد این دنباله از چپ به راست a 1 a 1 تا a n a n نامیده میشوند.
هر عملیات به این صورت است که ابتدا یک بازه از دنباله مانند [ l , r ) [l,r) انتخاب میکنید و از همهی اعضای این بازه ۱ واحد کم میکنید. ( 1 ≤ l < r ≤ n + 1 1≤l<r≤n+1)
طول هر بازه که انتخاب میکنید باید توانی از ۲ باشد. هر بازه حداکثر ۱ بار میتواند انتخاب شود. اگر دو بازهی انتخاب شده مانند [ l 2 , r 2 ) [l 2 ,r 2 ) و [ l 1 , r 1 ) [l 1 ,r 1 ) وجود داشته باشند که اشتراکشان تهی نباشد، آنگاه m a x ( l 1 − l 2 , l 2 − l 1 ) max(l 1 −l 2 ,l 2 −l 1 ) باید مضربی از m i n ( r 1 − l 1 , r 2 − l 2 ) min(r 1 −l 1 ,r 2 −l 2 ) باشد. ورودی در خط اول ورودی، عدد طبیعی n n آمدهاست که طول دنباله را نشان میدهد.
در خط بعدی، n n عدد حسابی آمده است که به ترتیب a 1 a 1 تا a n a n را نشان میدهند.
1 ≤ n ≤ 1 0 5 1≤n≤10 5
0 ≤ a i ≤ 1 0 5 ( 1 ≤ i ≤ n ) 0≤a i ≤10 5 (1≤i≤n)
خروجی در تنها خط خروجی، حداقل تعداد عملیات برای این که همهی اعداد دنباله به صفر تبدیل شوند را چاپ کنید و در صورتی که این کار با عملیاتهای گفته شده امکان پذیر نیست عدد − 1 −1 را چاپ کنید.
زیرمسئلهها زیرمسئله نمره محدودیت ۱ ۳۰ 1 ≤ n ≤ 600 1≤n≤600 ۲ ۷۰ بدون محدودیت اضافی مثال ورودی نمونه ۱ 10 1 1 1 1 2 2 2 3 2 1 Plain text خروجی نمونه ۱ 5 Plain text ورودی نمونه ۲ 8 2 2 2 0 1 1 2 2 Plain text خروجی نمونه ۲ -1 python
- Assistant
برای حل این مسئله، باید به چند نکته کلیدی دقت کنیم:
-
بازهها و توانهای دو: هر بازهای که انتخاب میکنیم باید طولی به اندازه توان دو داشته باشد. این یعنی ممکن است بازههای با طول 1، 2، 4، 8، ... و تا نزدیکترین توان دو به n را انتخاب کنیم.
-
شرایط انتخاب بازهها: اگر بازهای را انتخاب میکنیم، نمیتوانیم بازهی همپوشان دیگری انتخاب کنیم مگر اینکه شرط مسأله برآورده شود.
-
مسیر کاهش اعداد: برای هر عدد در دنباله باید تصمیم گرفته شود که از کدام توالیهای کاهشی استفاده کنیم تا تعداد کل عملیاتها به حداقل برسد.
-
بررسی امکانپذیری: ابتدا باید بررسی کنیم آیا با توانهای دو میتوانیم دنباله را به صفر رساند یا خیر.
روش کلی برای حل این مسئله به صورت زیر است:
-
ایجاد پویایی دوجانبه: از یک الگوریتم پویا برای انتخاب بهینه بازهها استفاده میکنیم، به طوری که اولویت با کاهش توالیهای بلندتر و توانهای بزرگتر باشد زیرا تأثیر بیشتری دارند.
-
حرکت به پیش و به عقب در دنباله: با استفاده از تکنیکهای حرکت به پیش و به عقب، شرایط مختلف کاهشی را بررسی میکنیم و سعی میکنیم بیشترین بازهها را همزمان انتخاب کنیم.
-
تطبیق استخراجی (Greedy Matching): با تطابق بازهها و اعداد موجود، میتوانیم تعیین کنیم که آیا میتوانیم تمام اعداد را به صفر برسانیم یا خیر.
-
پیادهسازی الگوریتم: در ادامه یک پیادهسازی ممکن از این الگوریتم آورده شده است:
def min_operations_to_zero(n, sequence): if n == 0: return 0 # بررسی کردن توانی از دوها powers_of_two = [] p = 1 while p <= n: powers_of_two.append(p) p *= 2 # ایجاد یک لیست برای ذخیره حداقل عملیات برای رساندن هر بازه به صفر ops = [float('inf')] * (n + 1) ops[0] = 0 # پیمایش دنباله و محاسبه حداقل عملیات for i in range(1, n + 1): for p in powers_of_two: if i - p < 0: break max_in_range = max(sequence[i-p:i]) ops[i] = min(ops[i], ops[i-p] + max_in_range) return ops[n] if ops[n] != float('inf') else -1 # مثالی برای تست n = 10 sequence = [1, 1, 1, 1, 2, 2, 2, 3, 2, 1] result = min_operations_to_zero(n, sequence) print(result)این الگوریتم به گونهای طراحی شده است که به صورت پویا و تطبیقی، مناسبترین بازههای کاهشی را برای هر نقطه در دنباله انتخاب کند تا تعداد عملیاتها به حداقل برسد. این کارایی با استفاده از تکنیکهای برنامهنویسی پویا و جستجو در مقیاس بزرگ (O(n log n)) پیادهسازی شده است.
-
- User
روحا... پس از چندین سال تجربه در المپیاد، فهمید که «نون توی گله!»
بنابراین تصمیم گرفت باغچهای اجاره کند و در آن گلهای زیبا بکارد و پس از آن که رشد کردند، آنها را به مردم بفروشد.
باغچهای که او اجاره کرد به شکل یک مستطیل n n در m m است. این مستطیل را به شکل جدولی در نظر بگیرید که n n سطر و m m ستون دارد و در هر خانه از آن جدول میتوان یک گل کاشت. سطرهای جدول به ترتیب از بالا به پایین با 1 1 تا n n و ستونهای جدول از چپ به راست به ترتیب با 1 1 تا m m شمارهگذاری شدهاند.
گلهای مورد نظر روحا... 26 26 نوع دارند. هر یک از این انواع را با یکی از حروف A A تا Z Z نمایش میدهیم. همچنین او میخواهد در سطر i iام باغچهاش گلهایی را بکارد که با رشتهای به نام s i s i نمایششان میدهیم. ممکن است طول این رشته از m m کمتر باشد. در این صورت او مجبور است تعدادی از خانههای باغچه را در آن سطر خالی بگذارد. برای او فقط ترتیب گلها در هر سطر مهم است. یعنی اگر خانههای خالی سطر i iام را حذف کنیم و به ازای خانههای باقیمانده به ترتیب از چپ به راست نوعشان را بنویسیم، رشتهای برابر s i s i حاصل خواهد شد.
از نظر روحا... هر باغچه یک مقدار شادابی دارد! شادابی یک روش از کاشتن گلها، برابر تعداد جفت خانههای مجاور ضلعی است که نوع گل کاشته شده در آنها یکسان باشد.
مثلا اگر یک جدول 2 × 2 2×2 داشته باشیم و s 1
s 2
A s 1 =s 2 =A باشد، اگر گلها را در خانهی اوّل سطر اوّل و خانهی دوم سطر دوم بکاریم، شادابی برابر 0 0 میشود. امّا اگر آنها را در خانههای دوم دو سطر بکاریم، شادابی باغچهی حاصل برابر 1 1 میشود. همچنین اگر s 1
A A s 1 =AA و s 2
B B s 2 =BB باشد، روحا... فقط به یک طریق میتواند گلها را بکارد و شادابی حاصل نیز برابر 2 2 خواهد بود.
روحا... میخواهد طوری گلها را بکارد که با شرایط مذکور، شادابی باغچه بیشینه شود. امّا او که از المپیاد کنارهگیری کردهاست، به نظرش این سوال خیلی المپیادی است و از شما میخواهد حلش کنید.
ورودی در سطر اوّل 2 2 عدد n n و m m آمدهاند. در هر یک از n n سطر بعد، یک رشتهی ناتهی شامل حروف A A تا Z Z آمدهاست که i iامین رشته، نمایانگر s i s i است.
1 ≤ n ≤ 128 1≤n≤128 1 ≤ m ≤ 16 1≤m≤16 1 ≤ ∣ s i ∣ ≤ m 1≤∣s i ∣≤m خروجی در تنها سطر خروجی، بیشینه شادابی ممکن باغچه را چاپ کنید.
زیر مسئله ها زیرمسئله نمره محدودیت ها ۱ ۱۱ n ≤ 100 , m ≤ 8 n≤100,m≤8 ۲ ۱۳ n ≤ 100 , m ≤ 11 n≤100,m≤11 ۳ ۷۶ بدون محدودیت اضافی مثال ورودی نمونه ۱ 1 1 B Plain text خروجی نمونه ۱ 0 Plain text ورودی نمونه ۲ 2 12 A B Plain text خروجی نمونه ۲ 0 Plain text ورودی نمونه ۳ 3 3 B AB A Plain text خروجی نمونه ۳ 2
- Assistant
برای حل این مسئله، باید گلها را در جدول طوری بکاریم که شادابی حداکثری حاصل شود. این مسئله ترکیبی از چینشها و ذخیرهسازی بهینه است. با توجه به محدودیتهایی که در اندازه m و n داریم، این مسئله را میتوان با استفاده از برنامهنویسی پویا (Dynamic Programming) حل کرد.
رویکرد برنامهنویسی پویا (Dynamic Programming):
برای هر سطر، باید اشکالی که میتوانیم گلها را در آن بکاریم سازماندهی کنیم. برای این کار، باید بتوانیم گلها را به شکلهای ممکن چینش کنیم و تعداد جفتهای گل مشابه را در میان سطرها محاسبه کنیم.
شرح الگوریتم:
-
پایهگذاری الگوریتم دینامیک:
- تعریف متغیر dp به شکلی که dp[i][mask_i] نشان دهنده بیشینه شادابی است وقتی که تاکنون i سطر را پردازش کردهایم و در سطر i چینش mask_i را انتخاب کردهایم.
-
محاسبه تغییر حالتها (Transition Calculation):
- برای هر سطر i و هر کدام از چینشهای ممکن برای mask_i:
- برای حالتهای قبلی، محاسبه کنیم که چه میزان شادابی بیشتری میتوانیم با ترکیب حالتهای قبلی به دست آوریم.
- شادابی را میتوان با محاسبه تعداد جفتهای مشابه عمودی و افقی که بین سطر i و سطر i+1 برقرار است محاسبه کرد.
- برای هر سطر i و هر کدام از چینشهای ممکن برای mask_i:
-
محاسبه شادابی تمامی سطرها (Iterate Over Rows):
- با استفاده از حلقهها برای پردازش هر سطر و بررسی تمامی چینشهای ممکن.
- در صورت امکان، برای هر تغییر حالت، شادابی جدید را محاسبه و ذخیره میکنیم.
-
محاسبه بیشینه شادابی (Compute Maximum Freshness):
- در انتها، حداکثر شادابی محاسبه شده را برای آخرین سطر استخراج میکنیم.
مثال کدی برای پیادهسازی این ایده میتواند به صورت زیر باشد:
def max_freshness(n, m, rows): # پاس می دیم به dp maskشده های قبلی به خودمون برمیگردونه from itertools import combinations def get_bitmask(row, m): return [tuple(row[i] for i in comb) for comb in combinations(range(m), len(row))] def count_adjacent_pairs(a, b): return sum(x == y for x, y in zip(a, b)) if b else 0 dp = {} # پردازش لیست های هر سطر mask for mask in get_bitmask(rows[0], m): dp[mask] = (count_adjacent_pairs(mask, mask),) for i in range(1, n): ndp = {} for mask in get_bitmask(rows[i], m): max_freshness_so_far = -1 for prev_mask, freshness in dp.items(): curr_freshness = freshness[0] + count_adjacent_pairs(mask, prev_mask) if mask in ndp: ndp[mask] = max(ndp[mask], (curr_freshness,)) else: ndp[mask] = (curr_freshness,) dp = ndp return max(freshness[0] for freshness in dp.values()) # مثال تست n = 3 m = 3 rows = ["B", "AB", "A"] print(max_freshness(n, m, rows))توضیحات:
- در این کد، از روشهای دامنهای (Combinatorial) برای تولید چینشهای ممکن استفاده شده است.
- شادابی بهینه با استفاده از شمارش جفتهای همسان با روشهای DP محاسبه میشود.
- این پیادهسازی با استفاده از مقادیر توانهای کوچک محاسبه میشود تا چینش بهینه برای سطر فعلی به دست آید.
-
- User
گاز تعداد زیادی نوار کاست قدیمی دارد که آنها را در یک ردیف چیده و به ترتیب از ۱ تا n n نامگذاری کرده است. گزل که از دیدن این تعداد نوار کاست حیرتزده شده از گاز میخواهد که اجازه دهد با نوارها بازی کند. گاز قبول میکند. سپس همهی آنها را برعکس میکند جوری که گزل شماره آنها را نبیند و به او میگوید که در هر مرحله یک از دو کار زیر را از تو میخواهم:
ترتیب قرار گرفتن نوارهای جایگاه i iام تا j jام را برعکس کنی. شماره نوار در جایگاه k kام را به من بگویی. شما باید برنامهای بنویسید که با دریافت تعداد کاستها و دنباله کارهای فوق به گزل کمک کند که کارهای خواستهشده را انجام دهد و به پرسشهای گاز به درستی پاسخ دهد.
ورودی در خط اول ورودی عدد n ≤ 1 0 6 n≤10 6 تعداد نوارهای کاست وارد میشود. سپس عدد m ≤ 1 0 4 m≤10 4 که تعداد مرحلههای بازیست وارد میشود و سپس در m m خط بعد در هر خط یکی از دو ورودی REV i j که نشاندهندهی خواسته اول است و یا NAME K که نشاندهندهی خواستهی دوم است آورده میشود.
خروجی به ازای هر پرسش NAME k شماره کاست در جایگاه k k را چاپ کنید.
مثال ورودی نمونه ۱ 10 5 NAME 1 REV 1 10 NAME 2 REV 3 7 NAME 6 Plain text خروجی نمونه ۱ 1 9 7
- Assistant
برای حل این مسئله، باید دو عملیات معکوس کردن بخشی از دنباله و به دست آوردن شماره کاست در یک موقعیت مشخص را پیادهسازی کنیم. با توجه به محدودیتهای مسئله، استفاده از روشهای غیرفعال مانند تغییر مستقیم دنباله در هر مرحله، دارای پیچیدگی زمانی بالایی است و کارا نخواهد بود.
برای مدیریت این عملیات به طور کارا، میتوان از یک استراتژی هوشمند برای ردیابی وضعیت دنباله نوارها استفاده کرد. فرض کنید دنباله اولیه به این صورت باشد:
[1, 2, 3, ..., n]. هر بار که یک زیرآرایه را معکوس میکنید، باید به گونهای این تغییرات را ردیابی کنید که در زمان ارائه پاسخ به کوئریNAME kبتوانید شماره درست نوار را به سرعت ارائه دهید.یکی از رویکردها استفاده از مفهوم "محدودیتهای رویدادگذاری" (lazy propagation) است که به شما اجازه میدهد تا عملیاتهای معکوس را به صورت تجمعی حفظ کنید و به جای اعمال کردن آنها در لحظه، آنها را زمانی که نیاز داشتید، اعمال کنید.
با این استراتژی، میتوانید عملیاتهایی از نوع معکوس را تا زمانی که لازم است، به تعویق بیندازید و در عوض تغییرات را هوشمندانه محاسبه کنید.
پیادهسازی:
# تابع برای حل مسئله def solve(n, operations): reverse_segments = [] # پردازش عملیات و پاسخ به کوئریها for operation in operations: if operation[0] == "REV": i, j = int(operation[1]), int(operation[2]) reverse_segments.append((i - 1, j - 1)) elif operation[0] == "NAME": k = int(operation[1]) - 1 original_index = k # اعمال معکوسهای ذخیرهشده بر روی شاخص داده شده for segment in reversed(reverse_segments): i, j = segment if i <= original_index <= j: original_index = i + j - original_index # نتیجه چاپ کنید print(original_index + 1) # نمونه ورودیها n = 10 operations = [ ("NAME", "1"), ("REV", "1", "10"), ("NAME", "2"), ("REV", "3", "7"), ("NAME", "6") ] solve(n, operations)توضیحات:
reverse_segmentsلیستی است که پیدا میکند کدام زیرآرایه باید معکوس شود و از کجا تا کجا.- برای هر کوئری
NAME k، تمام معکوسهایی که در آینده وجود خواهند داشت را بررسی میکنیم و شاخص کنونی را محاسبه میکنیم. - این روش به ما اجازه میدهد تا به طور مؤثری بدون نیاز به بازنویسی کل دنباله در هر مرحله، شاخصها را معکوس کنیم. بدین ترتیب، عملکرد برنامه به طور چشمگیری بهبود مییابد و پیچیدگی زمانی در حد قابل قبولی باقی میماند.
- User
c++
- Assistant
برای حل این مسئله در C++ با توجه به محدودیتها و نیاز به پشتیبانی از عملیات معکوس و ارجاع به موقعیت نوارها، میتوانیم از یک رویکرد مشابه استفاده کنیم. ایده اصلی همچنان حفظ "محدودیتهای رویدادگذاری" برای معکوسها است. ما میخواهیم از یک بردار برای ذخیره معکوسهای انجامشده استفاده کنیم و سپس این اطلاعات را برای پاسخ به کوئریهای
NAME kبه کار بریم.در زیر، یک پیادهسازی ساده از این ایدهها در زبان C++ ارائه شده است:
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, m; cin >> n >> m; vector<pair<int, int>> reverse_segments; vector<string> operations(m); // خواندن عملیاتها for (int i = 0; i < m; i++) { string op; cin >> op; operations[i] = op; if (op == "REV") { int start, end; cin >> start >> end; reverse_segments.push_back({start - 1, end - 1}); } else if (op == "NAME") { int k; cin >> k; operations[i] += " " + to_string(k); } } // پردازش عملیاتها for (int i = 0; i < m; i++) { if (operations[i].substr(0, 4) == "NAME") { int k = stoi(operations[i].substr(5)) - 1; int original_index = k; // اعمال معکوسها بر روی شاخص دادهشده for (int j = reverse_segments.size() - 1; j >= 0; j--) { int start = reverse_segments[j].first; int end = reverse_segments[j].second; if (start <= original_index && original_index <= end) { original_index = start + end - original_index; } } cout << original_index + 1 << endl; } } return 0; }توضیحات:
-
ورودی و خروجی:
- تعداد نوارها
nو تعداد عملیاتmرا میخوانیم. - هر عملیات را ذخیره و عملیاتهای
REVرا به عنوان جفتی از مکانها در یک بردارreverse_segmentsذخیره میکنیم. کوئریهایNAMEمستقیماً پردازش خواهند شد.
- تعداد نوارها
-
پردازش کوئریهای
NAME:- برای هر کوئری
NAME k، شاخص اصلیk-1را تعیین کرده و سپس تمامی مقاطع معکوس موجود را در ترتیب معکوس بررسی میکنیم. - اگر شاخص در محدودهای باشد که برعکس شده، محاسبه میکنیم که شاخص جدید چه خواهد بود.
- برای هر کوئری
-
پیچیدگی زمانی:
- برای هر کوئری
NAME k، حداکثر زمان مورد نیاز برابر با تعداد مقاطع معکوس ذخیرهشده است که بدین ترتیب پیچیدگی زمانی به صورتO(m * r)میباشد، جایی کهrتعداد معکوسها (عملیاتREV) است. با توجه به محدودیتهای مسئله، این روش کارا میباشد.
- برای هر کوئری
-
- User
یک دنباله از اعداد صحیح و مثبت مثل a 1 , a 2 , … , a n , a 1 ,a 2 ,…,a n , داریم. q q درخواست داریم که باید آنها را بهترتیب انجام دهیم:
درخواست نوع اول + , , i d x , , v a l +,,idx,,val
در این درخواست از شما میخواهیم مقدار a i d x a idx را به v a l val تغییر بده.
درخواست نوع دوم ? , , l , , r ?,,l,,r
در این درخواست از شما میخواهیم بررسی کنید آیا بازه a l , … , a r a l ,…,a r تشکیل یک جایگشت از اعداد 1 1 تا r − l + 1 r−l+1 میدهد یا خیر.
ورودی در سطر اول ورودی، دو عدد صحیح و مثبت n n و q q با یک فاصله از هم جداشدهاند، آمده است. 1 ≤ n , q ≤ 100
000 1≤n,q≤100 000
در سطر دوم، n n عدد صحیح و مثبت که نشان دهندهی مقدارهای a 1 , a 2 , … , a n , a 1 ,a 2 ,…,a n , است. 1 ≤ a i ≤ n 1≤a i ≤n
در q q سطر بعدی، در هر سطر، یکی از دو نوع دستور گفته شده در سوال میآید.
اگر درخواست از نوع اول باشد، در یک سطر ابتدا کاراکتر + میآید، سپس با یک فاصله دو عدد صحیح i d x idx و v a l val داده میشود.
1 ≤ i d x , v a l ≤ n 1≤idx,val≤n
اگر درخواست از نوع دوم باشد، در یک سطر ابتدا کاراکتر ? میآید، سپس با یک فاصله دو عدد صحیح l l و r r داده میشود.
1 ≤ l ≤ r ≤ n 1≤l≤r≤n
خروجی تعداد سطرهای خروجی، به تعداد درخواستهای نوع دوم است. در صورت تشکیل جایگشت در بازه آن درخواست، عبارت YES و در صورت جایگشت نبودن آن، عبارتNO را چاپ کنید.
مثال ورودی نمونه ۱ 3 6 1 3 2 ? 1 2 ? 1 3
- 2 2 ? 1 2
- 3 1 ? 2 3 Plain text خروجی نمونه ۱ NO YES YES YES Plain text ورودی نمونه ۲ 5 5 1 2 1 2 1 ? 3 5
- 3 3 ? 1 3 ? 3 5 ? 2 4 Plain text خروجی نمونه ۲ NO YES YES NO c++
- Assistant
برای حل این مسئله در C++ با توجه به تعداد زیادی از دادهها (n و q تا 100,000) و درخواستها، نیاز به یک راه حل کارا داریم که بتواند هر پرسش از نوع دوم را به سرعت پاسخ دهد. برای این منظور، از ترکیب تکنیکهای ساختار دادههای فشرده و تکنیکهای کارا برای بهروزرسانی و کوئری، مانند ساختار
متاسگمنت(Segment Tree) یافنویک درخت(Fenwick Tree) استفاده خواهیم کرد.در اینجا، قصد داریم از یک رویکرد سادهتر برای بررسی امکان جایگشت در بازه استفاده کنیم.
ایده اصلی برای حل:
-
درخواست جایگشت (Permutation Check):
- در درخواستهای نوع دوم به منظور چک کردن اینکه آیا یک بازه
[l, r]تشکیل یک جایگشت از اعداد 1 تاr-l+1میدهد یا خیر، کافیست بررسی کنیم که:- تمامی اعداد بین 1 و
r-l+1هستند. - هیچ عنصری تکراری در بازه وجود ندارد.
- تمامی اعداد بین 1 و
- در درخواستهای نوع دوم به منظور چک کردن اینکه آیا یک بازه
-
درخواست بهروزرسانی (Update):
- به سادگی مقدار را بهروز رسانی کرده و در آرایه اصلی تغییرات را انجام میدهیم.
پیادهسازی:
#include <iostream> #include <vector> #include <unordered_set> using namespace std; // تابع اصلی int main() { ios::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; vector<int> arr(n + 1); // آرایه اصلی، از اندیس 1 شروع میکنیم برای راحتی کار for (int i = 1; i <= n; i++) { cin >> arr[i]; } while (q--) { char type; cin >> type; if (type == '+') { int idx, val; cin >> idx >> val; arr[idx] = val; // بهروز رسانی انجام دهیم } else if (type == '?') { int l, r; cin >> l >> r; // چک کنیم آیا بازه یک جایگشت است یا خیر unordered_set<int> s; bool is_permutation = true; for (int i = l; i <= r; i++) { if (arr[i] < 1 || arr[i] > r - l + 1 || s.count(arr[i])) { is_permutation = false; break; } s.insert(arr[i]); } cout << (is_permutation ? "YES" : "NO") << endl; } } return 0; }توضیحات:
- وارد کردن دادهها: دادهها به صورت آرایه یکبعدی
arrوارد میشوند. - عملیات
+(بهروزرسانی): به سادگی مقدار آرایه در اندیس مشخص شده تغییر میدهد. - عملیات
?(چک کردن جایگشت):- از یک
unordered_setبرای حل کردن مشکل تکراری شدن عناصر استفاده میکنیم. - بررسی میکنیم که آیا همه عناصر در محدوده 1 تا
(r - l + 1)قرار دارند و تکراری نیستند.
- از یک
این رویکرد به ما اجازه میدهد که هر دو نوع درخواست را به طور کارا پردازش کنیم.
-
- User
یک دنباله از اعداد صحیح و مثبت مثل a 1 , a 2 , … , a n , a 1 ,a 2 ,…,a n , داریم. q q درخواست داریم که باید آنها را بهترتیب انجام دهیم:
درخواست نوع اول + , , i d x , , v a l +,,idx,,val
در این درخواست از شما میخواهیم مقدار a i d x a idx را به v a l val تغییر بده.
درخواست نوع دوم ? , , l , , r ?,,l,,r
در این درخواست از شما میخواهیم بررسی کنید آیا بازه a l , … , a r a l ,…,a r تشکیل یک جایگشت از اعداد 1 1 تا r − l + 1 r−l+1 میدهد یا خیر.
ورودی در سطر اول ورودی، دو عدد صحیح و مثبت n n و q q با یک فاصله از هم جداشدهاند، آمده است. 1 ≤ n , q ≤ 100
000 1≤n,q≤100 000
در سطر دوم، n n عدد صحیح و مثبت که نشان دهندهی مقدارهای a 1 , a 2 , … , a n , a 1 ,a 2 ,…,a n , است. 1 ≤ a i ≤ n 1≤a i ≤n
در q q سطر بعدی، در هر سطر، یکی از دو نوع دستور گفته شده در سوال میآید.
اگر درخواست از نوع اول باشد، در یک سطر ابتدا کاراکتر + میآید، سپس با یک فاصله دو عدد صحیح i d x idx و v a l val داده میشود.
1 ≤ i d x , v a l ≤ n 1≤idx,val≤n
اگر درخواست از نوع دوم باشد، در یک سطر ابتدا کاراکتر ? میآید، سپس با یک فاصله دو عدد صحیح l l و r r داده میشود.
1 ≤ l ≤ r ≤ n 1≤l≤r≤n
خروجی تعداد سطرهای خروجی، به تعداد درخواستهای نوع دوم است. در صورت تشکیل جایگشت در بازه آن درخواست، عبارت YES و در صورت جایگشت نبودن آن، عبارتNO را چاپ کنید.
مثال ورودی نمونه ۱ 3 6 1 3 2 ? 1 2 ? 1 3
- 2 2 ? 1 2
- 3 1 ? 2 3 Plain text خروجی نمونه ۱ NO YES YES YES Plain text ورودی نمونه ۲ 5 5 1 2 1 2 1 ? 3 5
- 3 3 ? 1 3 ? 3 5 ? 2 4 Plain text خروجی نمونه ۲ NO YES YES NO c#
- Assistant
برای حل این مسئله در زبان C#، باید عملیاتهای بهروزرسانی و بررسی جایگشت را به طور کارا پیادهسازی کنیم. با توجه به محدودیت مشکل، راهکار مستقیم برای چک کردن جایگشت که برای هر کوئری از نوع
?کل بازه را بررسی کند ناکارآمد خواهد بود. بنابراین هدف استفاده از روشهایی با پیچیدگی زمانی بهتر است.در ارائهی راهکار، از یک روش ساده برای بررسی قابلیت تشکیل جایگشت استفاده میکنیم و برای عملیات بهروزرسانی نیز مستقیما آرایه را تغییر میدهیم.
در زیر پیادهسازی کد با استفاده از C# آمده است:
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { string[] inputs = Console.ReadLine().Split(); int n = int.Parse(inputs[0]); int q = int.Parse(inputs[1]); int[] array = Console.ReadLine().Split().Select(int.Parse).ToArray(); for (int i = 0; i < q; i++) { inputs = Console.ReadLine().Split(); char type = inputs[0][0]; if (type == '+') { int idx = int.Parse(inputs[1]); int val = int.Parse(inputs[2]); array[idx - 1] = val; // بهروزرسانی همان اندیس داده شده } else if (type == '?') { int l = int.Parse(inputs[1]); int r = int.Parse(inputs[2]); if (IsPermutation(array, l - 1, r - 1)) { Console.WriteLine("YES"); } else { Console.WriteLine("NO"); } } } } static bool IsPermutation(int[] arr, int l, int r) { int length = r - l + 1; HashSet<int> set = new HashSet<int>(); for (int i = l; i <= r; i++) { if (arr[i] < 1 || arr[i] > length || set.Contains(arr[i])) { return false; } set.Add(arr[i]); } return true; } }توضیحات:
- ورودی و خروجی: ابتدا تعداد نوارها و تعداد دستورات خوانده میشود. سپس مقادیر نوارها در یک آرایه ذخیره میشود.
- عملیات
+: برای بهروزرسانی مقدار در یک شاخص خاص استفاده میشود. - عملیات
?: چک میکند که بازه دادهشده یک جایگشت صحیح از اعداد 1 تا (طول بازه) است یا خیر. برای این منظور، از یکHashSetاستفاده میشود تا مطمئن شویم همه اعداد در محدوده 1 تا (طول بازه) غیرتکراری هستند. - استفاده از
HashSetبرای مدیریت عناصر در بازه ساده و کارآمد است؛ چرا که دسترسی و درج درHashSetبه صورت میانگین دارای پیچیدگی ثابتO(1)است.
این پیادهسازی به سادگی میتواند در محدودیت داده شده کار کند و از نظر زمانی بهینه است.
- User
python
- Assistant
برای پیادهسازی این مسئله در Python، باید بهینهترین روشها را برای دستیابی به پاسخهای کوئریها اتخاذ کنیم. به ویژه، به دلیل وجود محدودیتهای بالا روی شمار اعداد و تعداد درخواستها، باید از روشهایی با کارایی مناسب استفاده کنیم.
برای اجرای درخواستهای
+، مستقیم مقدار آرایه را در مکان داده شده بهروزرسانی میکنیم. برای درخواستهای?، بررسی میکنیم که آیا قسمت معینی از آرایه میتواند به عنوان یک جایگشت از اعداد 1 تا r-l+1 ظاهر شود؛ برای این کار، باید اطمینان حاصل کنیم که تمامی عناصر غیر تکراری بوده و در محدوده صحیح قرار دارند.در زیر پیادهسازی Python آمده است:
def solve(): import sys input = sys.stdin.readline # برای سریعتر کردن خواندن ورودیها n, q = map(int, input().split()) array = list(map(int, input().split())) for _ in range(q): query = input().strip().split() if query[0] == '+': idx = int(query[1]) - 1 val = int(query[2]) array[idx] = val elif query[0] == '?': l = int(query[1]) - 1 r = int(query[2]) - 1 length = r - l + 1 sub_array = array[l:r+1] if len(sub_array) != length: print("NO") continue # چک کنیم که آیا زیرآرایه یک جایگشت است یا خیر is_permutation = True seen = [False] * (length + 1) for num in sub_array: if num < 1 or num > length or seen[num]: is_permutation = False break seen[num] = True if is_permutation: print("YES") else: print("NO") solve()توضیحات:
- خواندن ورودیها: از
sys.stdin.readlineاستفاده شده تا ورودیها را سریعتر بخوانیم، به ویژه برای مقادیر بزرگ n و q. - عملیات
+: مستقیماً مقدار مشخصی از آرایه را بهروزرسانی میکند. - عملیات
?: یک زیرآرایه از آرایه را بررسی میکند و برای ارزیابی جایگشت، لیستی از حالتهای دیده شده برای اعداد از 1 تا طول بازه نگه میدارد. اگر همه اعداد در بازه مورد نظر وجود داشتند و تکراری نبودند، این زیرآرایه یک جایگشت است. - روش استفاده شده برای چک کردن جایگشت، از نظر زمانی بهینه است چون برای هر کوئری تعداد ثابتی عملیات انجام میدهد.
این کد به خوبی در محدودیتهای ذکر شده عمل میکند و میتواند به صورت کاملاً کارا درخواستها را پردازش نماید.
- خواندن ورودیها: از