# weekly-contest-298

## A

### Statement

``````输入：s = "lEeTcOdE"

``````输入：s = "arRAzFif"

``````

``````输入：s = "AbCdEfGhIjK"

``````

• `1 <= s.length <= 1000`
• `s` 由小写和大写英文字母组成

Given a string of English letters `s`, return the greatest English letter which occurs as both a lowercase and uppercase letter in `s`. The returned letter should be in uppercase. If no such letter exists, return an empty string.

An English letter `b` is greater than another letter `a` if `b` appears after `a` in the English alphabet.

Example 1:

``````Input: s = "lEeTcOdE"
Output: "E"
Explanation:
The letter 'E' is the only letter to appear in both lower and upper case.
``````

Example 2:

``````Input: s = "arRAzFif"
Output: "R"
Explanation:
The letter 'R' is the greatest letter to appear in both lower and upper case.
Note that 'A' and 'F' also appear in both lower and upper case, but 'R' is greater than 'F' or 'A'.
``````

Example 3:

``````Input: s = "AbCdEfGhIjK"
Output: ""
Explanation:
There is no letter that appears in both lower and upper case.
``````

Constraints:

• `1 <= s.length <= 1000`
• `s` consists of lowercase and uppercase English letters.

### Solution

``````#include <bits/stdc++.h>
#include <cctype>
#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

class Solution {
public:
string greatestLetter(string s) {
auto f = vector<int>(30, 0);
for (auto &c : s) {
if (islower(c)) {
f[c - 'a'] |= 2;
} else if (isupper(c)) {
f[c - 'A'] |= 4;
}
}

for (int i = 26; i >= 0; i--) {
if (f[i] == 6) {
return string(1, 'A' + i);
}
}

return "";
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

• 每个整数个位数字都是 `k`
• 所有整数之和是 `num`

• 多重集与集合类似，但多重集可以包含多个同一整数，空多重集的和为 `0`
• 个位数字 是数字最右边的数位。

``````输入：num = 58, k = 9

``````

``````输入：num = 37, k = 2

``````输入：num = 0, k = 7

``````

• `0 <= num <= 3000`
• `0 <= k <= 9`

Given two integers `num` and `k`, consider a set of positive integers with the following properties:

• The units digit of each integer is `k`.
• The sum of the integers is `num`.

Return the minimum possible size of such a set, or `-1` if no such set exists.

Note:

• The set can contain multiple instances of the same integer, and the sum of an empty set is considered `0`.
• The units digit of a number is the rightmost digit of the number.

Example 1:

``````Input: num = 58, k = 9
Output: 2
Explanation:
One valid set is [9,49], as the sum is 58 and each integer has a units digit of 9.
Another valid set is [19,39].
It can be shown that 2 is the minimum possible size of a valid set.
``````

Example 2:

``````Input: num = 37, k = 2
Output: -1
Explanation: It is not possible to obtain a sum of 37 using only integers that have a units digit of 2.
``````

Example 3:

``````Input: num = 0, k = 7
Output: 0
Explanation: The sum of an empty set is considered 0.
``````

Constraints:

• `0 <= num <= 3000`
• `0 <= k <= 9`

### 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 minimumNumbers(int num, int k) {
if (num == 0) {
return 0;
}

if (num < k) {
return -1;
}

int sum = 0;
for (int i = 1; i <= 10; i++) {
sum += k;
if (num % 10 == sum % 10 && sum <= num) {
return i;
}
}

return -1;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

• 子序列可以有 前导 0 。
• 空字符串视为 `0` 。
• 子序列 是指从一个字符串中删除零个或者多个字符后，不改变顺序得到的剩余字符序列。

``````输入：s = "1001010", k = 5

``````

``````输入：s = "00101001", k = 1

``````

• `1 <= s.length <= 1000`
• `s[i]` 要么是 `'0'` ，要么是 `'1'`
• `1 <= k <= 109`

You are given a binary string `s` and a positive integer `k`.

Return the length of the longest subsequence of `s` that makes up a binary number less than or equal to `k`.

Note:

• The subsequence can contain leading zeroes.
• The empty string is considered to be equal to `0`.
• A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

Example 1:

``````Input: s = "1001010", k = 5
Output: 5
Explanation: The longest subsequence of s that makes up a binary number less than or equal to 5 is "00010", as this number is equal to 2 in decimal.
Note that "00100" and "00101" are also possible, which are equal to 4 and 5 in decimal, respectively.
The length of this subsequence is 5, so 5 is returned.
``````

Example 2:

``````Input: s = "00101001", k = 1
Output: 6
Explanation: "000001" is the longest subsequence of s that makes up a binary number less than or equal to 1, as this number is equal to 1 in decimal.
The length of this subsequence is 6, so 6 is returned.
``````

Constraints:

• `1 <= s.length <= 1000`
• `s[i]` is either `'0'` or `'1'`.
• `1 <= k <= 109`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <numeric>
#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

class Solution {
public:
int longestSubsequence(string s, int k) {
int len = int(s.size());
auto f = vector<int>(len + 1, 0);

for (int i = 0; i < len; i++) {
if (s[i] == '0') {
f[i] = 1;
}
}

ll sum = 0, base = 1;
for (int i = len - 1; i >= 0 && base <= k; i--) {
if (s[i] == '1') {
if (sum + base <= k) {
sum += base;
f[i] = 1;
} else {
break;
}
}

base <<= 1;
}

return accumulate(f.begin(), f.end(), 0);
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

• Difficulty: Hard
• Tag: `回溯`

• 沿垂直方向按高度 完全 切割木块，或
• 沿水平方向按宽度 完全 切割木块 ``````输入：m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]]

- 2 块 2 x 2 的小木块，售出 2 * 7 = 14 元。
- 1 块 2 x 1 的小木块，售出 1 * 3 = 3 元。
- 1 块 1 x 4 的小木块，售出 1 * 2 = 2 元。

19 元是最多能得到的钱数。
`````` ``````输入：m = 4, n = 6, prices = [[3,2,10],[1,4,2],[4,1,3]]

- 3 块 3 x 2 的小木块，售出 3 * 10 = 30 元。
- 1 块 1 x 4 的小木块，售出 1 * 2 = 2 元。

32 元是最多能得到的钱数。

• `1 <= m, n <= 200`
• `1 <= prices.length <= 2 * 104`
• `prices[i].length == 3`
• `1 <= hi <= m`
• `1 <= wi <= n`
• `1 <= pricei <= 106`
• 所有 `(hi, wi)` 互不相同 。

You are given two integers `m` and `n` that represent the height and width of a rectangular piece of wood. You are also given a 2D integer array `prices`, where `prices[i] = [hi, wi, pricei]` indicates you can sell a rectangular piece of wood of height `hi` and width `wi` for `pricei` dollars.

To cut a piece of wood, you must make a vertical or horizontal cut across the entire height or width of the piece to split it into two smaller pieces. After cutting a piece of wood into some number of smaller pieces, you can sell pieces according to `prices`. You may sell multiple pieces of the same shape, and you do not have to sell all the shapes. The grain of the wood makes a difference, so you cannot rotate a piece to swap its height and width.

Return the maximum money you can earn after cutting an `m x n` piece of wood.

Note that you can cut the piece of wood as many times as you want.

Example 1: ``````Input: m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]]
Output: 19
Explanation: The diagram above shows a possible scenario. It consists of:
- 2 pieces of wood shaped 2 x 2, selling for a price of 2 * 7 = 14.
- 1 piece of wood shaped 2 x 1, selling for a price of 1 * 3 = 3.
- 1 piece of wood shaped 1 x 4, selling for a price of 1 * 2 = 2.
This obtains a total of 14 + 3 + 2 = 19 money earned.
It can be shown that 19 is the maximum amount of money that can be earned.
``````

Example 2: ``````Input: m = 4, n = 6, prices = [[3,2,10],[1,4,2],[4,1,3]]
Output: 32
Explanation: The diagram above shows a possible scenario. It consists of:
- 3 pieces of wood shaped 3 x 2, selling for a price of 3 * 10 = 30.
- 1 piece of wood shaped 1 x 4, selling for a price of 1 * 2 = 2.
This obtains a total of 30 + 2 = 32 money earned.
It can be shown that 32 is the maximum amount of money that can be earned.
Notice that we cannot rotate the 1 x 4 piece of wood to obtain a 4 x 1 piece of wood.``````

Constraints:

• `1 <= m, n <= 200`
• `1 <= prices.length <= 2 * 104`
• `prices[i].length == 3`
• `1 <= hi <= m`
• `1 <= wi <= n`
• `1 <= pricei <= 106`
• All the shapes of wood `(hi, wi)` are pairwise distinct.

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

class Solution {
public:
long long sellingWood(int m, int n, vector<vector<int>> &prices) {
auto f = vector<vector<ll>>(m + 1, vector<ll>(n + 1, 0));
for (auto &p : prices) {
f[p][p] = p;
}

while (true) {
bool change = false;

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k < j; k++) {
if (f[i][j - k] + f[i][k] > f[i][j]) {
change = true;
f[i][j] = f[i][j - k] + f[i][k];
}
}
}
}

for (int j = 1; j <= n; j++) {
for (int i = 1; i <= m; i++) {
for (int k = 1; k < i; k++) {
if (f[i - k][j] + f[k][j] > f[i][j]) {
change = true;
f[i][j] = f[i - k][j] + f[k][j];
}
}
}
}

if (!change) {
break;
}
}

return f[m][n];
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````