# weekly-contest-281

## A

### Statement

``````输入：num = 4

``````

``````输入：num = 30

2、4、6、8、11、13、15、17、19、20、22、24、26 和 28 。
``````

• `1 <= num <= 1000`

Given a positive integer `num`, return the number of positive integers less than or equal to `num` whose digit sums are even.

The digit sum of a positive integer is the sum of all its digits.

Example 1:

``````Input: num = 4
Output: 2
Explanation:
The only integers less than or equal to 4 whose digit sums are even are 2 and 4.
``````

Example 2:

``````Input: num = 30
Output: 14
Explanation:
The 14 integers less than or equal to 30 whose digit sums are even are
2, 4, 6, 8, 11, 13, 15, 17, 19, 20, 22, 24, 26, and 28.
``````

Constraints:

• `1 <= num <= 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>;
const ll mod = 1e9 + 7;

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 countEven(int num) {
auto f = [](int x) {
int res = 0;
while (x) {
res += x % 10;
x /= 10;
}
return res;
};

int res = 0;
for (int i = 1; i <= num; i++) {
res += f(i) % 2 == 0;
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

返回修改后链表的头节点 `head`

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

- 标记为绿色的节点之和：3 + 1 = 4
- 标记为红色的节点之和：4 + 5 + 2 = 11
``````

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

- 标记为绿色的节点之和：1 = 1
- 标记为红色的节点之和：3 = 3
- 标记为黄色的节点之和：2 + 2 = 4
``````

• 列表中的节点数目在范围 `[3, 2 * 105]`
• `0 <= Node.val <= 1000`
• 存在连续两个 `Node.val == 0` 的节点
• 链表的 开端末尾 节点都满足 `Node.val == 0`

You are given the `head` of a linked list, which contains a series of integers separated by `0`'s. The beginning and end of the linked list will have `Node.val == 0`.

For every two consecutive `0`'s, merge all the nodes lying in between them into a single node whose value is the sum of all the merged nodes. The modified list should not contain any `0`'s.

Return the `head` of the modified linked list.

Example 1:

``````Input: head = [0,3,1,0,4,5,2,0]
Output: [4,11]
Explanation:
The above figure represents the given linked list. The modified list contains
- The sum of the nodes marked in green: 3 + 1 = 4.
- The sum of the nodes marked in red: 4 + 5 + 2 = 11.
``````

Example 2:

``````Input: head = [0,1,0,3,0,2,2,0]
Output: [1,3,4]
Explanation:
The above figure represents the given linked list. The modified list contains
- The sum of the nodes marked in green: 1 = 1.
- The sum of the nodes marked in red: 3 = 3.
- The sum of the nodes marked in yellow: 2 + 2 = 4.
``````

Constraints:

• The number of nodes in the list is in the range `[3, 2 * 105]`.
• `0 <= Node.val <= 1000`
• There are no two consecutive nodes with `Node.val == 0`.
• The beginning and end of the linked list have `Node.val == 0`.

### 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>;
const ll mod = 1e9 + 7;

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 ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/

#ifdef LOCAL

struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};

#endif

class Solution {
public:
vector<int> val;
int tmp = 0;
if (tmp > 0) {
val.push_back(tmp);
}
tmp = 0;
} else {
}
}

ListNode *res = new ListNode();
for (auto &v : val) {
res->next = new ListNode(v);
res = res->next;
}

}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

``````输入：s = "cczazcc", repeatLimit = 3

``````

``````输入：s = "aababab", repeatLimit = 2

``````

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

You are given a string `s` and an integer `repeatLimit`. Construct a new string `repeatLimitedString` using the characters of `s` such that no letter appears more than `repeatLimit` times in a row. You do not have to use all characters from `s`.

Return the lexicographically largest `repeatLimitedString` possible.

A string `a` is lexicographically larger than a string `b` if in the first position where `a` and `b` differ, string `a` has a letter that appears later in the alphabet than the corresponding letter in `b`. If the first `min(a.length, b.length)` characters do not differ, then the longer string is the lexicographically larger one.

Example 1:

``````Input: s = "cczazcc", repeatLimit = 3
Output: "zzcccac"
Explanation: We use all of the characters from s to construct the repeatLimitedString "zzcccac".
The letter 'a' appears at most 1 time in a row.
The letter 'c' appears at most 3 times in a row.
The letter 'z' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "zzcccac".
Note that the string "zzcccca" is lexicographically larger but the letter 'c' appears more than 3 times in a row, so it is not a valid repeatLimitedString.
``````

Example 2:

``````Input: s = "aababab", repeatLimit = 2
Output: "bbabaa"
Explanation: We use only some of the characters from s to construct the repeatLimitedString "bbabaa".
The letter 'a' appears at most 2 times in a row.
The letter 'b' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "bbabaa".
Note that the string "bbabaaa" is lexicographically larger but the letter 'a' appears more than 2 times in a row, so it is not a valid repeatLimitedString.
``````

Constraints:

• `1 <= repeatLimit <= s.length <= 105`
• `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>;
const ll mod = 1e9 + 7;

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 repeatLimitedString(string s, int repeatLimit) {
vector<int> cnt(30, 0);
for (const auto &c : s) {
++cnt[c - 'a'];
}

string res = "@";
int sum = 0;
while (true) {
int f = 0;

for (int i = 25; i >= 0; i--) {
if (cnt[i] == 0) {
continue;
}

if (sum >= repeatLimit && i == res.back() - 'a') {
continue;
}

if (i == res.back() - 'a') {
++sum;
} else {
sum = 1;
}

res += char('a' + i);
--cnt[i];
f = 1;

break;
}

if (f == 0) {
break;
}
}

return res.substr(1);
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

• `0 <= i < j <= n - 1`
• `nums[i] * nums[j]` 能被 `k` 整除。

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

(0, 1)、(0, 3)、(1, 2)、(1, 3)、(1, 4)、(2, 3) 和 (3, 4)

``````

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

``````

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

Given a 0-indexed integer array `nums` of length `n` and an integer `k`, return the number of pairs `(i, j)` such that:

• `0 <= i < j <= n - 1` and
• `nums[i] * nums[j]` is divisible by `k`.

Example 1:

``````Input: nums = [1,2,3,4,5], k = 2
Output: 7
Explanation:
The 7 pairs of indices whose corresponding products are divisible by 2 are
(0, 1), (0, 3), (1, 2), (1, 3), (1, 4), (2, 3), and (3, 4).
Their products are 2, 4, 6, 8, 10, 12, and 20 respectively.
Other pairs such as (0, 2) and (2, 4) have products 3 and 15 respectively, which are not divisible by 2.
``````

Example 2:

``````Input: nums = [1,2,3,4], k = 5
Output: 0
Explanation: There does not exist any pair of indices whose corresponding product is divisible by 5.
``````

Constraints:

• `1 <= nums.length <= 105`
• `1 <= nums[i], k <= 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>;
const ll mod = 1e9 + 7;

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:
const int N = 1e5 + 10;
const int M = 1e5;

long long coutPairs(vector<int> &nums, int k) {
vector<int> cnt(N, 0);
for (auto &v : nums) {
++cnt[v];
}

vector<long long> f(N, 0);
for (int i = 1; i <= M; i++) {
for (int j = 1; j * i <= M; j++) {
f[i] += cnt[j * i];
}
}

int n = nums.size();
long long res = 0;

for (int i = 0; i < n; i++) {
int x = nums[i];
int y = k / __gcd(x, k);
res += f[y];
if (1ll * x * x % k == 0) {
--res;
}
}

return res / 2;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````