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

Автор IOI2018, история, 9 лет назад, По-русски
  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

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

Где ты нашел задачи Респы 2015 можешь дать ссылку.

»
9 лет назад, # |
Rev. 12   Проголосовать: нравится +17 Проголосовать: не нравится

пускай

  • l левая граница текущего отрезка (l = 0)
  • lans левая граница отрезка-ответа (lans = 0)
  • rans правая граница отрезка-ответа (rans = INF)
  • cur текущее количество различных букв в отрезке (cur = 0)
  • a[26] количество каждой буквы на отрезке

переберём r(правую границу отрезка)

  • обновим массив a и cur
if (++a[s[r] - 'a'] == 1) cur++;
  • если cur > k , то обрежем отрезок наш слева при этом обновляя массив а и cur
  • теперь попытаемся еще обрезать отрезок наш чтобы cur остался равным k и отрезок имел минимальную длину
  • если cur == k , то попытаемся обновить rans и lans

нетрудно заметить что если rans == INF то ответ -1, иначе rans — lans + 1

код на С++ http://pastebin.com/6jE2MVzS