pekempelog

ペケンペイのブログ

Educational Codeforces Round 58 G (Zero XOR Subset)-less

https://codeforces.com/contest/1101/problem/G

みためからして ランクだから ランクをもとめればいい。

ルイセキワをとると それぞれのセグメントは S[i1] , S[i1] xor S[i2] , S[i2] xor S[i3] , ... という あたいになる。これらをつかって つくれるあたいと S[i1] , S[i2] , S[i3] , ... をつかって つくれるあたいは おなじである。

つまり モンダイは つぎのように いいかえられる。 N コのセイスウ a[1] , ... , a[N] があたえられる。このなかから ブブンワとして 0 をもたないような もっとも おおきい シュウゴウの おおきさを もとめよ。

ひとつのセイスウを F230 のゲンとして あつかえば a[1] , ... , a[N] から いくつの センケイドクリツなゲンを とれるのか きいてるのと おなじだから ランクをもとめればいい。

ただし シュウゴウに a[N] を ふくめないと いけないから a[N] = 0 のときは つくれない。ランクをもとめるときに a[N] をトクベツあつかいしなくてもいいのは a[N] となにかを とりかえられるから。

https://codeforces.com/contest/1101/submission/48244241



ところで E モンダイに だまされた。なんだあれ。