# weekly-contest-203

## A

### Statement

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

1 –> 2 –> 3（阶段 1 结束）–> 4 –> 1（阶段 2 结束）–> 2（阶段 3 结束，即本场马拉松结束）

``````输入：n = 2, rounds = [2,1,2,1,2,1,2,1,2]

``````

``````输入：n = 7, rounds = [1,3,5,7]

``````

• `2 <= n <= 100`
• `1 <= m <= 100`
• `rounds.length == m + 1`
• `1 <= rounds[i] <= n`
• `rounds[i] != rounds[i + 1]` ，其中 `0 <= i < m`

Given an integer `n` and an integer array `rounds`. We have a circular track which consists of `n` sectors labeled from `1` to `n`. A marathon will be held on this track, the marathon consists of `m` rounds. The `ith` round starts at sector `rounds[i - 1]` and ends at sector `rounds[i]`. For example, round 1 starts at sector `rounds[0]` and ends at sector `rounds[1]`

Return an array of the most visited sectors sorted in ascending order.

Notice that you circulate the track in ascending order of sector numbers in the counter-clockwise direction (See the first example).

Example 1:

``````Input: n = 4, rounds = [1,3,1,2]
Output: [1,2]
Explanation: The marathon starts at sector 1. The order of the visited sectors is as follows:
1 –> 2 –> 3 (end of round 1) –> 4 –> 1 (end of round 2) –> 2 (end of round 3 and the marathon)
We can see that both sectors 1 and 2 are visited twice and they are the most visited sectors. Sectors 3 and 4 are visited only once.``````

Example 2:

``````Input: n = 2, rounds = [2,1,2,1,2,1,2,1,2]
Output: [2]
``````

Example 3:

``````Input: n = 7, rounds = [1,3,5,7]
Output: [1,2,3,4,5,6,7]
``````

Constraints:

• `2 <= n <= 100`
• `1 <= m <= 100`
• `rounds.length == m + 1`
• `1 <= rounds[i] <= n`
• `rounds[i] != rounds[i + 1]` for `0 <= i < m`

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

class Solution {
public:
vector<int> mostVisited(int n, vector<int> &rounds) {
for (int i = 0; i <= n; ++i) cnt[i] = 0;
int m = SZ(rounds);
int i = 1;
int pos = rounds[0] - 1;
//	++cnt[pos];
while (i < m) {
++pos;
++cnt[pos];
if (pos == rounds[i])
++i;
//		pt(i, pos);
if (pos == n)
pos = 0;
}
vector<int> res;
int Max = 0;
for (int i = 1; i <= n; ++i) {
if (cnt[i] == Max) {
res.push_back(i);
} else if (cnt[i] > Max) {
res.clear();
//	pt(i);
res.push_back(i);
Max = cnt[i];
}
}
return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

• 每一轮中，你将会选出 任意 3 堆硬币（不一定连续）。
• Alice 将会取走硬币数量最多的那一堆。
• 你将会取走硬币数量第二多的那一堆。
• Bob 将会取走最后一堆。
• 重复这个过程，直到没有更多硬币。

``````输入：piles = [2,4,1,2,7,8]

``````

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

``````

``````输入：piles = [9,8,7,6,5,1,2,3,4]

``````

• `3 <= piles.length <= 10^5`
• `piles.length % 3 == 0`
• `1 <= piles[i] <= 10^4`

• Link: Maximum Number of Coins You Can Get
• Difficulty: Medium
• Tag: `Greedy` `Array` `Math` `Game Theory` `Sorting`

There are `3n` piles of coins of varying size, you and your friends will take piles of coins as follows:

• In each step, you will choose any `3` piles of coins (not necessarily consecutive).
• Of your choice, Alice will pick the pile with the maximum number of coins.
• You will pick the next pile with the maximum number of coins.
• Your friend Bob will pick the last pile.
• Repeat until there are no more piles of coins.

Given an array of integers `piles` where `piles[i]` is the number of coins in the `ith` pile.

Return the maximum number of coins that you can have.

Example 1:

``````Input: piles = [2,4,1,2,7,8]
Output: 9
Explanation: Choose the triplet (2, 7, 8), Alice Pick the pile with 8 coins, you the pile with 7 coins and Bob the last one.
Choose the triplet (1, 2, 4), Alice Pick the pile with 4 coins, you the pile with 2 coins and Bob the last one.
The maximum number of coins which you can have are: 7 + 2 = 9.
On the other hand if we choose this arrangement (1, 2, 8), (2, 4, 7) you only get 2 + 4 = 6 coins which is not optimal.
``````

Example 2:

``````Input: piles = [2,4,5]
Output: 4
``````

Example 3:

``````Input: piles = [9,8,7,6,5,1,2,3,4]
Output: 18
``````

Constraints:

• `3 <= piles.length <= 105`
• `piles.length % 3 == 0`
• `1 <= piles[i] <= 104`

### 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 maxCoins(vector<int> &piles) {
int n = SZ(piles);
sort(all(piles));
int sz = n / 3;
int res = 0;
while (sz--) {
int a = piles.back();
piles.pop_back();
int b = piles.back();
piles.pop_back();
res += b;
}
return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

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

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

``````

``````输入：arr = [1], m = 1

``````

``````输入：arr = [2,1], m = 2

``````

• `n == arr.length`
• `1 <= n <= 10^5`
• `1 <= arr[i] <= n`
• `arr` 中的所有整数 互不相同
• `1 <= m <= arr.length`

Given an array `arr` that represents a permutation of numbers from `1` to `n`.

You have a binary string of size `n` that initially has all its bits set to zero. At each step `i` (assuming both the binary string and `arr` are 1-indexed) from `1` to `n`, the bit at position `arr[i]` is set to `1`.

You are also given an integer `m`. Find the latest step at which there exists a group of ones of length `m`. A group of ones is a contiguous substring of `1`'s such that it cannot be extended in either direction.

Return the latest step at which there exists a group of ones of length exactly `m`. If no such group exists, return `-1`.

Example 1:

``````Input: arr = [3,5,1,2,4], m = 1
Output: 4
Explanation:
Step 1: "00100", groups: ["1"]
Step 2: "00101", groups: ["1", "1"]
Step 3: "10101", groups: ["1", "1", "1"]
Step 4: "11101", groups: ["111", "1"]
Step 5: "11111", groups: ["11111"]
The latest step at which there exists a group of size 1 is step 4.
``````

Example 2:

``````Input: arr = [3,1,5,4,2], m = 2
Output: -1
Explanation:
Step 1: "00100", groups: ["1"]
Step 2: "10100", groups: ["1", "1"]
Step 3: "10101", groups: ["1", "1", "1"]
Step 4: "10111", groups: ["1", "111"]
Step 5: "11111", groups: ["11111"]
No group of size 2 exists during any step.
``````

Constraints:

• `n == arr.length`
• `1 <= m <= n <= 105`
• `1 <= arr[i] <= n`
• All integers in `arr` 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 cnt[N];

class Solution {
public:
int findLatestStep(vector<int> &arr, int m) {
set<pII> se;
int n = SZ(arr);
for (int i = 0; i <= n; ++i) cnt[i] = 0;
int res = -1;
for (int i = 0; i < n; ++i) {
int x = arr[i];
if (se.empty()) {
se.insert(pII(x, x));
++cnt[1];
} else {
auto pos = se.lower_bound(pII(x, x));
auto pre = prev(pos);
int l = x, r = x;
if (pre != se.end() && pre->se == x - 1) {
--cnt[pre->se - pre->fi + 1];
l = pre->fi;
se.erase(pre);
}
if (pos != se.end() && pos->fi == x + 1) {
--cnt[pos->se - pos->fi + 1];
r = pos->se;
se.erase(pos);
}
++cnt[r - l + 1];
se.insert(pII(l, r));
}
if (cnt[m])
res = i + 1;
}
return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

• Difficulty: Hard
• Tag: `数组` `数学` `动态规划` `博弈`

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

``````

``````输入：stoneValue = [7,7,7,7,7,7,7]

``````

``````输入：stoneValue = [4]

``````

• `1 <= stoneValue.length <= 500`
• `1 <= stoneValue[i] <= 10^6`

• Difficulty: Hard
• Tag: `Array` `Math` `Dynamic Programming` `Game Theory`

There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array `stoneValue`.

In each round of the game, Alice divides the row into two non-empty rows (i.e. left row and right row), then Bob calculates the value of each row which is the sum of the values of all the stones in this row. Bob throws away the row which has the maximum value, and Alice's score increases by the value of the remaining row. If the value of the two rows are equal, Bob lets Alice decide which row will be thrown away. The next round starts with the remaining row.

The game ends when there is only one stone remaining. Alice's is initially zero.

Return the maximum score that Alice can obtain.

Example 1:

``````Input: stoneValue = [6,2,3,4,5,5]
Output: 18
Explanation: In the first round, Alice divides the row to [6,2,3], [4,5,5]. The left row has the value 11 and the right row has value 14. Bob throws away the right row and Alice's score is now 11.
In the second round Alice divides the row to [6], [2,3]. This time Bob throws away the left row and Alice's score becomes 16 (11 + 5).
The last round Alice has only one choice to divide the row which is [2], [3]. Bob throws away the right row and Alice's score is now 18 (16 + 2). The game ends because only one stone is remaining in the row.
``````

Example 2:

``````Input: stoneValue = [7,7,7,7,7,7,7]
Output: 28
``````

Example 3:

``````Input: stoneValue = [4]
Output: 0
``````

Constraints:

• `1 <= stoneValue.length <= 500`
• `1 <= stoneValue[i] <= 106`

### 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 = 5e2 + 10;
// int n;
int a[N], sum[N], f[N][N];

int dfs(int l, int r) {
if (l >= r)
return 0;
if (f[l][r] != -1)
return f[l][r];
int tot = sum[r] - sum[l - 1];
int now = 0;
int Max = 0;
for (int i = l; i <= r; ++i) {
now += a[i];
int oth = tot - now;
if (now < oth) {
chmax(Max, dfs(l, i) + now);
} else if (now == oth) {
chmax(Max, dfs(l, i) + now);
chmax(Max, dfs(i + 1, r) + oth);
} else {
chmax(Max, dfs(i + 1, r) + oth);
}
}
return f[l][r] = Max;
}

class Solution {
public:
int stoneGameV(vector<int> &stoneValue) {
int n = SZ(stoneValue);
for (int i = 0; i < n; ++i) {
a[i + 1] = stoneValue[i];
sum[i + 1] = sum[i] + a[i + 1];
}
memset(f, -1, sizeof f);
return dfs(1, n);
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````