# weekly-contest-317

## A

### Statement

``````输入：nums = [1,3,6,10,12,15]

``````

``````输入：nums = [1,2,4,7,10]

``````

• `1 <= nums.length <= 1000`
• `1 <= nums[i] <= 1000`

Given an integer array `nums` of positive integers, return the average value of all even integers that are divisible by `3`.

Note that the average of `n` elements is the sum of the `n` elements divided by `n` and rounded down to the nearest integer.

Example 1:

``````Input: nums = [1,3,6,10,12,15]
Output: 9
Explanation: 6 and 12 are even numbers that are divisible by 3. (6 + 12) / 2 = 9.
``````

Example 2:

``````Input: nums = [1,2,4,7,10]
Output: 0
Explanation: There is no single number that satisfies the requirement, so return 0.
``````

Constraints:

• `1 <= nums.length <= 1000`
• `1 <= nums[i] <= 1000`

### 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 averageValue(vector<int> &nums) {
int sum = 0;
int num = 0;

for (const auto &a : nums) {
if (a % 3 == 0 && a % 2 == 0) {
sum += a;
num++;
}
}

if (num == 0) {
return 0;
}

return sum / num;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

• 如果存在多个创作者流行度都最高，则需要找出所有符合条件的创作者。
• 如果某个创作者存在多个播放量最高的视频，则只需要找出字典序最小的 `id`

``````输入：creators = ["alice","bob","alice","chris"], ids = ["one","two","three","four"], views = [5,10,5,4]

alice 的流行度是 5 + 5 = 10 。
bob 的流行度是 10 。
chris 的流行度是 4 。
alice 和 bob 是流行度最高的创作者。
bob 播放量最高的视频 id 为 "two" 。
alice 播放量最高的视频 id 是 "one" 和 "three" 。由于 "one" 的字典序比 "three" 更小，所以结果中返回的 id 是 "one" 。
``````

``````输入：creators = ["alice","alice","alice"], ids = ["a","b","c"], views = [1,2,2]

id 为 "b" 和 "c" 的视频都满足播放量最高的条件。

``````

• `n == creators.length == ids.length == views.length`
• `1 <= n <= 105`
• `1 <= creators[i].length, ids[i].length <= 5`
• `creators[i]``ids[i]` 仅由小写英文字母组成
• `0 <= views[i] <= 105`

You are given two string arrays `creators` and `ids`, and an integer array `views`, all of length `n`. The `ith` video on a platform was created by `creator[i]`, has an id of `ids[i]`, and has `views[i]` views.

The popularity of a creator is the sum of the number of views on all of the creator's videos. Find the creator with the highest popularity and the id of their most viewed video.

• If multiple creators have the highest popularity, find all of them.
• If multiple videos have the highest view count for a creator, find the lexicographically smallest id.

Return a 2D array of strings `answer` where `answer[i] = [creatori, idi]` means that `creatori` has the highest popularity and `idi` is the id of their most popular video. The answer can be returned in any order.

Example 1:

``````Input: creators = ["alice","bob","alice","chris"], ids = ["one","two","three","four"], views = [5,10,5,4]
Output: [["alice","one"],["bob","two"]]
Explanation:
The popularity of alice is 5 + 5 = 10.
The popularity of bob is 10.
The popularity of chris is 4.
alice and bob are the most popular creators.
For bob, the video with the highest view count is "two".
For alice, the videos with the highest view count are "one" and "three". Since "one" is lexicographically smaller than "three", it is included in the answer.
``````

Example 2:

``````Input: creators = ["alice","alice","alice"], ids = ["a","b","c"], views = [1,2,2]
Output: [["alice","b"]]
Explanation:
The videos with id "b" and "c" have the highest view count.
Since "b" is lexicographically smaller than "c", it is included in the answer.
``````

Constraints:

• `n == creators.length == ids.length == views.length`
• `1 <= n <= 105`
• `1 <= creators[i].length, ids[i].length <= 5`
• `creators[i]` and `ids[i]` consist only of lowercase English letters.
• `0 <= views[i] <= 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>;

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

struct node {
ll sum = 0;
int max_view = -1;
string id = "";
};

class Solution {
public:
vector<vector<string>> mostPopularCreator(vector<string> &creators, vector<string> &ids, vector<int> &views) {
int n = int(creators.size());

auto mp = map<string, node>();
ll mx_views = 0;

for (int i = 0; i < n; i++) {
const auto &c = creators[i];
const auto &id = ids[i];
int view = views[i];

mp[c].sum += view;
if (view > mp[c].max_view || (view == mp[c].max_view && id < mp[c].id)) {
mp[c].max_view = view;
mp[c].id = id;
}

mx_views = max(mx_views, mp[c].sum);
}

auto res = vector<vector<string>>();
for (const auto &[k, v] : mp) {
if (v.sum == mx_views) {
res.push_back(vector<string>({k, v.id}));
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

``````输入：n = 16, target = 6

``````

``````输入：n = 467, target = 6

``````输入：n = 1, target = 1

``````

• `1 <= n <= 1012`
• `1 <= target <= 150`
• 生成的输入保证总可以使 `n` 变成一个美丽整数。

You are given two positive integers `n` and `target`.

An integer is considered beautiful if the sum of its digits is less than or equal to `target`.

Return the minimum non-negative integer `x` such that `n + x` is beautiful. The input will be generated such that it is always possible to make `n` beautiful.

Example 1:

``````Input: n = 16, target = 6
Output: 4
Explanation: Initially n is 16 and its digit sum is 1 + 6 = 7. After adding 4, n becomes 20 and digit sum becomes 2 + 0 = 2. It can be shown that we can not make n beautiful with adding non-negative integer less than 4.
``````

Example 2:

``````Input: n = 467, target = 6
Output: 33
Explanation: Initially n is 467 and its digit sum is 4 + 6 + 7 = 17. After adding 33, n becomes 500 and digit sum becomes 5 + 0 + 0 = 5. It can be shown that we can not make n beautiful with adding non-negative integer less than 33.
``````

Example 3:

``````Input: n = 1, target = 1
Output: 0
Explanation: Initially n is 1 and its digit sum is 1, which is already smaller than or equal to target.
``````

Constraints:

• `1 <= n <= 1012`
• `1 <= target <= 150`
• The input will be generated such that it is always possible to make `n` beautiful.

### 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 getTarget(ll n) {
int res = 0;

while (n) {
res += n % 10;
n /= 10;
}

return res;
}

long long makeIntegerBeautiful(long long n, int target) {
auto vec = vector<int>();

ll _n = n;
while (_n) {
vec.push_back(_n % 10);
_n /= 10;
}

vec.push_back(0);

int sze = int(vec.size());

// for (int i = 0; i < sze; i++) {
//     cout << i << " " << vec[i] << endl;
// }

for (int i = 0; i < sze - 1; i++) {
int sum = accumulate(all(vec), 0);
if (sum <= target) {
break;
}

vec[i] = 0;
++vec[i + 1];

for (int j = i + 1; j < sze - 1; j++) {
if (vec[j] < 10) {
break;
}
vec[j] = 0;
++vec[j + 1];
}
}

// while (!vec.empty() && vec.back() == 0) {
//     vec.pop_back();
// }

reverse(all(vec));

ll m = 0;
for (const auto &a : vec) {
m = m * 10 + a;
}

return m - n;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

• 从树中 移除`queries[i]` 的值作为根节点的子树。题目所用测试用例保证 `queries[i]` 等于根节点的值。

• 查询之间是独立的，所以在每个查询执行后，树会回到其 初始 状态。
• 树的高度是从根到树中某个节点的 最长简单路径中的边数

``````输入：root = [1,3,4,2,null,6,5,null,null,null,null,null,7], queries = [4]

``````

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

- 移除以 3 为根节点的子树。树的高度变为 3（路径为 5 -> 8 -> 2 -> 4）。
- 移除以 2 为根节点的子树。树的高度变为 2（路径为 5 -> 8 -> 1）。
- 移除以 4 为根节点的子树。树的高度变为 3（路径为 5 -> 8 -> 2 -> 6）。
- 移除以 8 为根节点的子树。树的高度变为 2（路径为 5 -> 9 -> 3）。
``````

• 树中节点的数目是 `n`
• `2 <= n <= 105`
• `1 <= Node.val <= n`
• 树中的所有值 互不相同
• `m == queries.length`
• `1 <= m <= min(n, 104)`
• `1 <= queries[i] <= n`
• `queries[i] != root.val`

You are given the `root` of a binary tree with `n` nodes. Each node is assigned a unique value from `1` to `n`. You are also given an array `queries` of size `m`.

You have to perform `m` independent queries on the tree where in the `ith` query you do the following:

• Remove the subtree rooted at the node with the value `queries[i]` from the tree. It is guaranteed that `queries[i]` will not be equal to the value of the root.

Return an array `answer` of size `m` where `answer[i]` is the height of the tree after performing the `ith` query.

Note:

• The queries are independent, so the tree returns to its initial state after each query.
• The height of a tree is the number of edges in the longest simple path from the root to some node in the tree.

Example 1:

``````Input: root = [1,3,4,2,null,6,5,null,null,null,null,null,7], queries = [4]
Output: [2]
Explanation: The diagram above shows the tree after removing the subtree rooted at node with value 4.
The height of the tree is 2 (The path 1 -> 3 -> 2).
``````

Example 2:

``````Input: root = [5,8,9,2,1,3,7,4,6], queries = [3,2,4,8]
Output: [3,2,3,2]
Explanation: We have the following queries:
- Removing the subtree rooted at node with value 3. The height of the tree becomes 3 (The path 5 -> 8 -> 2 -> 4).
- Removing the subtree rooted at node with value 2. The height of the tree becomes 2 (The path 5 -> 8 -> 1).
- Removing the subtree rooted at node with value 4. The height of the tree becomes 3 (The path 5 -> 8 -> 2 -> 6).
- Removing the subtree rooted at node with value 8. The height of the tree becomes 2 (The path 5 -> 9 -> 3).
``````

Constraints:

• The number of nodes in the tree is `n`.
• `2 <= n <= 105`
• `1 <= Node.val <= n`
• All the values in the tree are unique.
• `m == queries.length`
• `1 <= m <= min(n, 104)`
• `1 <= queries[i] <= n`
• `queries[i] != root.val`

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

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/

#ifdef LOCAL

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

#endif

struct node {
int left_h = 0;
int right_h = 0;
int deep = 0;
};

class Solution {
public:
map<int, int> res;
map<int, node> tree_info;
int n;
int max_height;

int preDFS(TreeNode *root, int deep) {
++n;

int val = root->val;
auto &ti = tree_info[val];

ti.deep = deep;
max_height = max(max_height, deep);

if (root->left) {
ti.left_h = preDFS(root->left, deep + 1) + 1;
}

if (root->right) {
ti.right_h = preDFS(root->right, deep + 1) + 1;
}

return max(ti.left_h, ti.right_h);
}

void dfs(TreeNode *root, int mmax_height) {
int val = root->val;

const auto &ti = tree_info[val];
if (ti.left_h == ti.right_h) {
return;
}

if (ti.left_h > ti.right_h) {
int height = max(ti.deep + ti.right_h, mmax_height);
res[root->left->val] = height;
dfs(root->left, height);
} else {
int height = max(ti.deep + ti.left_h, mmax_height);
res[root->right->val] = height;
dfs(root->right, height);
}
}

vector<int> treeQueries(TreeNode *root, vector<int> &queries) {
res.clear();
tree_info.clear();

n = 0;
max_height = 0;

preDFS(root, 0);
dfs(root, -1);

// cout << max_hight << endl;

auto ans = vector<int>();
for (const auto &q : queries) {
if (res.count(q)) {
ans.push_back(res[q]);
} else {
ans.push_back(max_height);
}
}

return ans;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````