Задача «Школа танцев» РОИ 2008 Автор задачи: Вадим Юрьевич Антонов Разбор: Сергей Игоревич Назаров
Решение с асимптотикой О(N 2 ) ABBABABBAA
Решение с асимптотикой О(N) ABBABABBAA Sum[0] = 0; Sum[i] = Sum[i 1] + 1, S[i] = 'A' Sum[i] = Sum[i 1] - 1, S[i] = 'B' Sum[i]: S[i]:
Решение с асимптотикой О(N) var Count: array[-NMAX...NMAX] of integer; Ans: int64;... Sum := 0; Ans := 0; Count[0] := 1; for i := 1 to N do begin if (S[i] = 'A') then Sum := Sum + 1; else Sum := Sum 1; inc(Ans, Count[Sum]); inc(Count[Sum]); end; writeln(Ans);