# weekly-contest-205

## A

### Statement

``````输入：s = "?zs"

``````输入：s = "ubv?w"

``````

``````输入：s = "j?qg??b"

``````

``````输入：s = "??yw?ipkj?"

``````

• `1 <= s.length <= 100`

• `s` 仅包含小写英文字母和 `'?'` 字符

Given a string `s` containing only lowercase English letters and the `'?'` character, convert all the `'?'` characters into lowercase letters such that the final string does not contain any consecutive repeating characters. You cannot modify the non `'?'` characters.

It is guaranteed that there are no consecutive repeating characters in the given string except for `'?'`.

Return the final string after all the conversions (possibly zero) have been made. If there is more than one solution, return any of them. It can be shown that an answer is always possible with the given constraints.

Example 1:

``````Input: s = "?zs"
Output: "azs"
Explanation: There are 25 solutions for this problem. From "azs" to "yzs", all are valid. Only "z" is an invalid modification as the string will consist of consecutive repeating characters in "zzs".
``````

Example 2:

``````Input: s = "ubv?w"
Output: "ubvaw"
Explanation: There are 24 solutions for this problem. Only "v" and "w" are invalid modifications as the strings will consist of consecutive repeating characters in "ubvvw" and "ubvww".
``````

Constraints:

• `1 <= s.length <= 100`
• `s` consist of lowercase English letters and `'?'`.

### Solution

``````#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
x += y;
while (x >= Mod) x -= Mod;
while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
if (x < y)
x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
if (x > y)
x = y;
}
inline int nextInt() {
int x;
cin >> x;
return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
cin >> arg;
rd(args...);
}
#define dbg(x...)                             \
do {                                      \
cout << "\033[32;1m" << #x << " -> "; \
err(x);                               \
} while (0)
void err() {
cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
cout << arg << ' ';
err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
for (auto &v : arg) cout << v << ' ';
err(args...);
}
void ptt() {
cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
cout << ' ' << arg;
ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
cout << arg;
ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
pt(args...);
}
inline ll qpow(ll base, ll n) {
assert(n >= 0);
ll res = 1;
while (n) {
if (n & 1)
res = res * base % mod;
base = base * base % mod;
n >>= 1;
}
return res;
}
constexpr int N = 1e5 + 10;
int n;

class Solution {
public:
string modifyString(string s) {
n = SZ(s);
for (int i = 0; i < n; ++i) {
if (s[i] == '?') {
for (int j = 0; j < 26; ++j) {
if (i && j == s[i - 1] - 'a')
continue;
if (i < n - 1 && j == s[i + 1] - 'a')
continue;
s[i] = j + 'a';
}
}
}
return s;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

• 类型 1：三元组 `(i, j, k)` ，如果 `nums1[i]2 == nums2[j] * nums2[k]` 其中 `0 <= i < nums1.length``0 <= j < k < nums2.length`
• 类型 2：三元组 `(i, j, k)` ，如果 `nums2[i]2 == nums1[j] * nums1[k]` 其中 `0 <= i < nums2.length``0 <= j < k < nums1.length`

``````输入：nums1 = [7,4], nums2 = [5,2,8,9]

``````输入：nums1 = [1,1], nums2 = [1,1,1]

``````

``````输入：nums1 = [7,7,8,3], nums2 = [1,2,9,7]

``````

``````输入：nums1 = [4,7,9,11,23], nums2 = [3,5,1024,12,18]

``````

• `1 <= nums1.length, nums2.length <= 1000`
• `1 <= nums1[i], nums2[i] <= 10^5`

Given two arrays of integers `nums1` and `nums2`, return the number of triplets formed (type 1 and type 2) under the following rules:

• Type 1: Triplet (i, j, k) if `nums1[i]2 == nums2[j] * nums2[k]` where `0 <= i < nums1.length` and `0 <= j < k < nums2.length`.
• Type 2: Triplet (i, j, k) if `nums2[i]2 == nums1[j] * nums1[k]` where `0 <= i < nums2.length` and `0 <= j < k < nums1.length`.

Example 1:

``````Input: nums1 = [7,4], nums2 = [5,2,8,9]
Output: 1
Explanation: Type 1: (1, 1, 2), nums1[1]2 = nums2[1] * nums2[2]. (42 = 2 * 8).
``````

Example 2:

``````Input: nums1 = [1,1], nums2 = [1,1,1]
Output: 9
Explanation: All Triplets are valid, because 12 = 1 * 1.
Type 1: (0,0,1), (0,0,2), (0,1,2), (1,0,1), (1,0,2), (1,1,2).  nums1[i]2 = nums2[j] * nums2[k].
Type 2: (0,0,1), (1,0,1), (2,0,1). nums2[i]2 = nums1[j] * nums1[k].
``````

Example 3:

``````Input: nums1 = [7,7,8,3], nums2 = [1,2,9,7]
Output: 2
Explanation: There are 2 valid triplets.
Type 1: (3,0,2).  nums1[3]2 = nums2[0] * nums2[2].
Type 2: (3,0,1).  nums2[3]2 = nums1[0] * nums1[1].
``````

Constraints:

• `1 <= nums1.length, nums2.length <= 1000`
• `1 <= nums1[i], nums2[i] <= 105`

### Solution

``````#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
x += y;
while (x >= Mod) x -= Mod;
while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
if (x < y)
x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
if (x > y)
x = y;
}
inline int nextInt() {
int x;
cin >> x;
return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
cin >> arg;
rd(args...);
}
#define dbg(x...)                             \
do {                                      \
cout << "\033[32;1m" << #x << " -> "; \
err(x);                               \
} while (0)
void err() {
cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
cout << arg << ' ';
err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
for (auto &v : arg) cout << v << ' ';
err(args...);
}
void ptt() {
cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
cout << ' ' << arg;
ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
cout << arg;
ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
pt(args...);
}
inline ll qpow(ll base, ll n) {
assert(n >= 0);
ll res = 1;
while (n) {
if (n & 1)
res = res * base % mod;
base = base * base % mod;
n >>= 1;
}
return res;
}
constexpr int N = 1e5 + 10;
int n;
int cnt[N];

int sqr(ll x) {
int y = sqrt(x);
for (int i = max(1, y - 5); i <= y + 5; ++i) {
if (1ll * i * i == x)
return i;
}
return 0;
}

int gao(vector<int> nums1, vector<int> nums2) {
memset(cnt, 0, sizeof cnt);
for (auto &it : nums1) ++cnt[it];
int res = 0;
int n = SZ(nums2);
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
res += cnt[sqr(1ll * nums2[i] * nums2[j])];
}
}
return res;
}

class Solution {
public:
int numTriplets(vector<int> &nums1, vector<int> &nums2) {
int res = gao(nums1, nums2) + gao(nums2, nums1);
return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

Alice 把 `n` 个气球排列在一根绳子上。给你一个下标从 0 开始的字符串 `colors` ，其中 `colors[i]` 是第 `i` 个气球的颜色。

Alice 想要把绳子装扮成 彩色 ，且她不希望两个连续的气球涂着相同的颜色，所以她喊来 Bob 帮忙。Bob 可以从绳子上移除一些气球使绳子变成 彩色 。给你一个下标从 0 开始的整数数组 `neededTime` ，其中 `neededTime[i]` 是 Bob 从绳子上移除第 `i` 个气球需要的时间（以秒为单位）。

``````输入：colors = "abaac", neededTime = [1,2,3,4,5]

Bob 可以移除下标 2 的蓝色气球。这将花费 3 秒。

``````输入：colors = "abc", neededTime = [1,2,3]

``````

``````输入：colors = "aabaa", neededTime = [1,2,3,4,1]

``````

• `n == colors.length == neededTime.length`
• `1 <= n <= 105`
• `1 <= neededTime[i] <= 104`
• `colors` 仅由小写英文字母组成

Alice has `n` balloons arranged on a rope. You are given a 0-indexed string `colors` where `colors[i]` is the color of the `ith` balloon.

Alice wants the rope to be colorful. She does not want two consecutive balloons to be of the same color, so she asks Bob for help. Bob can remove some balloons from the rope to make it colorful. You are given a 0-indexed integer array `neededTime` where `neededTime[i]` is the time (in seconds) that Bob needs to remove the `ith` balloon from the rope.

Return the minimum time Bob needs to make the rope colorful.

Example 1:

``````Input: colors = "abaac", neededTime = [1,2,3,4,5]
Output: 3
Explanation: In the above image, 'a' is blue, 'b' is red, and 'c' is green.
Bob can remove the blue balloon at index 2. This takes 3 seconds.
There are no longer two consecutive balloons of the same color. Total time = 3.``````

Example 2:

``````Input: colors = "abc", neededTime = [1,2,3]
Output: 0
Explanation: The rope is already colorful. Bob does not need to remove any balloons from the rope.
``````

Example 3:

``````Input: colors = "aabaa", neededTime = [1,2,3,4,1]
Output: 2
Explanation: Bob will remove the ballons at indices 0 and 4. Each ballon takes 1 second to remove.
There are no longer two consecutive balloons of the same color. Total time = 1 + 1 = 2.
``````

Constraints:

• `n == colors.length == neededTime.length`
• `1 <= n <= 105`
• `1 <= neededTime[i] <= 104`
• `colors` contains only lowercase English letters.

### Solution

``````#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
x += y;
while (x >= Mod) x -= Mod;
while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
if (x < y)
x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
if (x > y)
x = y;
}
inline int nextInt() {
int x;
cin >> x;
return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
cin >> arg;
rd(args...);
}
#define dbg(x...)                             \
do {                                      \
cout << "\033[32;1m" << #x << " -> "; \
err(x);                               \
} while (0)
void err() {
cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
cout << arg << ' ';
err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
for (auto &v : arg) cout << v << ' ';
err(args...);
}
void ptt() {
cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
cout << ' ' << arg;
ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
cout << arg;
ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
pt(args...);
}
inline ll qpow(ll base, ll n) {
assert(n >= 0);
ll res = 1;
while (n) {
if (n & 1)
res = res * base % mod;
base = base * base % mod;
n >>= 1;
}
return res;
}
constexpr int N = 1e5 + 10;
int n;
int f[N][30];

class Solution {
public:
int minCost(string s, vector<int> &cost) {
n = SZ(s);
memset(f, 0x3f, sizeof f);
memset(f[0], 0, sizeof f[0]);
for (int i = 1; i <= n; ++i) {
int ch = s[i - 1] - 'a';
int fee = cost[i - 1];
for (int j = 0; j < 26; ++j) {
if (j != ch) {
chmin(f[i][ch], f[i - 1][j]);
chmin(f[i][j], f[i - 1][j] + fee);
} else {
chmin(f[i][j], f[i - 1][j] + fee);
}
}
}
int res = 2e9;
for (int i = 0; i < 26; ++i) chmin(res, f[n][i]);
return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

Alice 和 Bob 共有一个无向图，其中包含 n 个节点和 3  种类型的边：

• 类型 1：只能由 Alice 遍历。
• 类型 2：只能由 Bob 遍历。
• 类型 3：Alice 和 Bob 都可以遍历。

``````输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]

``````

``````输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]

``````

``````输入：n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]

• `1 <= n <= 10^5`
• `1 <= edges.length <= min(10^5, 3 * n * (n-1) / 2)`
• `edges[i].length == 3`
• `1 <= edges[i][0] <= 3`
• `1 <= edges[i][1] < edges[i][2] <= n`
• 所有元组 `(typei, ui, vi)` 互不相同

Alice and Bob have an undirected graph of `n` nodes and 3 types of edges:

• Type 1: Can be traversed by Alice only.
• Type 2: Can be traversed by Bob only.
• Type 3: Can by traversed by both Alice and Bob.

Given an array `edges` where `edges[i] = [typei, ui, vi]` represents a bidirectional edge of type `typei` between nodes `ui` and `vi`, find the maximum number of edges you can remove so that after removing the edges, the graph can still be fully traversed by both Alice and Bob. The graph is fully traversed by Alice and Bob if starting from any node, they can reach all other nodes.

Return the maximum number of edges you can remove, or return `-1` if it's impossible for the graph to be fully traversed by Alice and Bob.

Example 1:

``````Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
Output: 2
Explanation: If we remove the 2 edges [1,1,2] and [1,1,3]. The graph will still be fully traversable by Alice and Bob. Removing any additional edge will not make it so. So the maximum number of edges we can remove is 2.
``````

Example 2:

``````Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]
Output: 0
Explanation: Notice that removing any edge will not make the graph fully traversable by Alice and Bob.
``````

Example 3:

``````Input: n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]
Output: -1
Explanation: In the current graph, Alice cannot reach node 4 from the other nodes. Likewise, Bob cannot reach 1. Therefore it's impossible to make the graph fully traversable.``````

Constraints:

• `1 <= n <= 10^5`
• `1 <= edges.length <= min(10^5, 3 * n * (n-1) / 2)`
• `edges[i].length == 3`
• `1 <= edges[i][0] <= 3`
• `1 <= edges[i][1] < edges[i][2] <= n`
• All tuples `(typei, ui, vi)` are distinct.

### Solution

``````#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
x += y;
while (x >= Mod) x -= Mod;
while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
if (x < y)
x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
if (x > y)
x = y;
}
inline int nextInt() {
int x;
cin >> x;
return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
cin >> arg;
rd(args...);
}
#define dbg(x...)                             \
do {                                      \
cout << "\033[32;1m" << #x << " -> "; \
err(x);                               \
} while (0)
void err() {
cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
cout << arg << ' ';
err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
for (auto &v : arg) cout << v << ' ';
err(args...);
}
void ptt() {
cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
cout << ' ' << arg;
ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
cout << arg;
ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
pt(args...);
}
inline ll qpow(ll base, ll n) {
assert(n >= 0);
ll res = 1;
while (n) {
if (n & 1)
res = res * base % mod;
base = base * base % mod;
n >>= 1;
}
return res;
}
constexpr int N = 1e5 + 10;
int n;
vector<vector<int>> edges;

struct UFS {
int fa[N], rk[N];
void init(int n) {
memset(fa, 0, sizeof(fa[0]) * (n + 5));
memset(rk, 0, sizeof(rk[0]) * (n + 5));
}
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;
if (rk[fx] == rk[fy])
++rk[fy];
return true;
}
return false;
}
bool same(int x, int y) {
return find(x) == find(y);
}
} ufs[3];

int gao() {
ufs[0].init(n);
ufs[1].init(n);
ufs[2].init(n);
int res = 0;
for (auto &it : edges) {
int tp = it[0], u = it[1], v = it[2];
if (tp == 3) {
res += ufs[0].merge(u, v) ^ 1;
}
}
ufs[1] = ufs[2] = ufs[0];
for (int i = 1; i <= 2; ++i) {
for (auto &it : edges) {
int tp = it[0], u = it[1], v = it[2];
if (tp == i) {
res += ufs[i].merge(u, v) ^ 1;
}
}
int cnt = 0;
for (int j = 1; j <= n; ++j) {
cnt += ufs[i].fa[j] == 0;
}
if (cnt > 1)
return -1;
}
return res;
}

class Solution {
public:
int maxNumEdgesToRemove(int _n, vector<vector<int>> &_edges) {
n = _n;
edges = _edges;
return gao();
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````