Блог пользователя Serh.kry

Автор Serh.kry, 8 лет назад, По-английски

There was the problem on the last contest which was solved with bit approach by some of top participants: one, two. I just can't understand how it works. Can someone explain?

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Oh, I did it that way! Observe the following pattern (bi represents the ith lower bit of n (1-based)):

Suppose that n has exactly one bit: then, your array will be b1.

If n has two bits, the final array will be b2, b1, b2.

If n has three bits, the final array will be b3, b2, b3, b1, b3, b2, b3.

If n has four bits, the final array will be b4, b3, b4, b2, b4, b3, b4, b1, b4, b3, b4, b2, b4, b3, b4.

You can see that in general, if the lowest significant bit of i is the k th one (1-based), then, the bit in the i th position (1-based) in the array of bits you get is bm + 1 - k, where m is the number of bits n has. This can be formally proved with induction. (Hint: notice that the way the array is built is symmetrical).

Then, for this solution, you only need to iterate from l to r and find those bits. My submission: 24858226

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    in your code , i & -i ,i dont understand this ,

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      i& - i gives you the least significant bit of number i. It is the same as (i & (i-1)). The least significant bit of a number is the rightmost bit that is not 0.