# weekly-contest-278

## A

### Statement

• Difficulty: Easy
• Tag: `数组` `哈希表` `排序` `模拟`

1. 如果在 `nums` 中找到 `original` ，将 `original` 乘以 2 ，得到新 `original`（即，令 `original = 2 * original`）。
2. 否则，停止这一过程。
3. 只要能在数组中找到新 `original` ，就对新 `original` 继续 重复 这一过程

``````输入：nums = [5,3,6,1,12], original = 3

- 3 能在 nums 中找到。3 * 2 = 6 。
- 6 能在 nums 中找到。6 * 2 = 12 。
- 12 能在 nums 中找到。12 * 2 = 24 。
- 24 不能在 nums 中找到。因此，返回 24 。
``````

``````输入：nums = [2,7,9], original = 4

- 4 不能在 nums 中找到。因此，返回 4 。
``````

• `1 <= nums.length <= 1000`
• `1 <= nums[i], original <= 1000`

You are given an array of integers `nums`. You are also given an integer `original` which is the first number that needs to be searched for in `nums`.

You then do the following steps:

1. If `original` is found in `nums`, multiply it by two (i.e., set `original = 2 * original`).
2. Otherwise, stop the process.
3. Repeat this process with the new number as long as you keep finding the number.

Return the final value of `original`.

Example 1:

``````Input: nums = [5,3,6,1,12], original = 3
Output: 24
Explanation:
- 3 is found in nums. 3 is multiplied by 2 to obtain 6.
- 6 is found in nums. 6 is multiplied by 2 to obtain 12.
- 12 is found in nums. 12 is multiplied by 2 to obtain 24.
``````

Example 2:

``````Input: nums = [2,7,9], original = 4
Output: 4
Explanation:
``````

Constraints:

• `1 <= nums.length <= 1000`
• `1 <= nums[i], original <= 1000`

### 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 lowbit(x) ((x) & (-(x)))
#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 findFinalValue(vector<int> &nums, int original) {
vector<int> vis(4096, 0);
for (const auto &a : nums) vis[a] = 1;
while (vis[original]) {
original <<= 1;
}

return original;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

• `numsleft` 包含 `nums` 中从下标 `0``i - 1` 的所有元素（包括 `0``i - 1`，而 `numsright` 包含 `nums` 中从下标 `i``n - 1` 的所有元素（包括 `i``n - 1` ）。
• 如果 `i == 0``numsleft` ，而 `numsright` 将包含 `nums` 中的所有元素。
• 如果 `i == n``numsleft` 将包含 `nums` 中的所有元素，而 `numsright`

``````输入：nums = [0,0,1,0]

- 0 ：numsleft 为 [] 。numsright 为 [0,0,1,0] 。得分为 0 + 1 = 1 。
- 1 ：numsleft 为 [0] 。numsright 为 [0,1,0] 。得分为 1 + 1 = 2 。
- 2 ：numsleft 为 [0,0] 。numsright 为 [1,0] 。得分为 2 + 1 = 3 。
- 3 ：numsleft 为 [0,0,1] 。numsright 为 [0] 。得分为 2 + 0 = 2 。
- 4 ：numsleft 为 [0,0,1,0] 。numsright 为 [] 。得分为 3 + 0 = 3 。

``````输入：nums = [0,0,0]

- 0 ：numsleft 为 [] 。numsright 为 [0,0,0] 。得分为 0 + 0 = 0 。
- 1 ：numsleft 为 [0] 。numsright 为 [0,0] 。得分为 1 + 0 = 1 。
- 2 ：numsleft 为 [0,0] 。numsright 为 [0] 。得分为 2 + 0 = 2 。
- 3 ：numsleft 为 [0,0,0] 。numsright 为 [] 。得分为 3 + 0 = 3 。

``````

``````输入：nums = [1,1]

- 0 ：numsleft 为 [] 。numsright 为 [1,1] 。得分为 0 + 2 = 2 。
- 1 ：numsleft 为 [1] 。numsright 为 [1] 。得分为 0 + 1 = 1 。
- 2 ：numsleft 为 [1,1] 。numsright 为 [] 。得分为 0 + 0 = 0 。

``````

• `n == nums.length`
• `1 <= n <= 105`
• `nums[i]``0``1`

You are given a 0-indexed binary array `nums` of length `n`. `nums` can be divided at index `i` (where `0 <= i <= n)` into two arrays (possibly empty) `numsleft` and `numsright`:

• `numsleft` has all the elements of `nums` between index `0` and `i - 1` (inclusive), while `numsright` has all the elements of nums between index `i` and `n - 1` (inclusive).
• If `i == 0`, `numsleft` is empty, while `numsright` has all the elements of `nums`.
• If `i == n`, `numsleft` has all the elements of nums, while `numsright` is empty.

The division score of an index `i` is the sum of the number of `0`'s in `numsleft` and the number of `1`'s in `numsright`.

Return all distinct indices that have the highest possible division score. You may return the answer in any order.

Example 1:

``````Input: nums = [0,0,1,0]
Output: [2,4]
Explanation: Division at index
- 0: numsleft is []. numsright is [0,0,1,0]. The score is 0 + 1 = 1.
- 1: numsleft is [0]. numsright is [0,1,0]. The score is 1 + 1 = 2.
- 2: numsleft is [0,0]. numsright is [1,0]. The score is 2 + 1 = 3.
- 3: numsleft is [0,0,1]. numsright is [0]. The score is 2 + 0 = 2.
- 4: numsleft is [0,0,1,0]. numsright is []. The score is 3 + 0 = 3.
Indices 2 and 4 both have the highest possible division score 3.
Note the answer [4,2] would also be accepted.``````

Example 2:

``````Input: nums = [0,0,0]
Output: [3]
Explanation: Division at index
- 0: numsleft is []. numsright is [0,0,0]. The score is 0 + 0 = 0.
- 1: numsleft is [0]. numsright is [0,0]. The score is 1 + 0 = 1.
- 2: numsleft is [0,0]. numsright is [0]. The score is 2 + 0 = 2.
- 3: numsleft is [0,0,0]. numsright is []. The score is 3 + 0 = 3.
Only index 3 has the highest possible division score 3.
``````

Example 3:

``````Input: nums = [1,1]
Output: [0]
Explanation: Division at index
- 0: numsleft is []. numsright is [1,1]. The score is 0 + 2 = 2.
- 1: numsleft is [1]. numsright is [1]. The score is 0 + 1 = 1.
- 2: numsleft is [1,1]. numsright is []. The score is 0 + 0 = 0.
Only index 0 has the highest possible division score 2.
``````

Constraints:

• `n == nums.length`
• `1 <= n <= 105`
• `nums[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 lowbit(x) ((x) & (-(x)))
#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:
vector<int> maxScoreIndices(vector<int> &nums) {
int n = nums.size();
vector<int> score(n + 5, 0);
int zero = 0;
for (int i = 0; i <= n; i++) {
score[i] += zero;
if (i < n && nums[i] == 0) {
++zero;
}
}

int one = 0;
for (int i = n; i >= 0; i--) {
if (i < n && nums[i] == 1) {
++one;
}

score[i] += one;
}

int Max = 0;
for (int i = 0; i <= n; i++) {
chmax(Max, score[i]);
}

vector<int> res;
for (int i = 0; i <= n; i++) {
if (score[i] == Max) {
res.push_back(i);
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

• Difficulty: Medium
• Tag: `字符串` `滑动窗口` `哈希函数` `滚动哈希`

• `hash(s, p, m) = (val(s[0]) * p0 + val(s[1]) * p1 + … + val(s[k-1]) * pk-1) mod m`.

``````输入：s = "leetcode", power = 7, modulo = 20, k = 2, hashValue = 0

"ee" 是长度为 2 的第一个哈希值为 0 的子串，所以我们返回 "ee" 。
``````

``````输入：s = "fbxzaad", power = 31, modulo = 100, k = 3, hashValue = 32

"bxz" 的哈希值为 hash("bxz", 31, 100) = (2 * 1 + 24 * 31 + 26 * 312) mod 100 = 25732 mod 100 = 32 。
"fbx" 是长度为 3 的第一个哈希值为 32 的子串，所以我们返回 "fbx" 。

``````

• `1 <= k <= s.length <= 2 * 104`
• `1 <= power, modulo <= 109`
• `0 <= hashValue < modulo`
• `s` 只包含小写英文字母。
• 测试数据保证一定 存在 满足条件的子串。

The hash of a 0-indexed string `s` of length `k`, given integers `p` and `m`, is computed using the following function:

• `hash(s, p, m) = (val(s[0]) * p0 + val(s[1]) * p1 + … + val(s[k-1]) * pk-1) mod m`.

Where `val(s[i])` represents the index of `s[i]` in the alphabet from `val('a') = 1` to `val('z') = 26`.

You are given a string `s` and the integers `power`, `modulo`, `k`, and `hashValue.` Return `sub`, the first substring of `s` of length `k` such that `hash(sub, power, modulo) == hashValue`.

The test cases will be generated such that an answer always exists.

A substring is a contiguous non-empty sequence of characters within a string.

Example 1:

``````Input: s = "leetcode", power = 7, modulo = 20, k = 2, hashValue = 0
Output: "ee"
Explanation: The hash of "ee" can be computed to be hash("ee", 7, 20) = (5 * 1 + 5 * 7) mod 20 = 40 mod 20 = 0.
"ee" is the first substring of length 2 with hashValue 0. Hence, we return "ee".
``````

Example 2:

``````Input: s = "fbxzaad", power = 31, modulo = 100, k = 3, hashValue = 32
Output: "fbx"
Explanation: The hash of "fbx" can be computed to be hash("fbx", 31, 100) = (6 * 1 + 2 * 31 + 24 * 312) mod 100 = 23132 mod 100 = 32.
The hash of "bxz" can be computed to be hash("bxz", 31, 100) = (2 * 1 + 24 * 31 + 26 * 312) mod 100 = 25732 mod 100 = 32.
"fbx" is the first substring of length 3 with hashValue 32. Hence, we return "fbx".
Note that "bxz" also has a hash of 32 but it appears later than "fbx".
``````

Constraints:

• `1 <= k <= s.length <= 2 * 104`
• `1 <= power, modulo <= 109`
• `0 <= hashValue < modulo`
• `s` consists of lowercase English letters only.
• The test cases are generated such that an answer always exists.

### 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 lowbit(x) ((x) & (-(x)))
#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 Hash {
ll base[N];
ll a[N];
ll p, mod;

void init(ll p, ll mod, int n) {
this->p = p;
this->mod = mod;

base[0] = 1;
for (int i = 1; i <= n; ++i) {
base[i] = base[i - 1] * p % mod;
}
}

void gao(string &s) {
int n = s.length();
a[0] = 0;
a[1] = s[0] - 'a' + 1;
for (int i = 1; i <= n; ++i) {
a[i] = ((a[i - 1] * p) % mod + (s[i - 1] - 'a' + 1)) % mod;
}
}

ll get(int l, int r) {
return (a[r] - a[l - 1] * base[r - l + 1] % mod + mod) % mod;
}
} hs;

class Solution {
public:
string subStrHash(string s, int p, int mod, int k, int hashValue) {
int n = s.length();

string t = s;
reverse(all(t));

hs.init(p, mod, n);
hs.gao(t);

string ans = "";

for (int i = 0; i + k <= n; i++) {
if (hs.get(i + 1, i + k) == hashValue) {
ans = s.substr(n - i - k, k);
}
}

return ans;
}
};

#ifdef LOCAL

int main() {
auto s = Solution();

{
auto ans = s.subStrHash("leetcode", 7, 20, 2, 0);
dbg(ans);
}

{
auto ans = s.subStrHash("fbxzaad", 31, 100, 3, 32);
dbg(ans);
}
return 0;
}

#endif
``````

## D

### Statement

• Difficulty: Hard
• Tag: `位运算` `并查集` `字符串`

• 往 `s1` 的字母集合中添加一个字母。
• 从 `s1` 的字母集合中删去一个字母。
• `s1` 中的一个字母替换成另外任意一个字母（也可以替换为这个字母本身）。

• `ans[0]` 是 `words` 分组后的 总组数 。
• `ans[1]` 是字符串数目最多的组所包含的字符串数目。

``````输入：words = ["a","b","ab","cde"]

- words[0] 可以得到 words[1] （将 'a' 替换为 'b'）和 words[2] （添加 'b'）。所以 words[0] 与 words[1] 和 words[2] 关联。
- words[1] 可以得到 words[0] （将 'b' 替换为 'a'）和 words[2] （添加 'a'）。所以 words[1] 与 words[0] 和 words[2] 关联。
- words[2] 可以得到 words[0] （删去 'b'）和 words[1] （删去 'a'）。所以 words[2] 与 words[0] 和 words[1] 关联。
- words[3] 与 words 中其他字符串都不关联。

``````

``````输入：words = ["a","ab","abc"]

- words[0] 与 words[1] 关联。
- words[1] 与 words[0] 和 words[2] 关联。
- words[2] 与 words[1] 关联。

``````

• `1 <= words.length <= 2 * 104`
• `1 <= words[i].length <= 26`
• `words[i]` 只包含小写英文字母。
• `words[i]` 中每个字母最多只出现一次。

• Difficulty: Hard
• Tag: `Bit Manipulation` `Union Find` `String`

You are given a 0-indexed array of strings `words`. Each string consists of lowercase English letters only. No letter occurs more than once in any string of `words`.

Two strings `s1` and `s2` are said to be connected if the set of letters of `s2` can be obtained from the set of letters of `s1` by any one of the following operations:

• Adding exactly one letter to the set of the letters of `s1`.
• Deleting exactly one letter from the set of the letters of `s1`.
• Replacing exactly one letter from the set of the letters of `s1` with any letter, including itself.

The array `words` can be divided into one or more non-intersecting groups. A string belongs to a group if any one of the following is true:

• It is connected to at least one other string of the group.
• It is the only string present in the group.

Note that the strings in `words` should be grouped in such a manner that a string belonging to a group cannot be connected to a string present in any other group. It can be proved that such an arrangement is always unique.

Return an array `ans` of size `2` where:

• `ans[0]` is the maximum number of groups `words` can be divided into, and
• `ans[1]` is the size of the largest group.

Example 1:

``````Input: words = ["a","b","ab","cde"]
Output: [2,3]
Explanation:
- words[0] can be used to obtain words[1] (by replacing 'a' with 'b'), and words[2] (by adding 'b'). So words[0] is connected to words[1] and words[2].
- words[1] can be used to obtain words[0] (by replacing 'b' with 'a'), and words[2] (by adding 'a'). So words[1] is connected to words[0] and words[2].
- words[2] can be used to obtain words[0] (by deleting 'b'), and words[1] (by deleting 'a'). So words[2] is connected to words[0] and words[1].
- words[3] is not connected to any string in words.
Thus, words can be divided into 2 groups ["a","b","ab"] and ["cde"]. The size of the largest group is 3.
``````

Example 2:

``````Input: words = ["a","ab","abc"]
Output: [1,3]
Explanation:
- words[0] is connected to words[1].
- words[1] is connected to words[0] and words[2].
- words[2] is connected to words[1].
Since all strings are connected to each other, they should be grouped together.
Thus, the size of the largest group is 3.
``````

Constraints:

• `1 <= words.length <= 2 * 104`
• `1 <= words[i].length <= 26`
• `words[i]` consists of lowercase English letters only.
• No letter occurs more than once in `words[i]`.

### 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 lowbit(x) ((x) & (-(x)))
#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 + 5;

struct UFS {
int fa[N], rk[N], sze[N];
void init(int n) {
for (int i = 1; i <= n; i++) {
fa[i] = 0;
rk[i] = 0;
sze[i] = 1;
}
}

int find(int x) {
return fa[x] == 0 ? x : fa[x] = find(fa[x]);
}

bool merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) {
if (rk[fx] > rk[fy]) {
swap(fx, fy);
}

fa[fx] = fy;
sze[fy] += sze[fx];
if (rk[fx] == rk[fy]) {
++rk[fy];
}

return true;
}
return false;
}

bool same(int x, int y) {
return find(x) == find(y);
}
} ufs;

class Solution {
public:
vector<int> groupStrings(vector<string>& words) {
constexpr auto f = [](string& s) {
ll res = 0;
for (auto& c : s) {
res |= 1ll << (c - 'a');
}

return res;
};

int n = words.size();
ufs.init(n + 1);

unordered_map<ll, int> mp;
vector<ll> vec;
vec.reserve(n);

for (int i = 0; i < n; i++) {
ll a = f(words[i]);
vec.push_back(a);
if (mp.count(a)) {
ufs.merge(mp[a] + 1, i + 1);
} else {
mp[a] = i;
}
}

for (int i = 0; i < n; i++) {
ll a = vec[i];
if (mp[a] != i) {
continue;
}

for (int j = 0; j < 26; j++) {
ll b = (a ^ (1ll << j));
if (mp.count(b)) {
ufs.merge(i + 1, mp[b] + 1);
}

if ((a >> j) & 1) {
ll _a = a ^ (1ll << j);
for (int k = 0; k < 26 && k != j; k++) {
if (((_a >> k) & 1) == 0) {
ll c = (_a ^ (1ll << k));
if (mp.count(c)) {
ufs.merge(i + 1, mp[c] + 1);
}
}
}
}
}
}

int cnt = 0, Max = 0;
for (int i = 0; i < n; i++) {
if (ufs.find(i + 1) == i + 1) {
++cnt;
chmax(Max, ufs.sze[i + 1]);
}
}

return vector<int>{cnt, Max};
}
};

#ifdef LOCAL

int main() {
auto s = Solution();
{
auto w = vector<string>{"a", "b", "ab", "cde"};
auto ans = s.groupStrings(w);
assert_eq(ans, {2, 3});
}

{
auto w = vector<string>{"web", "a", "te", "hsx", "v", "k", "a", "roh"};
auto ans = s.groupStrings(w);
assert_eq(ans, {5, 4});
}

return 0;
}

#endif
``````