# biweekly-contest-85

## A

### Statement

Metadata

``````输入：blocks = "WBBWWBBWBW", k = 7

``````

``````输入：blocks = "WBWBBBW", k = 2

``````

• `n == blocks.length`
• `1 <= n <= 100`
• `blocks[i]` 要么是 `'W'` ，要么是 `'B'`
• `1 <= k <= n`

Metadata

You are given a 0-indexed string `blocks` of length `n`, where `blocks[i]` is either `'W'` or `'B'`, representing the color of the `ith` block. The characters `'W'` and `'B'` denote the colors white and black, respectively.

You are also given an integer `k`, which is the desired number of consecutive black blocks.

In one operation, you can recolor a white block such that it becomes a black block.

Return the minimum number of operations needed such that there is at least one occurrence of `k` consecutive black blocks.

Example 1:

``````Input: blocks = "WBBWWBBWBW", k = 7
Output: 3
Explanation:
One way to achieve 7 consecutive black blocks is to recolor the 0th, 3rd, and 4th blocks
so that blocks = "BBBBBBBWBW".
It can be shown that there is no way to achieve 7 consecutive black blocks in less than 3 operations.
Therefore, we return 3.
``````

Example 2:

``````Input: blocks = "WBWBBBW", k = 2
Output: 0
Explanation:
No changes need to be made, since 2 consecutive black blocks already exist.
Therefore, we return 0.
``````

Constraints:

• `n == blocks.length`
• `1 <= n <= 100`
• `blocks[i]` is either `'W'` or `'B'`.
• `1 <= k <= n`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <vector>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

class Solution {
public:
int minimumRecolors(string blocks, int k) {
int n = int(blocks.length());
auto f = vector<int>(n + 1, 0);
int res = k;

for (int i = 0; i < n; i++) {
f[i + 1] = f[i] + (blocks[i] == 'W');
if (i + 1 >= k) {
res = min(res, f[i + 1] - f[i + 1 - k]);
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

Metadata

``````输入：s = "0110101"

``````

``````输入：s = "11100"

s 中没有 "01" 存在，整个过程花费 0 秒。

``````

• `1 <= s.length <= 1000`
• `s[i]` 要么是 `'0'` ，要么是 `'1'`

Metadata

You are given a binary string `s`. In one second, all occurrences of `"01"` are simultaneously replaced with `"10"`. This process repeats until no occurrences of `"01"` exist.

Return the number of seconds needed to complete this process.

Example 1:

``````Input: s = "0110101"
Output: 4
Explanation:
After one second, s becomes "1011010".
After another second, s becomes "1101100".
After the third second, s becomes "1110100".
After the fourth second, s becomes "1111000".
No occurrence of "01" exists any longer, and the process needed 4 seconds to complete,
so we return 4.
``````

Example 2:

``````Input: s = "11100"
Output: 0
Explanation:
No occurrence of "01" exists in s, and the processes needed 0 seconds to complete,
so we return 0.
``````

Constraints:

• `1 <= s.length <= 1000`
• `s[i]` is either `'0'` or `'1'`.

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

class Solution {
public:
int secondsToRemoveOccurrences(string s) {
int n = int(s.length());
int res = 0;
while (true) {
bool c = false;
for (int i = n - 1; i > 0; i--) {
if (s[i] == '1' && s[i - 1] == '0') {
swap(s[i], s[i - 1]);
c = true;
i--;
}
}

if (c == false) {
break;
} else {
++res;
}
}

return res;

// int one = 0;
// for (const auto &c : s) {
//     one += (c == '1');
// }

// int res = 0;
// int current_one = 0;
// for (int i = 0; i < n; i++) {
//     if (s[i] == '1') {
//         res = max(res, i - current_one);
//         ++current_one;
//     }
// }

// return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

Metadata

``````输入：s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]]

``````输入：s = "dztz", shifts = [[0,0,0],[1,1,1]]

``````

• `1 <= s.length, shifts.length <= 5 * 104`
• `shifts[i].length == 3`
• `0 <= starti <= endi < s.length`
• `0 <= directioni <= 1`
• `s` 只包含小写英文字母。

Metadata

You are given a string `s` of lowercase English letters and a 2D integer array `shifts` where `shifts[i] = [starti, endi, directioni]`. For every `i`, shift the characters in `s` from the index `starti` to the index `endi` (inclusive) forward if `directioni = 1`, or shift the characters backward if `directioni = 0`.

Shifting a character forward means replacing it with the next letter in the alphabet (wrapping around so that `'z'` becomes `'a'`). Similarly, shifting a character backward means replacing it with the previous letter in the alphabet (wrapping around so that `'a'` becomes `'z'`).

Return the final string after all such shifts to `s` are applied.

Example 1:

``````Input: s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]]
Output: "ace"
Explanation: Firstly, shift the characters from index 0 to index 1 backward. Now s = "zac".
Secondly, shift the characters from index 1 to index 2 forward. Now s = "zbd".
Finally, shift the characters from index 0 to index 2 forward. Now s = "ace".``````

Example 2:

``````Input: s = "dztz", shifts = [[0,0,0],[1,1,1]]
Output: "catz"
Explanation: Firstly, shift the characters from index 0 to index 0 backward. Now s = "cztz".
Finally, shift the characters from index 1 to index 1 forward. Now s = "catz".
``````

Constraints:

• `1 <= s.length, shifts.length <= 5 * 104`
• `shifts[i].length == 3`
• `0 <= starti <= endi < s.length`
• `0 <= directioni <= 1`
• `s` consists of lowercase English letters.

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <vector>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

class Solution {
public:
string shiftingLetters(string s, vector<vector<int>> &shifts) {
int n = int(s.length());
auto f = vector<int>(n + 5, 0);
for (const auto &s : shifts) {
int st = s[0];
int ed = s[1];
int d = s[2];
if (d == 0) {
d = -1;
}

f[st + 1] += d;
f[ed + 2] -= d;
}

for (int i = 1; i <= n; i++) {
f[i] += f[i - 1];
f[i] = (f[i] % 26 + 26) % 26;
}

for (int i = 0; i < n; i++) {
s[i] -= 'a';
s[i] = char((s[i] + f[i + 1] % 26 + 26) % 26);
s[i] += 'a';
}

return s;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

Metadata

``````输入：nums = [1,2,5,6,1], removeQueries = [0,3,2,4,1]

``````输入：nums = [3,2,11,1], removeQueries = [3,2,1,0]

``````

• `n == nums.length == removeQueries.length`
• `1 <= n <= 105`
• `1 <= nums[i] <= 109`
• `0 <= removeQueries[i] < n`
• `removeQueries` 中所有数字 互不相同 。

Metadata

You are given two 0-indexed integer arrays `nums` and `removeQueries`, both of length `n`. For the `ith` query, the element in `nums` at the index `removeQueries[i]` is removed, splitting `nums` into different segments.

A segment is a contiguous sequence of positive integers in `nums`. A segment sum is the sum of every element in a segment.

Return an integer array `answer`, of length `n`, where `answer[i]` is the maximum segment sum after applying the `ith` removal.

Note: The same index will not be removed more than once.

Example 1:

``````Input: nums = [1,2,5,6,1], removeQueries = [0,3,2,4,1]
Output: [14,7,2,2,0]
Explanation: Using 0 to indicate a removed element, the answer is as follows:
Query 1: Remove the 0th element, nums becomes [0,2,5,6,1] and the maximum segment sum is 14 for segment [2,5,6,1].
Query 2: Remove the 3rd element, nums becomes [0,2,5,0,1] and the maximum segment sum is 7 for segment [2,5].
Query 3: Remove the 2nd element, nums becomes [0,2,0,0,1] and the maximum segment sum is 2 for segment [2].
Query 4: Remove the 4th element, nums becomes [0,2,0,0,0] and the maximum segment sum is 2 for segment [2].
Query 5: Remove the 1st element, nums becomes [0,0,0,0,0] and the maximum segment sum is 0, since there are no segments.
Finally, we return [14,7,2,2,0].``````

Example 2:

``````Input: nums = [3,2,11,1], removeQueries = [3,2,1,0]
Output: [16,5,3,0]
Explanation: Using 0 to indicate a removed element, the answer is as follows:
Query 1: Remove the 3rd element, nums becomes [3,2,11,0] and the maximum segment sum is 16 for segment [3,2,11].
Query 2: Remove the 2nd element, nums becomes [3,2,0,0] and the maximum segment sum is 5 for segment [3,2].
Query 3: Remove the 1st element, nums becomes [3,0,0,0] and the maximum segment sum is 3 for segment [3].
Query 4: Remove the 0th element, nums becomes [0,0,0,0] and the maximum segment sum is 0, since there are no segments.
Finally, we return [16,5,3,0].
``````

Constraints:

• `n == nums.length == removeQueries.length`
• `1 <= n <= 105`
• `1 <= nums[i] <= 109`
• `0 <= removeQueries[i] < n`
• All the values of `removeQueries` are unique.

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <vector>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

class Solution {
public:
vector<long long> maximumSegmentSum(vector<int> &nums, vector<int> &removeQueries) {
int n = int(nums.size());

auto f = vector<ll>(n + 5, 0);
for (int i = 1; i <= n; i++) {
f[i] = f[i - 1] + nums[i - 1];
}

auto se = set<pair<int, int>>();
auto sum_se = multiset<ll>();

se.insert({1, n});
sum_se.insert(f[n]);

auto res = vector<ll>();
for (auto ix : removeQueries) {
++ix;

auto it = se.lower_bound({ix, n + 1});
--it;

// if (it == se.end()) {
//     cout << ix << " " << se.size() << endl;
//     continue;
// }

auto st = it->first;
auto ed = it->second;

sum_se.erase(sum_se.lower_bound(f[ed] - f[st - 1]));

{
auto _ed = ix - 1;
if (st <= _ed) {
se.insert({st, _ed});
sum_se.insert(f[_ed] - f[st - 1]);
}
}

{
auto _st = ix + 1;
if (_st <= ed) {
se.insert({_st, ed});
sum_se.insert(f[ed] - f[_st - 1]);
}
}

se.erase(it);
if (sum_se.empty()) {
res.push_back(0);
} else {
res.push_back(*sum_se.rbegin());
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````