http://acmp.ru/index.asp?main=task&id_task=433
Подскажите идею динамики. Судя по ограничению в 10^6 там требуется максимум n*log(n) решение.
У меня пока, увы, только квадратичное, которые, ясное дело, падает с TLE:
void solve(istream& is, ostream& os) {
int n;
string s;
is >> n >> s;
vector<int> dp(n, 0);
unsigned long long ans = 0;
for (int i = 0; i < n; ++i) {
dp[i] = s[i] == 'a' ? +1 : -1;
for (int j = 0; j < i; ++j) {
dp[j] += dp[i];
if (dp[j] == 0)
ans += 1;
}
}
os << ans << endl;
}
Не пойму, как делать половинное деление, чтобы получить log(n), ведь приходится проверять подстроки не только в кусках с границами в 1/2, 1/4, 1/8 и т.д., но пересекающие их.
А можно и линейно решить, для этого просто нужно для каждого префикса хранить разность между количеством букв a и b и прибавлять к ответу сколько таких разностей уже было в предыдущих префиксах.
http://acmp.ru/index.asp?main=bstatus&id_t=433
1. Считаем суммы на префиксах
Можно заметить, что если сумма на двух префиксах равны. Значит между ними количество "a" и "b" равны
2. Считаем количесто префиксов суммы Х
3. Прибавляем к ответу d[X]*(d[X]-1) div 2, где d[X] - количесто префиксов суммы Х
вот мой код, если что-то непонятно