Cまで三完。
D. Birthday Gift
解説AC。
全体のxorをXORとすると、区間を分けてxorを取ったときの値もXOR以上になるということに気付かなくてはいけなかった。
あとは、上の桁から、XORのi bit目が0のときに、0のままにしなくてはいけないか、1にしても良いのかを考えていく。
0にするときは、A_l^...^A_rのi bit目が0になったとき、その部分をA_l^...^A_rに置き換える……という貪欲を行って良いと気付くと実装しやすい。
分かってしまえば難しくはないのだが……。
0 件のコメント:
コメントを投稿