weekly-contest-288

A

Statement

``````输入：num = 1234

``````

``````输入：num = 65875

``````

• `1 <= num <= 109`

You are given a positive integer `num`. You may swap any two digits of `num` that have the same parity (i.e. both odd digits or both even digits).

Return the largest possible value of `num` after any number of swaps.

Example 1:

``````Input: num = 1234
Output: 3412
Explanation: Swap the digit 3 with the digit 1, this results in the number 3214.
Swap the digit 2 with the digit 4, this results in the number 3412.
Note that there may be other sequences of swaps but it can be shown that 3412 is the largest possible number.
Also note that we may not swap the digit 4 with the digit 1 since they are of different parities.
``````

Example 2:

``````Input: num = 65875
Output: 87655
Explanation: Swap the digit 8 with the digit 6, this results in the number 85675.
Swap the first digit 5 with the digit 7, this results in the number 87655.
Note that there may be other sequences of swaps but it can be shown that 87655 is the largest possible number.
``````

Constraints:

• `1 <= num <= 109`

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>;
const ll mod = 1e9 + 7;

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 largestInteger(int num) {
vector<vector<int>> f(2, vector<int>());
auto g = vector<int>();

int x = num;
while (x) {
int y = x % 10;
f[y % 2].push_back(y);
x /= 10;
g.push_back(y % 2);
}

sort(all(f[0]));
sort(all(f[1]));

reverse(all(f[0]));
reverse(all(f[1]));

ll res = 0;
ll base = 1;
for (auto &_g : g) {
res += base * f[_g].back();
f[_g].pop_back();
base *= 10;
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

B

Statement

``````输入：expression = "247+38"

``````

``````输入：expression = "12+34"

``````

``````输入：expression = "999+999"

``````

• `3 <= expression.length <= 10`
• `expression` 仅由数字 `'1'``'9'``'+'` 组成
• `expression` 由数字开始和结束
• `expression` 恰好仅含有一个 `'+'`.
• `expression` 的原始值和添加满足要求的任一对括号之后 `expression` 的值，都符合 32-bit 带符号整数范围

You are given a 0-indexed string `expression` of the form `"<num1>+<num2>"` where `<num1>` and `<num2>` represent positive integers.

Add a pair of parentheses to `expression` such that after the addition of parentheses, `expression` is a valid mathematical expression and evaluates to the smallest possible value. The left parenthesis must be added to the left of `'+'` and the right parenthesis must be added to the right of `'+'`.

Return `expression` after adding a pair of parentheses such that `expression` evaluates to the smallest possible value. If there are multiple answers that yield the same result, return any of them.

The input has been generated such that the original value of `expression`, and the value of `expression` after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.

Example 1:

``````Input: expression = "247+38"
Output: "2(47+38)"
Explanation: The expression evaluates to 2 * (47 + 38) = 2 * 85 = 170.
Note that "2(4)7+38" is invalid because the right parenthesis must be to the right of the '+'.
It can be shown that 170 is the smallest possible value.
``````

Example 2:

``````Input: expression = "12+34"
Output: "1(2+3)4"
Explanation: The expression evaluates to 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20.
``````

Example 3:

``````Input: expression = "999+999"
Output: "(999+999)"
Explanation: The expression evaluates to 999 + 999 = 1998.
``````

Constraints:

• `3 <= expression.length <= 10`
• `expression` consists of digits from `'1'` to `'9'` and `'+'`.
• `expression` starts and ends with digits.
• `expression` contains exactly one `'+'`.
• The original value of `expression`, and the value of `expression` after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.

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>;
const ll mod = 1e9 + 7;

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:
string minimizeResult(string &e) {
auto f = vector<int>(2, 0);
int ix = 0;
for (int i = 0; i < e.length(); i++) {
if (e[i] == '+') {
++ix;
continue;
}

f[ix] = f[ix] * 10 + (e[i] - '0');
}

auto gen = [](int x) -> vector<int> {
auto res = vector<int>();

while (x) {
res.push_back(x % 10);
x /= 10;
}

reverse(all(res));

return res;
};

auto a = gen(f[0]);
auto b = gen(f[1]);

int m = 0x3f3f3f3f;
string res = "";

auto g = [&](int i, int j) -> tuple<int, string> {
auto _a = vector<int>(2, 0);
auto _b = vector<int>(2, 0);

string res = "";
for (int o = 0, ix = 0; o < a.size(); o++) {
if (o == i) {
++ix;
res += "(";
}

_a[ix] = _a[ix] * 10 + a[o];
res += char('0' + a[o]);
}

res += "+";

for (int o = 0, ix = 0; o < b.size(); o++) {
_b[ix] = _b[ix] * 10 + b[o];

res += char('0' + b[o]);

if (o == j) {
++ix;
res += ")";
}
}

if (_a[0] == 0) {
_a[0] = 1;
}

if (_b[1] == 0) {
_b[1] = 1;
}

return make_tuple(_a[0] * _b[1] * (_a[1] + _b[0]), res);
};

for (int i = 0; i < a.size(); i++) {
for (int j = 0; j < b.size(); j++) {
auto [_m, _res] = g(i, j);
if (_m < m) {
m = _m;
res = _res;
}
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

C

Statement

``````输入：nums = [0,4], k = 5

``````

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

``````

• `1 <= nums.length, k <= 105`
• `0 <= nums[i] <= 106`

You are given an array of non-negative integers `nums` and an integer `k`. In one operation, you may choose any element from `nums` and increment it by `1`.

Return the maximum product of `nums` after at most `k` operations. Since the answer may be very large, return it modulo `109 + 7`.

Example 1:

``````Input: nums = [0,4], k = 5
Output: 20
Explanation: Increment the first number 5 times.
Now nums = [5, 4], with a product of 5 * 4 = 20.
It can be shown that 20 is maximum product possible, so we return 20.
Note that there may be other ways to increment nums to have the maximum product.
``````

Example 2:

``````Input: nums = [6,3,3,2], k = 2
Output: 216
Explanation: Increment the second number 1 time and increment the fourth number 1 time.
Now nums = [6, 4, 3, 3], with a product of 6 * 4 * 3 * 3 = 216.
It can be shown that 216 is maximum product possible, so we return 216.
Note that there may be other ways to increment nums to have the maximum product.
``````

Constraints:

• `1 <= nums.length, k <= 105`
• `0 <= nums[i] <= 106`

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>;
const ll mod = 1e9 + 7;

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 maximumProduct(vector<int> &nums, int k) {
priority_queue<int, vector<int>, greater<int>> pq;
for (auto &a : nums) {
if (a == 0) {
if (k == 0) {
return 0;
}
--k;
++a;
}

pq.push(a);
}

while (k) {
int a = pq.top();
pq.pop();
++a;
--k;
pq.push(a);
}

ll res = 1;
while (!pq.empty()) {
int x = pq.top();
pq.pop();
res *= x;
res %= mod;
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

D

Statement

Alice 是 `n` 个花园的园丁，她想通过种花，最大化她所有花园的总美丽值。

• 完善 花园数目乘以 `full`.
• 剩余 不完善 花园里，花的 最少数目 乘以 `partial` 。如果没有不完善花园，那么这一部分的值为 `0` 。

``````输入：flowers = [1,3,1,1], newFlowers = 7, target = 6, full = 12, partial = 1

- 在第 0 个花园种 2 朵花
- 在第 1 个花园种 3 朵花
- 在第 2 个花园种 1 朵花
- 在第 3 个花园种 1 朵花

``````

``````输入：flowers = [2,4,5,3], newFlowers = 10, target = 5, full = 2, partial = 6

- 在第 0 个花园种 3 朵花
- 在第 1 个花园种 0 朵花
- 在第 2 个花园种 0 朵花
- 在第 3 个花园种 2 朵花

``````

• `1 <= flowers.length <= 105`
• `1 <= flowers[i], target <= 105`
• `1 <= newFlowers <= 1010`
• `1 <= full, partial <= 105`

Alice is a caretaker of `n` gardens and she wants to plant flowers to maximize the total beauty of all her gardens.

You are given a 0-indexed integer array `flowers` of size `n`, where `flowers[i]` is the number of flowers already planted in the `ith` garden. Flowers that are already planted cannot be removed. You are then given another integer `newFlowers`, which is the maximum number of flowers that Alice can additionally plant. You are also given the integers `target`, `full`, and `partial`.

A garden is considered complete if it has at least `target` flowers. The total beauty of the gardens is then determined as the sum of the following:

• The number of complete gardens multiplied by `full`.
• The minimum number of flowers in any of the incomplete gardens multiplied by `partial`. If there are no incomplete gardens, then this value will be `0`.

Return the maximum total beauty that Alice can obtain after planting at most `newFlowers` flowers.

Example 1:

``````Input: flowers = [1,3,1,1], newFlowers = 7, target = 6, full = 12, partial = 1
Output: 14
Explanation: Alice can plant
- 2 flowers in the 0th garden
- 3 flowers in the 1st garden
- 1 flower in the 2nd garden
- 1 flower in the 3rd garden
The gardens will then be [3,6,2,2]. She planted a total of 2 + 3 + 1 + 1 = 7 flowers.
There is 1 garden that is complete.
The minimum number of flowers in the incomplete gardens is 2.
Thus, the total beauty is 1 * 12 + 2 * 1 = 12 + 2 = 14.
No other way of planting flowers can obtain a total beauty higher than 14.
``````

Example 2:

``````Input: flowers = [2,4,5,3], newFlowers = 10, target = 5, full = 2, partial = 6
Output: 30
Explanation: Alice can plant
- 3 flowers in the 0th garden
- 0 flowers in the 1st garden
- 0 flowers in the 2nd garden
- 2 flowers in the 3rd garden
The gardens will then be [5,4,5,5]. She planted a total of 3 + 0 + 0 + 2 = 5 flowers.
There are 3 gardens that are complete.
The minimum number of flowers in the incomplete gardens is 4.
Thus, the total beauty is 3 * 2 + 4 * 6 = 6 + 24 = 30.
No other way of planting flowers can obtain a total beauty higher than 30.
Note that Alice could make all the gardens complete but in this case, she would obtain a lower total beauty.
``````

Constraints:

• `1 <= flowers.length <= 105`
• `1 <= flowers[i], target <= 105`
• `1 <= newFlowers <= 1010`
• `1 <= full, partial <= 105`

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>;
const ll mod = 1e9 + 7;

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 N = 1e5 + 5;

class Solution {
public:
long long maximumBeauty(vector<int> &fl, long long has, int target, int full, int partial) {
ll res = 0;

sort(all(fl));

while (!fl.empty()) {
if (fl.back() >= target) {
res += full;
fl.pop_back();
} else {
break;
}
}

int n = fl.size();

if (n == 0) {
return res;
}

int cnt = 0;
ll sum = 0;
ll res_p = 0;
ll target_need = 1ll * n * target - accumulate(all(fl), 0ll);

for (int i = 0, j = 0, k = 0; i < target; i++) {
while (j < n && fl[j] <= i) {
++cnt;
sum += fl[j];
++j;
}

ll remind = has - (1ll * i * cnt - sum);

while (k < n && (remind < target_need || k < cnt)) {
target_need -= target - fl[k];
k++;
}

remind -= target_need;

if (remind < 0) {
continue;
}

ll cur = 0;
cur += 1ll * partial * i * (cnt > 0);
cur += 1ll * full * (n - k);
cur += 1ll * full * max<ll>(0, min<ll>(cnt - 1, remind / (target - i)));

res_p = max(res_p, cur);
}

return res + res_p;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````