# weekly-contest-319

## A

### Statement

• `开氏度 = 摄氏度 + 273.15`
• `华氏度 = 摄氏度 * 1.80 + 32.00`

``````输入：celsius = 36.50

``````输入：celsius = 122.11

``````

• `0 <= celsius <= 1000`

You are given a non-negative floating point number rounded to two decimal places `celsius`, that denotes the temperature in Celsius.

You should convert Celsius into Kelvin and Fahrenheit and return it as an array `ans = [kelvin, fahrenheit]`.

Return the array `ans`. Answers within `10-5` of the actual answer will be accepted.

Note that:

• `Kelvin = Celsius + 273.15`
• `Fahrenheit = Celsius * 1.80 + 32.00`

Example 1:

``````Input: celsius = 36.50
Output: [309.65000,97.70000]
Explanation: Temperature at 36.50 Celsius converted in Kelvin is 309.65 and converted in Fahrenheit is 97.70.
``````

Example 2:

``````Input: celsius = 122.11
Output: [395.26000,251.79800]
Explanation: Temperature at 122.11 Celsius converted in Kelvin is 395.26 and converted in Fahrenheit is 251.798.
``````

Constraints:

• `0 <= celsius <= 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:
vector<double> convertTemperature(double celsius) {
return vector<double>({celsius + 273.15, celsius * 1.8 + 32});
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

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

- [3,6,2,7,1]
- [3,6,2,7,1]
- [3,6,2,7,1]
- [3,6,2,7,1]
``````

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

``````

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

Given an integer array `nums` and an integer `k`, return the number of subarrays of `nums` where the least common multiple of the subarray's elements is `k`.

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

The least common multiple of an array is the smallest positive integer that is divisible by all the array elements.

Example 1:

``````Input: nums = [3,6,2,7,1], k = 6
Output: 4
Explanation: The subarrays of nums where 6 is the least common multiple of all the subarray's elements are:
- [3,6,2,7,1]
- [3,6,2,7,1]
- [3,6,2,7,1]
- [3,6,2,7,1]
``````

Example 2:

``````Input: nums = [3], k = 2
Output: 0
Explanation: There are no subarrays of nums where 2 is the least common multiple of all the subarray's elements.
``````

Constraints:

• `1 <= nums.length <= 1000`
• `1 <= nums[i], k <= 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 subarrayLCM(vector<int> &nums, int k) {
int n = int(nums.size());

int res = 0;

for (int i = 0; i < n; i++) {
ll pre = 1;
for (int j = i; j < n; j++) {
pre = pre * nums[j] / __gcd(pre, ll(nums[j]));
if (pre > k) {
break;
}

if (pre == k) {
++res;
}
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

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

- 交换 4 和 3 。第 2 层变为 [3,4] 。
- 交换 7 和 5 。第 3 层变为 [5,6,8,7] 。
- 交换 8 和 7 。第 3 层变为 [5,6,7,8] 。

``````

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

- 交换 3 和 2 。第 2 层变为 [2,3] 。
- 交换 7 和 4 。第 3 层变为 [4,6,5,7] 。
- 交换 6 和 5 。第 3 层变为 [4,5,6,7] 。

``````

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

``````

• 树中节点的数目在范围 `[1, 105]`
• `1 <= Node.val <= 105`
• 树中的所有值 互不相同

You are given the `root` of a binary tree with unique values.

In one operation, you can choose any two nodes at the same level and swap their values.

Return the minimum number of operations needed to make the values at each level sorted in a strictly increasing order.

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

Example 1:

``````Input: root = [1,4,3,7,6,8,5,null,null,null,null,9,null,10]
Output: 3
Explanation:
- Swap 4 and 3. The 2nd level becomes [3,4].
- Swap 7 and 5. The 3rd level becomes [5,6,8,7].
- Swap 8 and 7. The 3rd level becomes [5,6,7,8].
We used 3 operations so return 3.
It can be proven that 3 is the minimum number of operations needed.
``````

Example 2:

``````Input: root = [1,3,2,7,6,5,4]
Output: 3
Explanation:
- Swap 3 and 2. The 2nd level becomes [2,3].
- Swap 7 and 4. The 3rd level becomes [4,6,5,7].
- Swap 6 and 5. The 3rd level becomes [4,5,6,7].
We used 3 operations so return 3.
It can be proven that 3 is the minimum number of operations needed.
``````

Example 3:

``````Input: root = [1,2,3,4,5,6]
Output: 0
Explanation: Each level is already sorted in increasing order so return 0.
``````

Constraints:

• The number of nodes in the tree is in the range `[1, 105]`.
• `1 <= Node.val <= 105`
• All the values of the tree are unique.

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

class Solution {
public:
vector<vector<int>> vec;
int max_depth = 0;
void getMaxDepth(TreeNode *rt, int deep) {
if (!rt) {
return;
}

max_depth = max(max_depth, deep);
getMaxDepth(rt->left, deep + 1);
getMaxDepth(rt->right, deep + 1);
}

void dfs(TreeNode *rt, int deep) {
if (!rt) {
return;
}

vec[deep].push_back(rt->val);
dfs(rt->left, deep + 1);
dfs(rt->right, deep + 1);
}

int getMinSwaps(const vector<int> &A) {
vector<int> B(A);
sort(B.begin(), B.end());
map<int, int> m;
int len = (int)A.size();
for (int i = 0; i < len; i++) {
m[B[i]] = i;
}
int loops = 0;
vector<bool> flag(len, false);
for (int i = 0; i < len; i++) {
if (!flag[i]) {
int j = i;
while (!flag[j]) {
flag[j] = true;
j = m[A[j]];
}
loops++;
}
}
return len - loops;
}

int minimumOperations(TreeNode *root) {
max_depth = 0;
getMaxDepth(root, 1);
vec = vector<vector<int>>(max_depth + 5, vector<int>());
dfs(root, 0);

int res = 0;
for (const auto &v : vec) {
res += getMinSwaps(v);
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

• 每个子字符串的长度 至少`k`
• 每个子字符串是一个 回文串

``````输入：s = "abaccdbbd", k = 3

``````

``````输入：s = "adbcda", k = 2

``````

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

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

Select a set of non-overlapping substrings from the string `s` that satisfy the following conditions:

• The length of each substring is at least `k`.
• Each substring is a palindrome.

Return the maximum number of substrings in an optimal selection.

A substring is a contiguous sequence of characters within a string.

Example 1:

``````Input: s = "abaccdbbd", k = 3
Output: 2
Explanation: We can select the substrings underlined in s = "abaccdbbd". Both "aba" and "dbbd" are palindromes and have a length of at least k = 3.
It can be shown that we cannot find a selection with more than two valid substrings.
``````

Example 2:

``````Input: s = "adbcda", k = 2
Output: 0
Explanation: There is no palindrome substring of length at least 2 in the string.
``````

Constraints:

• `1 <= k <= s.length <= 2000`
• `s` 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

class Manacher {
public:
Manacher() {}

Manacher(const int n) {
fake_s_.reserve(n << 1);
u.reserve(n << 1);
}

~Manacher() {}

// 0-index
void Build(const char *s, size_t len) {
this->len = static_cast<int>(len);
fake_s_.resize((len + 1) << 2);
u.resize((len + 1) << 2);

l = 0;

fake_s_[l++] = '\$';
fake_s_[l++] = '#';
for (size_t i = 0; i < len; i++) {
fake_s_[l++] = s[i];
fake_s_[l++] = '#';
}
fake_s_[l] = 0;

int mx = 0, id = 0;
for (int i = 0; i < l; i++) {
u[i] = mx > i ? std::min(u[2 * id - i], mx - i) : 1;

while (i - u[i] >= 0 && fake_s_[i + u[i]] == fake_s_[i - u[i]]) {
u[i]++;
}

if (i + u[i] > mx) {
mx = i + u[i];
id = i;
}
}

fake_s_.resize(l);
u.resize(l);
}

void Build(const char *s) {
Build(s, strlen(s));
}

void Build(const std::string &s) {
Build(s.c_str(), s.length());
}

// check if s[l:r + 1] is a palindrome.
bool IsPalindrome(int l, int r) const {
int il = (l + 1) * 2, ir = (r + 1) * 2;
int mid = (il + ir) / 2;
int len = (r - l + 2) / 2;
return (u[mid] / 2) >= len;
}

// get the length of the longest palindrome substring
int GetMaxLengthOfPalindromeSubstring() const {
int res = 0;

for (int i = 0; i < l; i++) {
res = std::max(res, u[i] - 1);
}

return res;
}

const std::vector<int> &GetU() {
return u;
}

private:
int len, l;
std::vector<char> fake_s_;
std::vector<int> u;
};

class Solution {
public:
int maxPalindromes(string s, int k) {
int n = int(s.size());
auto m = Manacher(n + 5);

m.Build(s);

auto f = vector<int>(n + 5, 0);

for (int i = 1; i <= n; i++) {
for (int j = i - k + 1; j >= 1; j--) {
if (m.IsPalindrome(j - 1, i - 1)) {
f[i] = max(f[i], f[j - 1] + 1);
}
}

f[i] = max(f[i], f[i - 1]);
}

return f[n];
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````