# weekly-contest-209

## A

### Statement

• Difficulty: Easy
• Tag: `数组` `二分查找` `排序`

``````输入：nums = [3,5]

``````

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

x 不能取更大的值，因为 nums 中只有两个元素。``````

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

``````

``````输入：nums = [3,6,7,7,0]

``````

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

You are given an array `nums` of non-negative integers. `nums` is considered special if there exists a number `x` such that there are exactly `x` numbers in `nums` that are greater than or equal to `x`.

Notice that `x` does not have to be an element in `nums`.

Return `x` if the array is special, otherwise, return `-1`. It can be proven that if `nums` is special, the value for `x` is unique.

Example 1:

``````Input: nums = [3,5]
Output: 2
Explanation: There are 2 values (3 and 5) that are greater than or equal to 2.
``````

Example 2:

``````Input: nums = [0,0]
Output: -1
Explanation: No numbers fit the criteria for x.
If x = 0, there should be 0 numbers >= x, but there are 2.
If x = 1, there should be 1 number >= x, but there are 0.
If x = 2, there should be 2 numbers >= x, but there are 0.
x cannot be greater since there are only 2 numbers in nums.
``````

Example 3:

``````Input: nums = [0,4,3,0,4]
Output: 3
Explanation: There are 3 values that are greater than or equal to 3.
``````

Constraints:

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

### Solution

``````#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
x += y;
while (x >= Mod) x -= Mod;
while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
if (x < y)
x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
if (x > y)
x = y;
}
inline int nextInt() {
int x;
cin >> x;
return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
cin >> arg;
rd(args...);
}
#define dbg(x...)                             \
do {                                      \
cout << "\033[32;1m" << #x << " -> "; \
err(x);                               \
} while (0)
void err() {
cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
cout << arg << ' ';
err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
for (auto &v : arg) cout << v << ' ';
err(args...);
}
void ptt() {
cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
cout << ' ' << arg;
ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
cout << arg;
ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
pt(args...);
}
inline ll qpow(ll base, ll n) {
assert(n >= 0);
ll res = 1;
while (n) {
if (n & 1)
res = res * base % mod;
base = base * base % mod;
n >>= 1;
}
return res;
}
constexpr int N = 1e5 + 10;
int n;

class Solution {
public:
int specialArray(vector<int> &nums) {
sort(all(nums));
n = SZ(nums);
int pos = 0;
for (int i = 0; i <= 1000; ++i) {
while (pos < n && nums[pos] < i) ++pos;
if (n - pos == i)
return i;
}
return -1;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

• Difficulty: Medium
• Tag: `树` `广度优先搜索` `二叉树`

• 二叉树根节点所在层下标为 `0` ，根的子节点所在层下标为 `1` ，根的孙节点所在层下标为 `2` ，依此类推。
• 偶数下标 层上的所有节点的值都是 整数，从左到右按顺序 严格递增
• 奇数下标 层上的所有节点的值都是 整数，从左到右按顺序 严格递减

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

0 层：[1]
1 层：[10,4]
2 层：[3,7,9]
3 层：[12,8,6,2]

``````

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

0 层：[5]
1 层：[4,2]
2 层：[3,3,7]
2 层上的节点值不满足严格递增的条件，所以这不是一棵奇偶树。
``````

``````输入：root = [5,9,1,3,5,7]

``````

``````输入：root = [1]

``````

``````输入：root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17]

``````

• 树中节点数在范围 `[1, 105]`
• `1 <= Node.val <= 106`

• Link: Even Odd Tree
• Difficulty: Medium
• Tag: `Tree` `Breadth-First Search` `Binary Tree`

A binary tree is named Even-Odd if it meets the following conditions:

• The root of the binary tree is at level index `0`, its children are at level index `1`, their children are at level index `2`, etc.
• For every even-indexed level, all nodes at the level have odd integer values in strictly increasing order (from left to right).
• For every odd-indexed level, all nodes at the level have even integer values in strictly decreasing order (from left to right).

Given the `root` of a binary tree, return `true` if the binary tree is Even-Odd, otherwise return `false`.

Example 1:

``````Input: root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
Output: true
Explanation: The node values on each level are:
Level 0: [1]
Level 1: [10,4]
Level 2: [3,7,9]
Level 3: [12,8,6,2]
Since levels 0 and 2 are all odd and increasing and levels 1 and 3 are all even and decreasing, the tree is Even-Odd.
``````

Example 2:

``````Input: root = [5,4,2,3,3,7]
Output: false
Explanation: The node values on each level are:
Level 0: [5]
Level 1: [4,2]
Level 2: [3,3,7]
Node values in level 2 must be in strictly increasing order, so the tree is not Even-Odd.
``````

Example 3:

``````Input: root = [5,9,1,3,5,7]
Output: false
Explanation: Node values in the level 1 should be even integers.
``````

Constraints:

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

### Solution

``````#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
x += y;
while (x >= Mod) x -= Mod;
while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
if (x < y)
x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
if (x > y)
x = y;
}
inline int nextInt() {
int x;
cin >> x;
return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
cin >> arg;
rd(args...);
}
#define dbg(x...)                             \
do {                                      \
cout << "\033[32;1m" << #x << " -> "; \
err(x);                               \
} while (0)
void err() {
cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
cout << arg << ' ';
err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
for (auto &v : arg) cout << v << ' ';
err(args...);
}
void ptt() {
cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
cout << ' ' << arg;
ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
cout << arg;
ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
pt(args...);
}
inline ll qpow(ll base, ll n) {
assert(n >= 0);
ll res = 1;
while (n) {
if (n & 1)
res = res * base % mod;
base = base * base % mod;
n >>= 1;
}
return res;
}
constexpr int N = 1e5 + 10;
constexpr int INF = 0x3f3f3f3f;
int n;

/**
* 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) {}
* };
*/
class Solution {
public:
bool isEvenOddTree(TreeNode *root) {
vector<vector<int>> vec;
queue<TreeNode *> que;
que.push(root);
while (!que.empty()) {
queue<TreeNode *> _que;
vector<int> _vec;
while (!que.empty()) {
TreeNode *rt = que.front();
que.pop();
_vec.push_back(rt->val);
if (rt->left)
_que.push(rt->left);
if (rt->right)
_que.push(rt->right);
}
que = _que;
vec.push_back(_vec);
}
for (int i = 0; i < SZ(vec); ++i) {
int f = i & 1 ^ 1;
int pre = f ? 0 : INF;
for (auto &x : vec[i]) {
if ((x & 1) != f)
return false;
if (f && x <= pre)
return false;
if (!f && x >= pre)
return false;
pre = x;
}
}
return true;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

• Difficulty: Hard
• Tag: `几何` `数组` `数学` `排序` `滑动窗口`

``````输入：points = [[2,1],[2,2],[3,3]], angle = 90, location = [1,1]

``````输入：points = [[2,1],[2,2],[3,4],[1,1]], angle = 90, location = [1,1]

``````输入：points = [[1,0],[2,1]], angle = 13, location = [1,1]

• `1 <= points.length <= 105`
• `points[i].length == 2`
• `location.length == 2`
• `0 <= angle < 360`
• `0 <= posx, posy, xi, yi <= 100`

• Link: Maximum Number of Visible Points
• Difficulty: Hard
• Tag: `Geometry` `Array` `Math` `Sorting` `Sliding Window`

You are given an array `points`, an integer `angle`, and your `location`, where `location = [posx, posy]` and `points[i] = [xi, yi]` both denote integral coordinates on the X-Y plane.

Initially, you are facing directly east from your position. You cannot move from your position, but you can rotate. In other words, `posx` and `posy` cannot be changed. Your field of view in degrees is represented by `angle`, determining how wide you can see from any given view direction. Let `d` be the amount in degrees that you rotate counterclockwise. Then, your field of view is the inclusive range of angles `[d - angle/2, d + angle/2]`.

You can see some set of points if, for each point, the angle formed by the point, your position, and the immediate east direction from your position is in your field of view.

There can be multiple points at one coordinate. There may be points at your location, and you can always see these points regardless of your rotation. Points do not obstruct your vision to other points.

Return the maximum number of points you can see.

Example 1:

``````Input: points = [[2,1],[2,2],[3,3]], angle = 90, location = [1,1]
Output: 3
Explanation: The shaded region represents your field of view. All points can be made visible in your field of view, including [3,3] even though [2,2] is in front and in the same line of sight.
``````

Example 2:

``````Input: points = [[2,1],[2,2],[3,4],[1,1]], angle = 90, location = [1,1]
Output: 4
Explanation: All points can be made visible in your field of view, including the one at your location.
``````

Example 3:

``````Input: points = [[1,0],[2,1]], angle = 13, location = [1,1]
Output: 1
Explanation: You can only see one of the two points, as shown above.
``````

Constraints:

• `1 <= points.length <= 105`
• `points[i].length == 2`
• `location.length == 2`
• `0 <= angle < 360`
• `0 <= posx, posy, xi, yi <= 100`

## D

### Statement

• 翻转 `n` 的二进制表示中最右侧位（第 `0` 位）。
• 如果第 `(i-1)` 位为 `1` 且从第 `(i-2)` 位到第 `0` 位都为 `0`，则翻转 `n` 的二进制表示中的第 `i` 位。

``````输入：n = 0

``````

``````输入：n = 3

"11" -> "01" ，执行的是第 2 种操作，因为第 0 位为 1 。
"01" -> "00" ，执行的是第 1 种操作。
``````

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

"110" -> "010" ，执行的是第 2 种操作，因为第 1 位为 1 ，第 0 到 0 位为 0 。
"010" -> "011" ，执行的是第 1 种操作。
"011" -> "001" ，执行的是第 2 种操作，因为第 0 位为 1 。
"001" -> "000" ，执行的是第 1 种操作。
``````

``````输入：n = 9

``````

``````输入：n = 333

``````

• `0 <= n <= 109`

Given an integer `n`, you must transform it into `0` using the following operations any number of times:

• Change the rightmost (`0th`) bit in the binary representation of `n`.
• Change the `ith` bit in the binary representation of `n` if the `(i-1)th` bit is set to `1` and the `(i-2)th` through `0th` bits are set to `0`.

Return the minimum number of operations to transform `n` into `0`.

Example 1:

``````Input: n = 3
Output: 2
Explanation: The binary representation of 3 is "11".
"11" -> "01" with the 2nd operation since the 0th bit is 1.
"01" -> "00" with the 1st operation.
``````

Example 2:

``````Input: n = 6
Output: 4
Explanation: The binary representation of 6 is "110".
"110" -> "010" with the 2nd operation since the 1st bit is 1 and 0th through 0th bits are 0.
"010" -> "011" with the 1st operation.
"011" -> "001" with the 2nd operation since the 0th bit is 1.
"001" -> "000" with the 1st operation.
``````

Constraints:

• `0 <= n <= 109`

### Solution

``````#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
x += y;
while (x >= Mod) x -= Mod;
while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
if (x < y)
x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
if (x > y)
x = y;
}
inline int nextInt() {
int x;
cin >> x;
return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
cin >> arg;
rd(args...);
}
#define dbg(x...)                             \
do {                                      \
cout << "\033[32;1m" << #x << " -> "; \
err(x);                               \
} while (0)
void err() {
cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
cout << arg << ' ';
err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
for (auto &v : arg) cout << v << ' ';
err(args...);
}
void ptt() {
cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
cout << ' ' << arg;
ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
cout << arg;
ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
pt(args...);
}
inline ll qpow(ll base, ll n) {
assert(n >= 0);
ll res = 1;
while (n) {
if (n & 1)
res = res * base % mod;
base = base * base % mod;
n >>= 1;
}
return res;
}
constexpr int N = 1e5 + 10;
int n;

map<int, int> mp;

int dfs(int n) {
if (!n)
return 0;
if (n == 1)
return mp[n] = 1;
if (mp.count(n))
return mp[n];
int f = 1 + dfs(n ^ 1);
int x = __builtin_ffs(n);
if (x <= 30)
chmin(f, 1 + dfs(n ^ (1 << x)));
return mp[n] = f;
}

class Solution {
public:
int minimumOneBitOperations(int n) {
mp.clear();
return dfs(n);
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````