# weekly-contest-183

## A

### Statement

Metadata

``````输入：nums = [4,3,10,9,8]

``````

``````输入：nums = [4,4,7,6,7]

``````

``````输入：nums = [6]

``````

• `1 <= nums.length <= 500`
• `1 <= nums[i] <= 100`

Metadata

Given the array `nums`, obtain a subsequence of the array whose sum of elements is strictly greater than the sum of the non included elements in such subsequence.

If there are multiple solutions, return the subsequence with minimum size and if there still exist multiple solutions, return the subsequence with the maximum total sum of all its elements. A subsequence of an array can be obtained by erasing some (possibly zero) elements from the array.

Note that the solution with the given constraints is guaranteed to be unique. Also return the answer sorted in non-increasing order.

Example 1:

``````
Input: nums = [4,3,10,9,8]
Output: [10,9]
Explanation: The subsequences [10,9] and [10,8] are minimal such that the sum of their elements is strictly greater than the sum of elements not included, however, the subsequence [10,9] has the maximum total sum of its elements.
``````

Example 2:

``````
Input: nums = [4,4,7,6,7]
Output: [7,7,6]
Explanation: The subsequence [7,7] has the sum of its elements equal to 14 which is not strictly greater than the sum of elements not included (14 = 4 + 4 + 6). Therefore, the subsequence [7,6,7] is the minimal satisfying the conditions. Note the subsequence has to returned in non-decreasing order.
``````

Example 3:

``````
Input: nums = [6]
Output: [6]
``````

Constraints:

• `1 <= nums.length <= 500`
• `1 <= nums[i] <= 100`

## B

### Statement

Metadata

• 如果当前数字为偶数，则将其除以 2 。

• 如果当前数字为奇数，则将其加上 1 。

``````输入：s = "1101"

Step 1) 13 是奇数，加 1 得到 14
Step 2) 14 是偶数，除 2 得到 7
Step 3) 7  是奇数，加 1 得到 8
Step 4) 8  是偶数，除 2 得到 4
Step 5) 4  是偶数，除 2 得到 2
Step 6) 2  是偶数，除 2 得到 1
``````

``````输入：s = "10"

Step 1) 2 是偶数，除 2 得到 1
``````

``````输入：s = "1"

``````

• `1 <= s.length <= 500`
• `s` 由字符 `'0'``'1'` 组成。
• `s[0] == '1'`

Metadata

Given the binary representation of an integer as a string `s`, return the number of steps to reduce it to `1` under the following rules:

• If the current number is even, you have to divide it by `2`.

• If the current number is odd, you have to add `1` to it.

It is guaranteed that you can always reach one for all test cases.

Example 1:

``````Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14.
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.
Step 5) 4 is even, divide by 2 and obtain 2.
Step 6) 2 is even, divide by 2 and obtain 1.
``````

Example 2:

``````Input: s = "10"
Output: 1
Explanation: "10" corressponds to number 2 in their decimal representation.
Step 1) 2 is even, divide by 2 and obtain 1.
``````

Example 3:

``````Input: s = "1"
Output: 0
``````

Constraints:

• `1 <= s.length <= 500`
• `s` consists of characters '0' or '1'
• `s[0] == '1'`

## C

### Statement

Metadata
• Link: 最长快乐字符串
• Difficulty: Medium
• Tag: `贪心` `字符串` `堆（优先队列）`

• `s` 是一个尽可能长的快乐字符串。
• `s`最多`a` 个字母 `'a'``b` 个字母 `'b'``c` 个字母 `'c'`
• `s `中只含有 `'a'``'b'``'c'` 三种字母。

``````输入：a = 1, b = 1, c = 7

``````

``````输入：a = 2, b = 2, c = 1

``````

``````输入：a = 7, b = 1, c = 0

• `0 <= a, b, c <= 100`
• `a + b + c > 0`

Metadata
• Link: Longest Happy String
• Difficulty: Medium
• Tag: `Greedy` `String` `Heap (Priority Queue)`

A string `s` is called happy if it satisfies the following conditions:

• `s` only contains the letters `'a'`, `'b'`, and `'c'`.
• `s` does not contain any of `"aaa"`, `"bbb"`, or `"ccc"` as a substring.
• `s` contains at most `a` occurrences of the letter `'a'`.
• `s` contains at most `b` occurrences of the letter `'b'`.
• `s` contains at most `c` occurrences of the letter `'c'`.

Given three integers `a`, `b`, and `c`, return the longest possible happy string. If there are multiple longest happy strings, return any of them. If there is no such string, return the empty string `""`.

A substring is a contiguous sequence of characters within a string.

Example 1:

``````Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.
``````

Example 2:

``````Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: It is the only correct answer in this case.
``````

Constraints:

• `0 <= a, b, c <= 100`
• `a + b + c > 0`

### Solution

``````#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define SZ(x) int((x).size())
#define endl "\n"
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;
}
// head

class Solution {
public:
bool gao(string &res, int &a, int &b, int &c, char _a, char _b, char _c) {
//	pt(res, res[-2], res[-3], _a);
if (SZ(res) > 1 && *(res.end() - 1) == _a && *(res.end() - 2) == _a) {
if (b + c == 0)
return false;
if (b > c) {
res += _b;
--b;
} else {
res += _c;
--c;
}
} else {
res += _a;
--a;
}
return true;
}
string longestDiverseString(int a, int b, int c) {
string res = "";
while (a + b + c > 0) {
int t = max({a, b, c});
if (a == t) {
if (!gao(res, a, b, c, 'a', 'b', 'c'))
break;
} else if (b == t) {
if (!gao(res, b, a, c, 'b', 'a', 'c'))
break;
} else {
if (!gao(res, c, a, b, 'c', 'a', 'b'))
break;
}
}
return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

Metadata
• Link: 石子游戏 III
• Difficulty: Hard
• Tag: `数组` `数学` `动态规划` `博弈`

Alice 和 Bob 用几堆石子在做游戏。几堆石子排成一行，每堆石子都对应一个得分，由数组 `stoneValue` 给出。

Alice 和 Bob 轮流取石子，Alice 总是先开始。在每个玩家的回合中，该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。

``````输入：values = [1,2,3,7]

``````

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

``````输入：values = [1,2,3,6]

``````

``````输入：values = [1,2,3,-1,-2,-3,7]

``````

``````输入：values = [-1,-2,-3]

``````

• `1 <= values.length <= 50000`
• `-1000 <= values[i] <= 1000`

Metadata
• Link: Stone Game III
• Difficulty: Hard
• Tag: `Array` `Math` `Dynamic Programming` `Game Theory`

Alice and Bob continue their games with piles of stones. There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array `stoneValue`.

Alice and Bob take turns, with Alice starting first. On each player's turn, that player can take `1`, `2`, or `3` stones from the first remaining stones in the row.

The score of each player is the sum of the values of the stones taken. The score of each player is `0` initially.

The objective of the game is to end with the highest score, and the winner is the player with the highest score and there could be a tie. The game continues until all the stones have been taken.

Assume Alice and Bob play optimally.

Return `"Alice"` if Alice will win, `"Bob"` if Bob will win, or `"Tie"` if they will end the game with the same score.

Example 1:

``````Input: values = [1,2,3,7]
Output: "Bob"
Explanation: Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.
``````

Example 2:

``````Input: values = [1,2,3,-9]
Output: "Alice"
Explanation: Alice must choose all the three piles at the first move to win and leave Bob with negative score.
If Alice chooses one pile her score will be 1 and the next move Bob's score becomes 5. In the next move, Alice will take the pile with value = -9 and lose.
If Alice chooses two piles her score will be 3 and the next move Bob's score becomes 3. In the next move, Alice will take the pile with value = -9 and also lose.
Remember that both play optimally so here Alice will choose the scenario that makes her win.
``````

Example 3:

``````Input: values = [1,2,3,6]
Output: "Tie"
Explanation: Alice cannot win this game. She can end the game in a draw if she decided to choose all the first three piles, otherwise she will lose.
``````

Constraints:

• `1 <= stoneValue.length <= 5 * 104`
• `-1000 <= stoneValue[i] <= 1000`

### Solution

``````#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define SZ(x) int((x).size())
#define endl "\n"
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;
}
// head

const int INF = 0x3f3f3f3f, N = 1e6 + 10;
int n;
vector<int> vec;

int f[N];

int dfs(int cur) {
if (cur >= n)
return 0;
if (f[cur] != -INF)
return f[cur];
int tot = 0, Max = -INF;
for (int i = 0; i < 3 && cur + i < n; ++i) {
tot += vec[cur + i];
chmax(Max, tot - dfs(cur + i + 1));
}
//	dbg(cur, Max);
return f[cur] = Max;
}

class Solution {
public:
string stoneGameIII(vector<int> &stoneValue) {
vec = stoneValue;
n = SZ(vec);
for (int i = 0; i <= n + 5; ++i) f[i] = -INF;
int t = dfs(0);
if (t > 0)
return "Alice";
else if (t < 0)
return "Bob";
else
return "Tie";
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````