# weekly-contest-311

## A

### Statement

``````输入：n = 5

``````

``````输入：n = 6

``````

• `1 <= n <= 150`

Given a positive integer `n`, return the smallest positive integer that is a multiple of both `2` and `n`.

Example 1:

``````Input: n = 5
Output: 10
Explanation: The smallest multiple of both 5 and 2 is 10.
``````

Example 2:

``````Input: n = 6
Output: 6
Explanation: The smallest multiple of both 6 and 2 is 6. Note that a number is a multiple of itself.
``````

Constraints:

• `1 <= n <= 150`

### 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 smallestEvenMultiple(int n) {
return n * 2 / __gcd(n, 2);
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

• 例如，`"abc"` 是一个字母序连续字符串，而 `"acb"``"za"` 不是。

``````输入：s = "abacaba"

"ab" 是最长的字母序连续子字符串。
``````

``````输入：s = "abcde"

``````

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

An alphabetical continuous string is a string consisting of consecutive letters in the alphabet. In other words, it is any substring of the string `"abcdefghijklmnopqrstuvwxyz"`.

• For example, `"abc"` is an alphabetical continuous string, while `"acb"` and `"za"` are not.

Given a string `s` consisting of lowercase letters only, return the length of the longest alphabetical continuous substring.

Example 1:

``````Input: s = "abacaba"
Output: 2
Explanation: There are 4 distinct continuous substrings: "a", "b", "c" and "ab".
"ab" is the longest continuous substring.
``````

Example 2:

``````Input: s = "abcde"
Output: 5
Explanation: "abcde" is the longest continuous substring.
``````

Constraints:

• `1 <= s.length <= 105`
• `s` consists of only English lowercase letters.

### 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 longestContinuousSubstring(string s) {
int n = int(s.size());
int res = 1;
int cur = 1;

for (int i = 1; i < n; i++) {
if (s[i] == s[i - 1] + 1) {
++cur;
res = max(res, cur);
} else {
cur = 1;
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

• 例如，假设第 3 层的节点值是 `[2,1,3,4,7,11,29,18]` ，那么反转后它应该变成 `[18,29,11,7,4,3,1,2]`

``````输入：root = [2,3,5,8,13,21,34]

``````

``````输入：root = [7,13,11]

``````

``````输入：root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]

``````

• 树中的节点数目在范围 `[1, 214]`
• `0 <= Node.val <= 105`
• `root` 是一棵 完美 二叉树

Given the `root` of a perfect binary tree, reverse the node values at each odd level of the tree.

• For example, suppose the node values at level 3 are `[2,1,3,4,7,11,29,18]`, then it should become `[18,29,11,7,4,3,1,2]`.

Return the root of the reversed tree.

A binary tree is perfect if all parent nodes have two children and all leaves are on the same level.

The level of a node is the number of edges along the path between it and the root node.

Example 1:

``````Input: root = [2,3,5,8,13,21,34]
Output: [2,5,3,8,13,21,34]
Explanation:
The tree has only one odd level.
The nodes at level 1 are 3, 5 respectively, which are reversed and become 5, 3.
``````

Example 2:

``````Input: root = [7,13,11]
Output: [7,11,13]
Explanation:
The nodes at level 1 are 13, 11, which are reversed and become 11, 13.
``````

Example 3:

``````Input: root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]
Output: [0,2,1,0,0,0,0,2,2,2,2,1,1,1,1]
Explanation:
The odd levels have non-zero values.
The nodes at level 1 were 1, 2, and are 2, 1 after the reversal.
The nodes at level 3 were 1, 1, 1, 1, 2, 2, 2, 2, and are 2, 2, 2, 2, 1, 1, 1, 1 after the reversal.
``````

Constraints:

• The number of nodes in the tree is in the range `[1, 214]`.
• `0 <= Node.val <= 105`
• `root` is a perfect binary tree.

### 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 {
TreeNode *t{nullptr};
int dep{0};
};

class Solution {
public:
TreeNode *reverseOddLevels(TreeNode *root) {
queue<node> q;
q.push(node{
.t = root,
.dep = 0,
});

auto vec = vector<vector<node>>(20, vector<node>{});

while (!q.empty()) {
auto front = q.front();
q.pop();

vec[front.dep].push_back(front);
if (front.t->left) {
q.push(node{
.t = front.t->left,
.dep = front.dep + 1,
});
}

if (front.t->right) {
q.push(node{
.t = front.t->right,
.dep = front.dep + 1,
});
}
}

for (int i = 1; i < 20; i += 2) {
int n = int(vec[i].size());
for (int j = 0, k = n - 1; j < k; j++, k--) {
swap(vec[i][j].t->val, vec[i][k].t->val);
}
}

return root;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

• 例如，如果 `words = ["a", "ab", "abc", "cab"]` ，那么 `"ab"` 的分数是 `2` ，因为 `"ab"``"ab"``"abc"` 的一个前缀。

``````输入：words = ["abc","ab","bc","b"]

- "abc" 有 3 个前缀："a"、"ab" 和 "abc" 。
- 2 个字符串的前缀为 "a" ，2 个字符串的前缀为 "ab" ，1 个字符串的前缀为 "abc" 。

- "ab" 有 2 个前缀："a" 和 "ab" 。
- 2 个字符串的前缀为 "a" ，2 个字符串的前缀为 "ab" 。

- "bc" 有 2 个前缀："b" 和 "bc" 。
- 2 个字符串的前缀为 "b" ，1 个字符串的前缀为 "bc" 。

- "b" 有 1 个前缀："b"。
- 2 个字符串的前缀为 "b" 。

``````

``````输入：words = ["abcd"]

"abcd" 有 4 个前缀 "a"、"ab"、"abc" 和 "abcd"。

``````

• `1 <= words.length <= 1000`
• `1 <= words[i].length <= 1000`
• `words[i]` 由小写英文字母组成

You are given an array `words` of size `n` consisting of non-empty strings.

We define the score of a string `word` as the number of strings `words[i]` such that `word` is a prefix of `words[i]`.

• For example, if `words = ["a", "ab", "abc", "cab"]`, then the score of `"ab"` is `2`, since `"ab"` is a prefix of both `"ab"` and `"abc"`.

Return an array `answer` of size `n` where `answer[i]` is the sum of scores of every non-empty prefix of `words[i]`.

Note that a string is considered as a prefix of itself.

Example 1:

``````Input: words = ["abc","ab","bc","b"]
Output: [5,4,3,2]
Explanation: The answer for each string is the following:
- "abc" has 3 prefixes: "a", "ab", and "abc".
- There are 2 strings with the prefix "a", 2 strings with the prefix "ab", and 1 string with the prefix "abc".
The total is answer[0] = 2 + 2 + 1 = 5.
- "ab" has 2 prefixes: "a" and "ab".
- There are 2 strings with the prefix "a", and 2 strings with the prefix "ab".
The total is answer[1] = 2 + 2 = 4.
- "bc" has 2 prefixes: "b" and "bc".
- There are 2 strings with the prefix "b", and 1 string with the prefix "bc".
The total is answer[2] = 2 + 1 = 3.
- "b" has 1 prefix: "b".
- There are 2 strings with the prefix "b".
The total is answer[3] = 2.
``````

Example 2:

``````Input: words = ["abcd"]
Output: [4]
Explanation:
"abcd" has 4 prefixes: "a", "ab", "abc", and "abcd".
Each prefix has a score of one, so the total is answer[0] = 1 + 1 + 1 + 1 = 4.
``````

Constraints:

• `1 <= words.length <= 1000`
• `1 <= words[i].length <= 1000`
• `words[i]` consists of lowercase English letters.

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

constexpr int N = 1e6 + 10;

struct TRIE {
struct node {
int son[26];
int cnt;
node() {
memset(son, -1, sizeof son);
cnt = 0;
}
} t[N];
int rt, cnt;

void init() {
rt = 0;
t[0] = node();
cnt = 0;
}

void insert(const std::string &s) {
int cur_rt = rt;
for (const auto &c : s) {
if (t[cur_rt].son[c - 'a'] == -1) {
++cnt;
t[cnt] = node();
t[cur_rt].son[c - 'a'] = cnt;
}

cur_rt = t[cur_rt].son[c - 'a'];
++t[cur_rt].cnt;
}
}

int query(const std::string &s) {
int res = 0;
int cur_rt = rt;
for (const auto &c : s) {
cur_rt = t[cur_rt].son[c - 'a'];
res += t[cur_rt].cnt;
}

return res;
}
} tr;

class Solution {
public:
vector<int> sumPrefixScores(vector<string> &words) {
tr.init();

for (const auto &w : words) {
tr.insert(w);
}

auto res = vector<int>();
for (const auto &w : words) {
res.push_back(tr.query(w));
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````