# biweekly-contest-81

## A

### Statement

``````输入：s = "l|*e*et|c**o|*de|"

``````输入：s = "iamprogrammer"

``````

``````输入：s = "yo|uar|e**|b|e***au|tifu|l"

• `1 <= s.length <= 1000`
• `s` 只包含小写英文字母，竖线 `'|'` 和星号 `'*'` 。
• `s` 包含 偶数 个竖线 `'|'`

You are given a string `s`, where every two consecutive vertical bars `'|'` are grouped into a pair. In other words, the 1st and 2nd `'|'` make a pair, the 3rd and 4th `'|'` make a pair, and so forth.

Return the number of `'*'` in `s`, excluding the `'*'` between each pair of `'|'`.

Note that each `'|'` will belong to exactly one pair.

Example 1:

``````Input: s = "l|*e*et|c**o|*de|"
Output: 2
Explanation: The considered characters are underlined: "l|*e*et|c**o|*de|".
The characters between the first and second '|' are excluded from the answer.
Also, the characters between the third and fourth '|' are excluded from the answer.
There are 2 asterisks considered. Therefore, we return 2.``````

Example 2:

``````Input: s = "iamprogrammer"
Output: 0
Explanation: In this example, there are no asterisks in s. Therefore, we return 0.
``````

Example 3:

``````Input: s = "yo|uar|e**|b|e***au|tifu|l"
Output: 5
Explanation: The considered characters are underlined: "yo|uar|e**|b|e***au|tifu|l". There are 5 asterisks considered. Therefore, we return 5.``````

Constraints:

• `1 <= s.length <= 1000`
• `s` consists of lowercase English letters, vertical bars `'|'`, and asterisks `'*'`.
• `s` contains an even number of vertical bars `'|'`.

### 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

class Solution {
public:
int countAsterisks(const string &s) {
int flag = 1;
int res = 0;
for (const char &c : s) {
if (c == '*') {
res += flag;
}

if (c == '|') {
flag ^= 1;
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

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

``````

``````输入：n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]

[[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]]

``````

• `1 <= n <= 105`
• `0 <= edges.length <= 2 * 105`
• `edges[i].length == 2`
• `0 <= ai, bi < n`
• `ai != bi`
• 不会有重复边。

You are given an integer `n`. There is an undirected graph with `n` nodes, numbered from `0` to `n - 1`. You are given a 2D integer array `edges` where `edges[i] = [ai, bi]` denotes that there exists an undirected edge connecting nodes `ai` and `bi`.

Return the number of pairs of different nodes that are unreachable from each other.

Example 1:

``````Input: n = 3, edges = [[0,1],[0,2],[1,2]]
Output: 0
Explanation: There are no pairs of nodes that are unreachable from each other. Therefore, we return 0.
``````

Example 2:

``````Input: n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
Output: 14
Explanation: There are 14 pairs of nodes that are unreachable from each other:
[[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]].
Therefore, we return 14.
``````

Constraints:

• `1 <= n <= 105`
• `0 <= edges.length <= 2 * 105`
• `edges[i].length == 2`
• `0 <= ai, bi < n`
• `ai != bi`
• There are no repeated edges.

### 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

constexpr int N = 1e5 + 10;

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

class Solution {
public:
long long countPairs(int n, vector<vector<int>> &edges) {
ufs.init(n);

for (auto &e : edges) {
ufs.merge(e[0] + 1, e[1] + 1);
}

auto f = vector<int>();

for (int i = 1; i <= n; i++) {
if (ufs.find(i) == i) {
f.push_back(ufs.sz[i]);
}
}

ll sum = f[0];
ll res = 0;
for (size_t i = 1; i < f.size(); i++) {
res += f[i] * sum;
sum += f[i];
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

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

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

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

You are given a 0-indexed integer array `nums`. In one operation, select any non-negative integer `x` and an index `i`, then update `nums[i]` to be equal to `nums[i] AND (nums[i] XOR x)`.

Note that `AND` is the bitwise AND operation and `XOR` is the bitwise XOR operation.

Return the maximum possible bitwise XOR of all elements of `nums` after applying the operation any number of times.

Example 1:

``````Input: nums = [3,2,4,6]
Output: 7
Explanation: Apply the operation with x = 4 and i = 3, num[3] = 6 AND (6 XOR 4) = 6 AND 2 = 2.
Now, nums = [3, 2, 4, 2] and the bitwise XOR of all the elements = 3 XOR 2 XOR 4 XOR 2 = 7.
It can be shown that 7 is the maximum possible bitwise XOR.
Note that other operations may be used to achieve a bitwise XOR of 7.``````

Example 2:

``````Input: nums = [1,2,3,9,2]
Output: 11
Explanation: Apply the operation zero times.
The bitwise XOR of all the elements = 1 XOR 2 XOR 3 XOR 9 XOR 2 = 11.
It can be shown that 11 is the maximum possible bitwise XOR.``````

Constraints:

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

### 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

class Solution {
public:
int maximumXOR(vector<int> &nums) {
int res = 0;

for (auto &a : nums) {
res |= a;
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

1. 序列中任意 相邻 数字的 最大公约数 为 `1` 。
2. 序列中 相等 的值之间，至少有 `2` 个其他值的数字。正式地，如果第 `i` 次掷骰子的值 等于 第 `j` 次的值，那么 `abs(i - j) > 2` 。

``````输入：n = 4

(1, 2, 1, 3) 是不可行的，因为第一个和第三个骰子值相等且 abs(1 - 3) = 2 （下标从 1 开始表示）。
(1, 2, 3, 6) i是不可行的，因为 3 和 6 的最大公约数是 3 。

``````输入：n = 2

``````

• `1 <= n <= 104`

You are given an integer `n`. You roll a fair 6-sided dice `n` times. Determine the total number of distinct sequences of rolls possible such that the following conditions are satisfied:

1. The greatest common divisor of any adjacent values in the sequence is equal to `1`.
2. There is at least a gap of `2` rolls between equal valued rolls. More formally, if the value of the `ith` roll is equal to the value of the `jth` roll, then `abs(i - j) > 2`.

Return the total number of distinct sequences possible. Since the answer may be very large, return it modulo `109 + 7`.

Two sequences are considered distinct if at least one element is different.

Example 1:

``````Input: n = 4
Output: 184
Explanation: Some of the possible sequences are (1, 2, 3, 4), (6, 1, 2, 3), (1, 2, 3, 1), etc.
Some invalid sequences are (1, 2, 1, 3), (1, 2, 3, 6).
(1, 2, 1, 3) is invalid since the first and third roll have an equal value and abs(1 - 3) = 2 (i and j are 1-indexed).
(1, 2, 3, 6) is invalid since the greatest common divisor of 3 and 6 = 3.
There are a total of 184 distinct sequences possible, so we return 184.``````

Example 2:

``````Input: n = 2
Output: 22
Explanation: Some of the possible sequences are (1, 2), (2, 1), (3, 2).
Some invalid sequences are (3, 6), (2, 4) since the greatest common divisor is not equal to 1.
There are a total of 22 distinct sequences possible, so we return 22.
``````

Constraints:

• `1 <= n <= 104`

### 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

const int mod = 1e9 + 7;

// 1 2 1 3
// 1 2 3 6

class Solution {
public:
int distinctSequences(int n) {
static auto f = std::invoke([]() {
auto f = vector<vector<ll>>(1e4 + 5, vector<ll>(10, 0));
auto g = vector<vector<ll>>(1e4 + 5, vector<ll>(10, 0));

const int n = 1e4;

for (int i = 1; i <= 6; i++) {
f[1][i] = 1;
g[1][i] = 1;
}

for (int i = 2; i <= n; i++) {
for (int j = 1; j <= 6; j++) {
for (int k = 1; k <= 6; k++) {
if (j == k || __gcd(j, k) != 1) {
continue;
}

f[i][j] += f[i - 1][k];
f[i][j] %= mod;

f[i][j] -= g[i - 2][j];
f[i][j] += mod;
f[i][j] %= mod;

if (i >= 3) {
f[i][j] += g[i - 3][k];
f[i][j] %= mod;
}
}

g[i][j] = f[i][j] + g[i - 2][j];
g[i][j] %= mod;
}
}

return f;
});

ll res = 0;
for (int i = 1; i <= 6; i++) {
res += f[n][i];
res %= mod;
}

return res;

// return ans[n - 1];

// static auto f = std::invoke([]() {
//     auto res = vector<int>(15);

//     auto dfs = [&res](auto &&dfs, int n, vector<int> &vec) {
//         if (vec.size() == (size_t)n) {
//             ++res[n];
//             return;
//         }

//         for (int i = 1; i <= 6; i++) {
//             if (!vec.empty()) {
//                 if (vec.back() == i) {
//                     continue;
//                 }

//                 if (__gcd(vec.back(), i) != 1) {
//                     continue;
//                 }

//                 if (vec.size() >= 2 && vec.end()[-2] == i) {
//                     continue;
//                 }
//             }

//             vec.push_back(i);
//             dfs(dfs, n, vec);
//             vec.pop_back();
//         }
//     };

//     for (int i = 1; i <= 15; i++) {
//         auto tmp = vector<int>();
//         dfs(dfs, i, tmp);
//     }

//     return res;
// });

// return f[n];
}
};

#ifdef LOCAL

int main() {
auto s = Solution();
for (int i = 1; i <= 15; i++) {
cout << s.distinctSequences(i) << ",";
}

return 0;
}

#endif
``````