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 и т.д., но пересекающие их.
Comments (0)
