حسام حداد تکنولوژی، برنامه‌نویسی، هوش مصنوعی

در مطالب گذشته سوال کارت های برابر را حل کردیم حل اول کارت های برابر

حل قدیمی از چند جهت اشکال داشت ... اول اینکه بسیار ناخوانا بود و رفع عیب های احتمالی بوجود آمده سخت بود.

دوم اینکه دارای پیچیدگی زمانی O(N²M⁴) بود که با توجه به N کمتر از 100 و M=5 این کد Accept شد اما برای مسئله مشابه با M های بزرگتر ، برای مثال M=100 برنامه ما در محدوده زمانی مورد نظر به جواب نمیرسید و نتیجه ارسال کد Time Limit Executed میشد.

برای حل این سوال اینبار از یکی از Data Structure های C++ Standard Library به نام Bitset استفاده میکنیم که میتوان از این Solution به عنوان مثالی برای یادگیری Bitset نیز استفاده کرد.

میشود Bitset را به عنوان یک آرایه ای از متغیر Boolean تعریف کرد، اما این تعریف بسیار ناقص میباشد زیرا برای یک آرایه Boolean توابعی مانند شیفت به چپ ، شیفت به راست ، نقیض ، مساوی بودن ، OR , AND , XOR با یک آرایه Boolean دیگر وجود ندارد و برای پیاده سازی هریک نیاز به تابع نویسی داریم. اما در Bitset تمام این امکانات گنجانده شده است.

امروز میخواهیم یک مسئله سطح متوسط ACM را حل کنیم اینگونه سوال ها دارای یک نکته یا یک ابتکار کوچک میباشند که اگر آنرا متوجه شوید به راحتی میتوانید سوال را حل کنید.

این سوال دوباره به شکل بهتر و سریعتر حل شده و میتوانید از لینک زیر برای مشاهده آن استفاده کنید.

حل بهتر مسئله کارتهای برابر

این سوال از مسابقه Southeast USA 2000 انتخاب شده است.

در مورد سوال را از سایت ShareCode.ir مسئله 1003 بخوانید.