Неделя кода 32 задача 1
ПОСТАНОВКА ЗАДАЧИ
У нас есть двоичная строка S. На каждом шаге мы добавляем еще одну двоичную строку T. T – дополнение до 1 для S (пример: S=10, затем T=01) .
Шаг 1: S=10, T=01, новое S=S+T =1001
Шаг 2: S=1001, после добавления S=10010110
шаг 3:S=10010110, после добавления S=1001011001101001
мы продолжаем делать это до тех пор, пока длина S не превысит 1000. Теперь дано Q запросов, где каждый запрос является индексом i строки С . Вывести значение в S[i] .Example(i=5,S[5] будет 1)
Ограничения для этой задачи очень низкие. Таким образом, мы можем просто написать программу для генерации строки длиной › 1000 и сохранить ее в нашей программе отправки и отвечать на запросы за время O(1). В этом :p нет ничего смешного, но это правильно!
ИСХОДНАЯ ПРОБЛЕМА
Эта задача на самом деле является модифицированной задачей, приведенной в APAC (они действительно продублировали ее?). Просто этот намного проще. Хорошее решение проблемы apac можно найти ЗДЕСЬ
РЕШЕНИЕ
Мы заметили, что генерируемая строка растет очень быстро (2^n) . Так что, если мы попытаемся сделать это на бумаге, будет легко просто прочитать индекс один и продолжать добавлять 0, если мы читаем 1, и 1, если читаем ноль. Итак, все числа в нашей строке взяты из первой строки S=01. Теперь все, что нам нужно сделать, это выяснить, как сопоставить любой index(i) в string(S) больше, чем 1(i›1 при нулевой индексации) на S=01.
Круто, давайте возьмемS длиной 4, S=0110
Теперь, имея индекс 3, мы можем сопоставить его с индексом 1, так как именно оттуда он был взят. И от индекса 2 до индекса 0.
Возьмем Sс длиной 8, S=01101001
Теперь задан индекс 7. давайте сопоставим его с S=0110 . Это будет индекс 3. Теперь мы знаем, что 3 сопоставляется с index 1 (помните нулевой индекс) . поэтому S[7]=S[3]=S[1]=1
Эй!, но S[7] на самом деле не s[3] правильно. Да, но мы читаем S[3] и записываем S[7]. Это будет очищено, когда мы возьмем S длины 16.S=0110100110010110
Теперь давайте посчитаем для индекса i=14. S[14]=S[6]=S[2]=S[0]=0. вау! но S[14] равно 1, а не нольo. Но мы можем точно сказать, что мы получили S[14] из S[0]. Присмотревшись, вы можете заметить, что всякий раз, когда было нечетное количество переходов для достижения любого из S[0]/S[1], нам нужно инвертировать значение в S[0]/S[1 ]. Если оно четное, то инверсия не требуется.
По сути, здесь мы находим относительную позицию нашего текущего индекса, если длина строки S меньше нашего текущего размера, который является степенью 2( поскольку длина S всегда будет степенью 2). Мы делаем это неоднократно, пока не достигнем индекса 0/1. Для которого мы знаем ответ, также мы знаем количество совершенных переходов, поэтому можем дать правильный ответ.
СЛОЖНОСТЬ ВРЕМЕНИ
О(лог(n))
Надеюсь, это помогло :) ……если это дало ♥
