# biweekly-contest-33

## A

### Statement

``````输入：n = 987

``````

``````输入：n = 1234

``````

``````输入：n = 123456789

``````

``````输入：n = 0

``````

• `0 <= n < 2^31`

Given an integer `n`, add a dot (".") as the thousands separator and return it in string format.

Example 1:

``````Input: n = 987
Output: "987"
``````

Example 2:

``````Input: n = 1234
Output: "1.234"
``````

Constraints:

• `0 <= n <= 231 - 1`

### 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 thousandSeparator(int n) {
int x = n;
if (!x)
return "0";
vector<int> vec;
while (x) {
vec.push_back(x % 10);
x /= 10;
}
//		reverse(all(vec));
string res = "";
for (int i = 0; i < SZ(vec); ++i) {
if (i && i % 3 == 0)
res += ".";
res += vec[i] + '0';
}
reverse(all(res));
return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

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

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

``````

• `2 <= n <= 10^5`
• `1 <= edges.length <= min(10^5, n * (n - 1) / 2)`
• `edges[i].length == 2`
• `0 <= fromi, toi < n`
• 所有点对 `(fromi, toi)` 互不相同。

Given a directed acyclic graph, with `n` vertices numbered from `0` to `n-1`, and an array `edges` where `edges[i] = [fromi, toi]` represents a directed edge from node `fromi` to node `toi`.

Find the smallest set of vertices from which all nodes in the graph are reachable. It's guaranteed that a unique solution exists.

Notice that you can return the vertices in any order.

Example 1:

``````
Input: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
Output: [0,3]
Explanation: It's not possible to reach all the nodes from a single vertex. From 0 we can reach [0,1,2,5]. From 3 we can reach [3,4,2,5]. So we output [0,3].``````

Example 2:

``````
Input: n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]
Output: [0,2,3]
Explanation: Notice that vertices 0, 3 and 2 are not reachable from any other node, so we must include them. Also any of these vertices can reach nodes 1 and 4.
``````

Constraints:

• `2 <= n <= 10^5`
• `1 <= edges.length <= min(10^5, n * (n - 1) / 2)`
• `edges[i].length == 2`
• `0 <= fromi, toi < n`
• All pairs `(fromi, toi)` 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;
int d[N];

class Solution {
public:
vector<int> findSmallestSetOfVertices(int n, vector<vector<int>> &edges) {
for (int i = 0; i <= n; ++i) d[i] = 0;
for (auto &it : edges) {
int u = it[0], v = it[1];
++d[v];
}
vector<int> res;
for (int i = 0; i < n; ++i)
if (!d[i])
res.push_back(i);
return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

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

``````

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

``````

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

``````

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

``````

``````输入：nums = [2,4,8,16]

``````

• `1 <= nums.length <= 10^5`
• `0 <= nums[i] <= 10^9`

You are given an integer array `nums`. You have an integer array `arr` of the same length with all values set to `0` initially. You also have the following `modify` function:

You want to use the modify function to covert `arr` to `nums` using the minimum number of calls.

Return the minimum number of function calls to make `nums` from `arr`.

The test cases are generated so that the answer fits in a 32-bit signed integer.

Example 1:

``````Input: nums = [1,5]
Output: 5
Explanation: Increment by 1 (second element): [0, 0] to get [0, 1] (1 operation).
Double all the elements: [0, 1] -> [0, 2] -> [0, 4] (2 operations).
Increment by 1 (both elements)  [0, 4] -> [1, 4] -> [1, 5] (2 operations).
Total of operations: 1 + 2 + 2 = 5.
``````

Example 2:

``````Input: nums = [2,2]
Output: 3
Explanation: Increment by 1 (both elements) [0, 0] -> [0, 1] -> [1, 1] (2 operations).
Double all the elements: [1, 1] -> [2, 2] (1 operation).
Total of operations: 2 + 1 = 3.
``````

Example 3:

``````Input: nums = [4,2,5]
Output: 6
Explanation: (initial)[0,0,0] -> [1,0,0] -> [1,0,1] -> [2,0,2] -> [2,1,2] -> [4,2,4] -> [4,2,5](nums).
``````

Constraints:

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

### 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:
int minOperations(vector<int> &nums) {
ll res = 0;
int Max = 0;
for (auto &it : nums) {
int now = 0;
while (it) {
if (it % 2 == 0) {
++now;
it /= 2;
} else {
++res;
--it;
}
}
chmax(Max, now);
}
return res + Max;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

• Difficulty: Medium
• Tag: `深度优先搜索` `广度优先搜索` `并查集` `数组` `矩阵`

``````输入：grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]

``````

``````输入：grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]

``````

``````输入：grid = [["a","b","b"],["b","z","b"],["b","b","a"]]

``````

• `m == grid.length`
• `n == grid[i].length`
• `1 <= m <= 500`
• `1 <= n <= 500`
• `grid` 只包含小写英文字母。

• Link: Detect Cycles in 2D Grid
• Difficulty: Medium
• Tag: `Depth-First Search` `Breadth-First Search` `Union Find` `Array` `Matrix`

Given a 2D array of characters `grid` of size `m x n`, you need to find if there exists any cycle consisting of the same value in `grid`.

A cycle is a path of length 4 or more in the grid that starts and ends at the same cell. From a given cell, you can move to one of the cells adjacent to it - in one of the four directions (up, down, left, or right), if it has the same value of the current cell.

Also, you cannot move to the cell that you visited in your last move. For example, the cycle `(1, 1) -> (1, 2) -> (1, 1)` is invalid because from `(1, 2)` we visited `(1, 1)` which was the last visited cell.

Return `true` if any cycle of the same value exists in `grid`, otherwise, return `false`.

Example 1:

``````Input: grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]
Output: true
Explanation: There are two valid cycles shown in different colors in the image below:

``````

Example 2:

``````Input: grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]
Output: true
Explanation: There is only one valid cycle highlighted in the image below:

``````

Example 3:

``````Input: grid = [["a","b","b"],["b","z","b"],["b","b","a"]]
Output: false
``````

Constraints:

• `m == grid.length`
• `n == grid[i].length`
• `1 <= m, n <= 500`
• `grid` consists only of 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 = 500 * 500 + 10;
int n, m;
vector<vector<int>> G;
int Move[4][2] = {-1, 0, 1, 0, 0, 1, 0, -1};
int vis[N], fa[N], g[510][510];
int has;

void dfs(int u) {
vis[u] = 1;
for (auto &v : G[u])
if (v != fa[u]) {
fa[v] = u;
if (vis[v]) {
has = 1;
return;
}
dfs(v);
if (has)
return;
}
}

bool valid(int x, int y) {
if (x < 0 || x > n || y < 0 || y > m)
return false;
return true;
}

bool ok(vector<pII> &vec) {
int _n = SZ(vec);
G.clear();
G.resize(_n + 1);
for (int i = 0; i < _n; ++i) {
g[vec[i].fi][vec[i].se] = i + 1;
vis[i + 1] = 0;
fa[i + 1] = 0;
}
has = 0;
//	pt("-----");
for (int i = 0; i < _n; ++i) {
int x = vec[i].fi, y = vec[i].se, u = i + 1;
for (int j = 0; j < 4; ++j) {
int nx = x + Move[j][0];
int ny = y + Move[j][1];
if (valid(nx, ny) && g[nx][ny]) {
int v = g[nx][ny];
G[u].push_back(v);
//	pt(u, v);
}
}
}
//	pt("-----------");
for (int i = 0; i < _n; ++i) {
g[vec[i].fi][vec[i].se] = 0;
}
for (int i = 1; i <= _n; ++i) {
if (!vis[i]) {
dfs(i);
//	if (has) pt(i);
if (has)
return true;
}
}
return false;
}

class Solution {
public:
bool containsCycle(vector<vector<char>> &grid) {
n = SZ(grid);
m = SZ(grid[0]);
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= m; ++j) g[i][j] = 0;
vector<pII> vec[30];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
vec[grid[i][j] - 'a'].push_back(pII(i, j));
}
}
for (int i = 0; i < 26; ++i) {
if (SZ(vec[i]) && ok(vec[i]))
return true;
}
return false;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````