Блог пользователя parth015

Help needed in following problem

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

Hello everyone, I needed help in following problem. From editorial it is not clear. Link of problem is(http://codeforces.net/contest/165/problem/C)

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

»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
  • Let Si be the amount of ones in the prefix 1..i, so for a substring l..r to contain exactly k ones, we have Sr - Sl - 1 = k. For this problem, we are interested for every position i in how many positions p we have Sp = Si + k.
  • We can precalculate Lx and Rx, the first position i with Si = x and the last position i with Si = x.
  • So now for every position i we must simply do the subtraction RSi + k - max(LSi + k, i + 1) + 1.

Check code for further clarity: String Problem

→ Ответить