# biweekly-contest-83

## A

### Statement

1. `"Flush"`：同花，五张相同花色的扑克牌。
2. `"Three of a Kind"`：三条，有 3 张大小相同的扑克牌。
3. `"Pair"`：对子，两张大小一样的扑克牌。
4. `"High Card"`：高牌，五张大小互不相同的扑克牌。

``````输入：ranks = [13,2,3,1,9], suits = ["a","a","a","a","a"]

``````

``````输入：ranks = [4,4,2,4,4], suits = ["d","a","a","b","c"]

``````输入：ranks = [10,10,2,12,9], suits = ["a","b","c","a","d"]

``````

• `ranks.length == suits.length == 5`
• `1 <= ranks[i] <= 13`
• `'a' <= suits[i] <= 'd'`
• 任意两张扑克牌不会同时有相同的大小和花色。

You are given an integer array `ranks` and a character array `suits`. You have `5` cards where the `ith` card has a rank of `ranks[i]` and a suit of `suits[i]`.

The following are the types of poker hands you can make from best to worst:

1. `"Flush"`: Five cards of the same suit.
2. `"Three of a Kind"`: Three cards of the same rank.
3. `"Pair"`: Two cards of the same rank.
4. `"High Card"`: Any single card.

Return a string representing the best type of poker hand you can make with the given cards.

Note that the return values are case-sensitive.

Example 1:

``````Input: ranks = [13,2,3,1,9], suits = ["a","a","a","a","a"]
Output: "Flush"
Explanation: The hand with all the cards consists of 5 cards with the same suit, so we have a "Flush".
``````

Example 2:

``````Input: ranks = [4,4,2,4,4], suits = ["d","a","a","b","c"]
Output: "Three of a Kind"
Explanation: The hand with the first, second, and fourth card consists of 3 cards with the same rank, so we have a "Three of a Kind".
Note that we could also make a "Pair" hand but "Three of a Kind" is a better hand.
Also note that other cards could be used to make the "Three of a Kind" hand.``````

Example 3:

``````Input: ranks = [10,10,2,12,9], suits = ["a","b","c","a","d"]
Output: "Pair"
Explanation: The hand with the first and second card consists of 2 cards with the same rank, so we have a "Pair".
Note that we cannot make a "Flush" or a "Three of a Kind".
``````

Constraints:

• `ranks.length == suits.length == 5`
• `1 <= ranks[i] <= 13`
• `'a' <= suits[i] <= 'd'`
• No two cards have the same rank and suit.

### 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:
string bestHand(vector<int> &ranks, vector<char> &suits) {
{
bool Flush = true;

for (int i = 1; i < 5; i++) {
if (suits[i] != suits[0]) {
Flush = false;
break;
}
}

if (Flush) {
return "Flush";
}
}

sort(all(ranks));

for (int i = 2; i < 5; i++) {
if (ranks[i] == ranks[i - 1] && ranks[i] == ranks[i - 2]) {
return "Three of a Kind";
}
}

for (int i = 1; i < 5; i++) {
if (ranks[i] == ranks[i - 1]) {
return "Pair";
}
}

return "High Card";
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

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

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

``````

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

``````

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

Given an integer array `nums`, return the number of subarrays filled with `0`.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

``````Input: nums = [1,3,0,0,2,0,0,4]
Output: 6
Explanation:
There are 4 occurrences of [0] as a subarray.
There are 2 occurrences of [0,0] as a subarray.
There is no occurrence of a subarray with a size more than 2 filled with 0. Therefore, we return 6.``````

Example 2:

``````Input: nums = [0,0,0,2,0,0]
Output: 9
Explanation:
There are 5 occurrences of [0] as a subarray.
There are 3 occurrences of [0,0] as a subarray.
There is 1 occurrence of [0,0,0] as a subarray.
There is no occurrence of a subarray with a size more than 3 filled with 0. Therefore, we return 9.
``````

Example 3:

``````Input: nums = [2,10,2019]
Output: 0
Explanation: There is no subarray filled with 0. Therefore, we return 0.
``````

Constraints:

• `1 <= nums.length <= 105`
• `-109 <= nums[i] <= 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:
long long zeroFilledSubarray(vector<int> &nums) {
int n = int(nums.size());
auto f = vector<ll>(nums.size() + 5, 0);
for (int i = 1; i <= n; i++) {
int x = nums[i - 1];
if (x != 0) {
f[i] = 0;
} else {
f[i] = f[i - 1] + 1;
}
}

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

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

• 在系统中给定下标处 插入 或者 替换 一个数字。
• 返回 系统中给定数字的最小下标。

• `NumberContainers()` 初始化数字容器系统。
• `void change(int index, int number)` 在下标 `index` 处填入 `number` 。如果该下标 `index` 处已经有数字了，那么用 `number` 替换该数字。
• `int find(int number)` 返回给定数字 `number` 在系统中的最小下标。如果系统中没有 `number` ，那么返回 `-1` 。

``````输入：
["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"]
[[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]]

[null, -1, null, null, null, null, 1, null, 2]

NumberContainers nc = new NumberContainers();
nc.find(10); // 没有数字 10 ，所以返回 -1 。
nc.change(2, 10); // 容器中下标为 2 处填入数字 10 。
nc.change(1, 10); // 容器中下标为 1 处填入数字 10 。
nc.change(3, 10); // 容器中下标为 3 处填入数字 10 。
nc.change(5, 10); // 容器中下标为 5 处填入数字 10 。
nc.find(10); // 数字 10 所在的下标为 1 ，2 ，3 和 5 。因为最小下标为 1 ，所以返回 1 。
nc.change(1, 20); // 容器中下标为 1 处填入数字 20 。注意，下标 1 处之前为 10 ，现在被替换为 20 。
nc.find(10); // 数字 10 所在下标为 2 ，3 和 5 。最小下标为 2 ，所以返回 2 。
``````

• `1 <= index, number <= 109`
• 调用 `change` 和 `find` 的 总次数 不超过 `105` 次。

Design a number container system that can do the following:

• Insert or Replace a number at the given index in the system.
• Return the smallest index for the given number in the system.

Implement the `NumberContainers` class:

• `NumberContainers()` Initializes the number container system.
• `void change(int index, int number)` Fills the container at `index` with the `number`. If there is already a number at that `index`, replace it.
• `int find(int number)` Returns the smallest index for the given `number`, or `-1` if there is no index that is filled by `number` in the system.

Example 1:

``````Input
["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"]
[[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]]
Output
[null, -1, null, null, null, null, 1, null, 2]
Explanation
NumberContainers nc = new NumberContainers();
nc.find(10); // There is no index that is filled with number 10. Therefore, we return -1.
nc.change(2, 10); // Your container at index 2 will be filled with number 10.
nc.change(1, 10); // Your container at index 1 will be filled with number 10.
nc.change(3, 10); // Your container at index 3 will be filled with number 10.
nc.change(5, 10); // Your container at index 5 will be filled with number 10.
nc.find(10); // Number 10 is at the indices 1, 2, 3, and 5. Since the smallest index that is filled with 10 is 1, we return 1.
nc.change(1, 20); // Your container at index 1 will be filled with number 20. Note that index 1 was filled with 10 and then replaced with 20.
nc.find(10); // Number 10 is at the indices 2, 3, and 5. The smallest index that is filled with 10 is 2. Therefore, we return 2.
``````

Constraints:

• `1 <= index, number <= 109`
• At most `105` calls will be made in total to `change` and `find`.

### 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 NumberContainers {
public:
NumberContainers() {
num_map.clear();
ix_map.clear();
}

void change(int index, int number) {
if (num_map.count(index) != 0) {
ix_map[num_map[index]].erase(index);
}

num_map[index] = number;
ix_map[number].insert(index);
}

int find(int number) {
if (ix_map.count(number) == 0 || ix_map[number].empty()) {
return -1;
}

auto it = ix_map[number].begin();
return *it;
}

map<int, int> num_map;
map<int, set<int>> ix_map;
};

/**
* Your NumberContainers object will be instantiated and called as such:
* NumberContainers* obj = new NumberContainers();
* obj->change(index,number);
* int param_2 = obj->find(number);
*/

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

``````输入：rolls = [4,2,1,2,3,3,2,4,1], k = 4

``````输入：rolls = [1,1,2,2], k = 2

``````

``````输入：rolls = [1,1,3,2,2,2,3,3], k = 4

``````

• `n == rolls.length`
• `1 <= n <= 105`
• `1 <= rolls[i] <= k <= 105`

You are given an integer array `rolls` of length `n` and an integer `k`. You roll a `k` sided dice numbered from `1` to `k`, `n` times, where the result of the `ith` roll is `rolls[i]`.

Return the length of the shortest sequence of rolls that cannot be taken from `rolls`.

A sequence of rolls of length `len` is the result of rolling a `k` sided dice `len` times.

Note that the sequence taken does not have to be consecutive as long as it is in order.

Example 1:

``````Input: rolls = [4,2,1,2,3,3,2,4,1], k = 4
Output: 3
Explanation: Every sequence of rolls of length 1, [1], [2], [3], [4], can be taken from rolls.
Every sequence of rolls of length 2, [1, 1], [1, 2], …, [4, 4], can be taken from rolls.
The sequence [1, 4, 2] cannot be taken from rolls, so we return 3.
Note that there are other sequences that cannot be taken from rolls.``````

Example 2:

``````Input: rolls = [1,1,2,2], k = 2
Output: 2
Explanation: Every sequence of rolls of length 1, [1], [2], can be taken from rolls.
The sequence [2, 1] cannot be taken from rolls, so we return 2.
Note that there are other sequences that cannot be taken from rolls but [2, 1] is the shortest.
``````

Example 3:

``````Input: rolls = [1,1,3,2,2,2,3,3], k = 4
Output: 1
Explanation: The sequence [4] cannot be taken from rolls, so we return 1.
Note that there are other sequences that cannot be taken from rolls but [4] is the shortest.
``````

Constraints:

• `n == rolls.length`
• `1 <= n <= 105`
• `1 <= rolls[i] <= k <= 105`

### 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:
int shortestSequence(vector<int> &rolls, int k) {
int res = 0;
auto f = vector<int>(k + 1, 0);
int cnt = 0;
for (const auto &r : rolls) {
if (f[r] == 0) {
++cnt;
f[r] = 1;
if (cnt == k) {
++res;
cnt = 0;
auto g = vector<int>(k + 1, 0);
f.swap(g);
}
}
}

return res + 1;
}
};

#ifdef LOCAL

int main() {
auto s = Solution();

{
auto r = vector<int>({4, 2, 1, 2, 3, 3, 2, 4, 1});
dbg(s.shortestSequence(r, 4));
}

{
auto r = vector<int>({1, 1, 2, 2});
dbg(s.shortestSequence(r, 2));
}

{
auto r = vector<int>({1, 1, 3, 2, 2, 2, 3, 3});
dbg(s.shortestSequence(r, 4));
}

{
auto r = vector<int>({1, 1});
dbg(s.shortestSequence(r, 2));
}

return 0;
}

#endif
``````