Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Topic describes

This is a question of the day for code source DIV2, corresponding to cf score 1500.

Prefixes and + hash tables

Daimayuan Online Judge

We call a string a good string when it contains only ‘0’ and ‘1’.

Now that you have a good string, find the number of substrings in that string where ‘1’ occurs exactly k times.

Input format

The first line gives a number k, representing the number of ‘1s’ in the substring.

The second line gives a good string.

The output format

Output an integer that represents the number of qualified substrings in the string

Data range

0 k e6 1 or less, or less | s | 1 or less e6

For example, enter 1

1, 1010Copy the code

Example output 1

6
Copy the code

Problem resolution

Topic for us to find is a substring of the number of 1 k, how many we can certainly enumerated the length of the string, and then traverse the string composition, if meet the requirements, the counter + +, but the time complexity is O (n ^ 2), under this topic e6 1 data is obviously will timeout, so we try to transform the title.

Since it’s a substring, it means that it’s continuous, and the string is 1 except for 0, so we can write it as a prefix sum, and then the question becomes, how many times does the interval sum be k?

We count the prefixes and arrays of substrings and hash the number of the same prefixes. Each position with a prefix sum of sum can form a good substring with all positions with a prefix sum of sum-k, so our counter is counting (the number of prefixes sum of sum * the number of prefixes sum of sum-k). Finally, just output the counter.

But there’s one special case, which is k=0, and if k=0, then the number of substrings we’re going to record is going to be (sum of prefix * sum of prefix), which is obviously not true, and there will be duplicate good substrings. Therefore, when k=0 is encountered, we should treat it specially. Its substring number is: the substring composed of consecutive ANS zeros. The different good substring it can form is: (ANS +1) * ANS /2.

AC code

#include<iostream> using namespace std; #include<vector> #include<map> typedef long long ll; typedef pair<int, int>PII; const int MOD = 1e9 + 7; const int N = 100100; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int k, l = 0; cin >> k; string str; cin >> str; int n = str.size(); map<int, ll>mymap; mymap[0]++; ll res = 0; vector<int>v(n + 1), sum(n + 1); if (k == 0) { ll ans = 0; // add 1 to the end of the string to prevent all zeros STR += '1'; n++; for (int i = 0; i < n; i++) { if (str[i] == '0')ans++; else { res += (ans + 1) * ans / 2; ans = 0; } } } else { for (int i = 1; i <= n; i++) { v[i] = str[i - 1] - '0'; sum[i] = v[i] + sum[i - 1]; mymap[sum[i]]++; } int ans = 0; while (mymap[ans + k] ! = 0) { res += mymap[ans] * mymap[ans + k]; ans++; } } cout << res << endl; return 0; }Copy the code
  • Time complexity: O(n) (we only need to iterate once to calculate the prefix sum)