xor sum ! پیدا کردن زیر دنباله ای از دنباله ای اصلی با xor ماکسیمم

آمار پرسش:

پرسیده شده: 2016-05-06 08:51:19 -0600
مشاهده شده: 309 بار
بروز شده: 2016-05-08 12:04:25 -0600

نکاتی در مورد نوشتن پاسخ:

در این قسمت می‌تونی به یک پرسش پاسخ بدی. اگه می‌خوای در مورد پرسش بحث و اظهار نظر کنی از قسمت «ثبت نظر» استفاده کن.
پاسخت رو دقیق و کامل بنویس، از عکس استفاده کن و اگه لازمه به منابع (کتاب یا سایت) ارجاع بده.
اگه پرسش یا پاسخ‌ها مفید هستند حتما بهشون رای بده تا پرسش‌ها و پاسخ‌های خوب مشخص بشن.

استفاده از ویرایشگر:

توی قسمت پیش‌نمایش می‌تونی ببینی متنی که نوشتی چجوری روی سایت دیده میشه.
خیلی مهم: برای اینکه به خط بعد بری باید دوتا Enter بزنی.
می‌تونی از تگ‌های معمولی و ساده‌ی html هم استفاده کنی.
با دکمه‌هایی که بالای ویرایش‌گر قرار دارند کلی کار می‌شه کرد. از عکس‌گذاشتن بگیر تا لیست شماره‌دار. حتما امتحان‌شون کن.

علائم ریاضی:

برای نوشتن علائم ریاضی می‌تونی از Mathjax استفاده کنی. راهنمای Mathjax رو از سایت math.stackexchange بخون.
برای نوشتن عبارت ریاضی وسط جمله، اون عبارت رو بین دوتا $ قرار بده.
برای نوشتن عبارت ریاضی تو یه خط جدید اون رو بین دوتا $$ قرار بده.

سلام . خب , صورت سوال رو تقریبا گفتم دیگه D: یه دنباله با n عضو می دن بهمون و ما می خوایم یه زیر دنباله از این دنباله رو انتخاب کنیم به صورتی که xor اعضای این زیر دنباله , ماکسیمم باشه و اون عدد ماکسیمم رو هم باید در نهایت چاپ کنیم

n حداکثر برابر با ۱۰ به توان ۵ هست

اعدادمون هم توی int جا می شن مثل اینکه D:

(صورت اصلی سوال اینه که حداکثر ۱۰ تا تست کیس داریم ! برای هر کدوم از تست کیس ها باید مسئله رو حل کنین ... D: )

محدودیت زمانی هم ۳ ثانیست D:

منظورم از زیردنباله , یه سری عضو متوالی بود ! نمی دونم اگر باید چیز دیگه ای بهش گفت D:

2016-05-06 08:51:19 -0600

دان م 61 ● 2 ● 3 ● 7

پاک‌کردن ویرایش سوال

نظرات

اعداد دنباله تو int جا می شن ها !! جواب شاید جا نشد D: و اینکه سوال رو خودم بلدم D: صرفا برای اونایی که می خوان تمرین کنن گذاشتم D:

2016-05-06 08:54:48 -0600 دان م

از یه ایده که میاد مثلث میساره باس استفاده کنی

2016-05-06 08:58:09 -0600 ساده

سوال سی اف رو کپی کردی بچه جون ؟

2016-05-06 09:38:14 -0600 ساده

نه ! D:

2016-05-06 10:01:12 -0600 دان م

در ضمن بالفرض هم که کپی کرده باشم , نیومدم بگم که سوال مال خودمه !

2016-05-06 10:01:39 -0600 دان م

2 پاسخ

ابتدا یه درخت دودویی از ۰ و ۱ برای نگه داری اعداد میسازیم طوری که با هر بار رفتن به راست یک ۰ به عدد که تاحالا بوده اضافه میشود (به تهش ) و به هر بار رفتن به چپ یک ۱ اضافه میشود برای مثال جیگاه عدد ۱۰۰۱ در این درخت برابر با LRRL . (اسمش فکر کنم trie بود ).

سپس pi را ایکس اور اعداد از اول تا عدد i ام قرار میدهیم. میدانیم ایکس ار اعداد l تا r برابر با pr ^ pl-1 است! حال هر دفعه هر عدد را به ترتیب وارد trie میکنیم و di را برابر با زیرشته ای با بیشترین ایکس اور که به i ختم میشود قرار میدهیم.

قبل از این که ai رو تو trie اضافه کنیم برای محاسبه di این کار را انجام میدهیم:

j را از maxbit تا 0 قرار بده و ابتدا اشاره گر را روی ریشه trie قرار بده , هر دفعه اگر شاخه ای با بیت مخالف بیت j امه ai وجود داشت به اون شاخه برو واگرنه به تنها شاخه باقی مانده برو و عدد بدست آمده از روی حرکت اشاره گر روی trie را در di بریز. جواب برابر با ماکسیمم di ها است!

اگه مشکلی بود مطرح کنید. ممنون.

*ابتدا trie خالی است و با هر بار اضافه شدن یه عدد شاخه های مربوطه را به وجود می آوریم ( ابتدا ۰ را اضافه میکنیم!)

2016-05-08 11:21:37 -0600