Учитывая двоичную строку, подсчитайте количество плотных подстрок за время O (nlogn)
Плотная подстрока: количество единиц > количество нулей.
Подход грубой силы в C++
#include <iostream>
#include <string>
using namespace std;
int bin_dense_count_bruteforce(string s) {
int n = s.size();
int ans = 0;
for(int i=0; i<=n-1; i++) {
int statusNow = 0;
for(int j=i; j<=n-1; j++) {
if (s[j] == '1')
statusNow++;
else
statusNow--;
if (statusNow>0)
ans++;
}
}
return ans;
}
int main() {
string s = "11000101";
cout<<bin_dense_count_bruteforce(s)<<endl;
// 7
// i, j substring
// 0, 0 1
// 0, 1 11
// 0, 2 110
// 1, 1 1
// 5, 5 1
// 5, 7 101
// 7, 7 1
return 0;
}
Я пробовал думать о любом подходе с unordered_map, например, о сумме префиксов, о подходе или аналогичном способе. Я пробовал искать в Интернете и даже в чате, Клоде и т. д., но безуспешно.
@LisanAlGaib Любой алгоритм O(n) также является O(nlogn), так что же вы на самом деле спрашиваете? Если у вас есть такое решение, не стесняйтесь опубликовать ответ.
Именно поэтому я спрашиваю, почему именно o(nlogn) является требованием, упомянутым в вопросе. Ответ O(n) уже предложен ЛМейером.
@LisanAlGaib Ответ Л. Мейера: Θ(nlogn), поскольку двоичные индексированные деревья требуют логарифмического времени для обновлений и запросов.
Ответы 1
Во-первых, быстрый поиск в Google выдаст вам вот эту полезную страницу https://www.geeksforgeeks.org/count-of-substrings-in-a-binary-string-that-contains-more-1s-than-0s /
Если мы возьмем префиксную сумму pre, массив, подсчитывающий разницу между единицами и нулями:
pre[i+1] = count of 1s in s[0..i] - number of 0s in s[0..i]
Проблема эквивалентна:
find all (i, j) with i < j such as pre[i] < pre[j].
Где i, j может изменяться от 0 до n. Следовательно, это похоже на подсчет инверсии. Дерево фенвика способно на это O(nlog(n)), но это не единственное решение.
Чтобы индексы не были отрицательными, их можно сдвинуть на n.
vector<int> p(n+1);
FenwickTree<long long> ft(2*n+1);
for (int i = 0; i < n; ++i) {
p[i+1] += (s[i] == '1'?1:-1)+p[i];
ft.update(n+p[i+1], +1);
}
long long ans = 0;
for (int i = 1; i <= n; ++i) {
ans += ft.query_greater_than(n+p[i-1]);
if (i != 1) ft.update(n+p[i-1],-1);
}
Результат может не соответствовать int, поскольку он может быть эквивалентен n^2.
Вы можете добиться результата за O(n), зачем вам это за O(nlogn)?