DemoVersion
در مطالب گذشته سوال کارت های برابر را حل کردیم حل اول کارت های برابر
حل قدیمی از چند جهت اشکال داشت ... اول اینکه بسیار ناخوانا بود و رفع عیب های احتمالی بوجود آمده سخت بود.
دوم اینکه دارای پیچیدگی زمانی O(N2M4) بود که با توجه به 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 تمام این امکانات گنجانده شده است.
ادامه مطلب