# biweekly-contest-75

## A

### Statement

• 比方说，`x = 7` ，二进制表示为 `111` ，我们可以选择任意一个位（包含没有显示的前导 0 ）并进行翻转。比方说我们可以翻转最右边一位得到 `110` ，或者翻转右边起第二位得到 `101` ，或者翻转右边起第五位（这一位是前导 0 ）得到 `10111` 等等。

``````输入：start = 10, goal = 7

- 翻转右边起第一位得到：1010 -> 1011 。
- 翻转右边起第三位：1011 -> 1111 。
- 翻转右边起第四位：1111 -> 0111 。

``````输入：start = 3, goal = 4

- 翻转右边起第一位：011 -> 010 。
- 翻转右边起第二位：010 -> 000 。
- 翻转右边起第三位：000 -> 100 。

``````

• `0 <= start, goal <= 109`

A bit flip of a number `x` is choosing a bit in the binary representation of `x` and flipping it from either `0` to `1` or `1` to `0`.

• For example, for `x = 7`, the binary representation is `111` and we may choose any bit (including any leading zeros not shown) and flip it. We can flip the first bit from the right to get `110`, flip the second bit from the right to get `101`, flip the fifth bit from the right (a leading zero) to get `10111`, etc.

Given two integers `start` and `goal`, return the minimum number of bit flips to convert `start` to `goal`.

Example 1:

``````Input: start = 10, goal = 7
Output: 3
Explanation: The binary representation of 10 and 7 are 1010 and 0111 respectively. We can convert 10 to 7 in 3 steps:
- Flip the first bit from the right: 1010 -> 1011.
- Flip the third bit from the right: 1011 -> 1111.
- Flip the fourth bit from the right: 1111 -> 0111.
It can be shown we cannot convert 10 to 7 in less than 3 steps. Hence, we return 3.``````

Example 2:

``````Input: start = 3, goal = 4
Output: 3
Explanation: The binary representation of 3 and 4 are 011 and 100 respectively. We can convert 3 to 4 in 3 steps:
- Flip the first bit from the right: 011 -> 010.
- Flip the second bit from the right: 010 -> 000.
- Flip the third bit from the right: 000 -> 100.
It can be shown we cannot convert 3 to 4 in less than 3 steps. Hence, we return 3.
``````

Constraints:

• `0 <= start, goal <= 109`

### 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>;
const ll mod = 1e9 + 7;

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

class Solution {
public:
int minBitFlips(int start, int goal) {
return __builtin_popcount(start ^ goal);
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

`nums` 的 三角和 是执行以下操作以后最后剩下元素的值：

1. `nums` 初始包含 `n` 个元素。如果 `n == 1` ，终止 操作。否则，创建 一个新的下标从 0 开始的长度为 `n - 1` 的整数数组 `newNums` 。
2. 对于满足 `0 <= i < n - 1` 的下标 `i` ，`newNums[i]` 赋值 为 `(nums[i] + nums[i+1]) % 10` ，`%` 表示取余运算。
3. 将 `newNums` 替换 数组 `nums` 。
4. 从步骤 1 开始 重复 整个过程。

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

``````输入：nums = [5]

• `1 <= nums.length <= 1000`
• `0 <= nums[i] <= 9`

You are given a 0-indexed integer array `nums`, where `nums[i]` is a digit between `0` and `9` (inclusive).

The triangular sum of `nums` is the value of the only element present in `nums` after the following process terminates:

1. Let `nums` comprise of `n` elements. If `n == 1`, end the process. Otherwise, create a new 0-indexed integer array `newNums` of length `n - 1`.
2. For each index `i`, where `0 <= i < n - 1`, assign the value of `newNums[i]` as `(nums[i] + nums[i+1]) % 10`, where `%` denotes modulo operator.
3. Replace the array `nums` with `newNums`.
4. Repeat the entire process starting from step 1.

Return the triangular sum of `nums`.

Example 1:

``````Input: nums = [1,2,3,4,5]
Output: 8
Explanation:
The above diagram depicts the process from which we obtain the triangular sum of the array.``````

Example 2:

``````Input: nums = [5]
Output: 5
Explanation:
Since there is only one element in nums, the triangular sum is the value of that element itself.``````

Constraints:

• `1 <= nums.length <= 1000`
• `0 <= nums[i] <= 9`

### 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>;
const ll mod = 1e9 + 7;

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

class Solution {
public:
int triangularSum(vector<int> &nums) {
if (nums.size() == 1) {
return nums[0];
}

auto f = vector<vector<int>>(2, vector<int>());
f[0] = nums;

for (int i = 1;; i++) {
auto &pre = f[i & 1 ^ 1];
auto &now = f[i & 1];

now.clear();
for (int i = 1; i < pre.size(); i++) {
now.push_back((pre[i - 1] + pre[i]) % 10);
}

if (now.size() == 1) {
return now[0];
}
}
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

• `s[i] = '0'` 表示第 `i` 栋建筑是一栋办公楼，
• `s[i] = '1'` 表示第 `i` 栋建筑是一间餐厅。

• 比方说，给你 `s = "001101"` ，我们不能选择第 `1` ，`3` 和 `5` 栋建筑，因为得到的子序列是 `"011"` ，有相邻两栋建筑是同一类型，所以 不合 题意。

``````输入：s = "001101"

- [0,2,4] ，从 "001101" 得到 "010"
- [0,3,4] ，从 "001101" 得到 "010"
- [1,2,4] ，从 "001101" 得到 "010"
- [1,3,4] ，从 "001101" 得到 "010"
- [2,4,5] ，从 "001101" 得到 "101"
- [3,4,5] ，从 "001101" 得到 "101"

``````

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

``````

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

You are given a 0-indexed binary string `s` which represents the types of buildings along a street where:

• `s[i] = '0'` denotes that the `ith` building is an office and
• `s[i] = '1'` denotes that the `ith` building is a restaurant.

As a city official, you would like to select 3 buildings for random inspection. However, to ensure variety, no two consecutive buildings out of the selected buildings can be of the same type.

• For example, given `s = "001101"`, we cannot select the `1st`, `3rd`, and `5th` buildings as that would form `"011"` which is not allowed due to having two consecutive buildings of the same type.

Return the number of valid ways to select 3 buildings.

Example 1:

``````Input: s = "001101"
Output: 6
Explanation:
The following sets of indices selected are valid:
- [0,2,4] from "001101" forms "010"
- [0,3,4] from "001101" forms "010"
- [1,2,4] from "001101" forms "010"
- [1,3,4] from "001101" forms "010"
- [2,4,5] from "001101" forms "101"
- [3,4,5] from "001101" forms "101"
No other selection is valid. Thus, there are 6 total ways.
``````

Example 2:

``````Input: s = "11100"
Output: 0
Explanation: It can be shown that there are no valid selections.
``````

Constraints:

• `3 <= s.length <= 105`
• `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>;
const ll mod = 1e9 + 7;

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

class Solution {
public:
long long numberOfWays(string s) {
auto calc = [&](string t) -> ll {
int n = t.length();
auto f = vector<ll>(n + 1, 0);
f[0] = 1;
for (int i = 0; i < s.length(); i++) {
for (int j = n; j >= 1; j--) {
if (s[i] == t[j - 1]) {
f[j] += f[j - 1];
}
}
}

return f[n];
};

return calc("010") + calc("101");
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

• 比方说，`s = "abaca"` ，`s1 == "a"` ，`s2 == "ca"` ，`s3 == "aca"` 依次类推。

`si` 的 得分 为 `si` 和 `sn` 的 最长公共前缀 的长度（注意 `s == sn` ）。

``````输入：s = "babab"

s1 == "b" ，最长公共前缀是 "b" ，得分为 1 。
s2 == "ab" ，没有公共前缀，得分为 0 。
s3 == "bab" ，最长公共前缀为 "bab" ，得分为 3 。
s4 == "abab" ，没有公共前缀，得分为 0 。
s5 == "babab" ，最长公共前缀为 "babab" ，得分为 5 。

``````输入：s = "azbazbzaz"

s2 == "az" ，最长公共前缀为 "az" ，得分为 2 。
s6 == "azbzaz" ，最长公共前缀为 "azb" ，得分为 3 。
s9 == "azbazbzaz" ，最长公共前缀为 "azbazbzaz" ，得分为 9 。

``````

• `1 <= s.length <= 105`
• `s` 只包含小写英文字母。

You are building a string `s` of length `n` one character at a time, prepending each new character to the front of the string. The strings are labeled from `1` to `n`, where the string with length `i` is labeled `si`.

• For example, for `s = "abaca"`, `s1 == "a"`, `s2 == "ca"`, `s3 == "aca"`, etc.

The score of `si` is the length of the longest common prefix between `si` and `sn` (Note that `s == sn`).

Given the final string `s`, return the sum of the score of every `si`.

Example 1:

``````Input: s = "babab"
Output: 9
Explanation:
For s1 == "b", the longest common prefix is "b" which has a score of 1.
For s2 == "ab", there is no common prefix so the score is 0.
For s3 == "bab", the longest common prefix is "bab" which has a score of 3.
For s4 == "abab", there is no common prefix so the score is 0.
For s5 == "babab", the longest common prefix is "babab" which has a score of 5.
The sum of the scores is 1 + 0 + 3 + 0 + 5 = 9, so we return 9.``````

Example 2:

``````Input: s = "azbazbzaz"
Output: 14
Explanation:
For s2 == "az", the longest common prefix is "az" which has a score of 2.
For s6 == "azbzaz", the longest common prefix is "azb" which has a score of 3.
For s9 == "azbazbzaz", the longest common prefix is "azbazbzaz" which has a score of 9.
For all other si, the score is 0.
The sum of the scores is 2 + 3 + 9 = 14, so we return 14.
``````

Constraints:

• `1 <= s.length <= 105`
• `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>

#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>;
const ll mod = 1e9 + 7;

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

const int N = 1e5 + 10;

struct ExKMP {
int Next[N];
void GetNext(const char *s) {
int lens = strlen(s + 1), p = 1, pos;
Next[1] = lens;
while (p + 1 <= lens && s[p] == s[p + 1]) ++p;
Next[pos = 2] = p - 1;
for (int i = 3; i <= lens; ++i) {
int len = Next[i - pos + 1];
if (len + i < p + 1)
Next[i] = len;
else {
int j = max(p - i + 1, 0);
while (i + j <= lens && s[j + 1] == s[i + j]) ++j;
p = i + (Next[pos = i] = j) - 1;
}
}
}
} exkmp;

class Solution {
public:
long long sumScores(string s) {
s.insert(0, "@");
exkmp.GetNext(s.c_str());

ll res = 0;

for (int i = 1; i < s.length(); i++) {
// cout << i << " " << exkmp.Next[i] << endl;
res += exkmp.Next[i];
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````