おーじのゆるゆる精進日記
Sum AND Subarrays
感想
上からビットを立ててそれを実現できるかという解法で実装を試みましたが実装できず.
問題概要
K個の数値の論理積を最大化しよう.
解法
論理積ということは一つでも0のビットがあればそのビットは立たない.
より上の方のビットが立っていれば嬉しい.
計算量的にも余裕があるので上からこのビットを立たせられるかの探索が思いつく.
あとは実装.
具体的にはこれまでの答えをans,部分列の値をdataとすると,ansと立たせたいビットでorを取ります.(これをBとする)
そして、値を一つ一つ比べてB & data = Bが成り立つ個数を調べます.
これがK個以上であればそのビットは立たせられます.
ビットは高々40回ほど回せばおっけーなのでTLEはなさそう.
注意点
論理積の基本A & B = Aが及ぼすあれこれを把握する.
今回では1LL<<i(0≦i≦40)みたいな感じでするとうまく立たせたいビットを動かせますよ!!これぐらい知っといてよ俺...