# weekly-contest-299

## A

### Statement

1. 矩阵对角线上的所有元素都 不是 0
2. 矩阵中所有其他元素都是 0

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

X 矩阵应该满足：绿色元素（对角线上）都不是 0 ，红色元素都是 0 。

``````

``````输入：grid = [[5,7,0],[0,3,1],[0,5,0]]

X 矩阵应该满足：绿色元素（对角线上）都不是 0 ，红色元素都是 0 。

``````

• `n == grid.length == grid[i].length`
• `3 <= n <= 100`
• `0 <= grid[i][j] <= 105`

A square matrix is said to be an X-Matrix if both of the following conditions hold:

1. All the elements in the diagonals of the matrix are non-zero.
2. All other elements are 0.

Given a 2D integer array `grid` of size `n x n` representing a square matrix, return `true` if `grid` is an X-Matrix. Otherwise, return `false`.

Example 1:

``````Input: grid = [[2,0,0,1],[0,3,1,0],[0,5,2,0],[4,0,0,2]]
Output: true
Explanation: Refer to the diagram above.
An X-Matrix should have the green elements (diagonals) be non-zero and the red elements be 0.
Thus, grid is an X-Matrix.
``````

Example 2:

``````Input: grid = [[5,7,0],[0,3,1],[0,5,0]]
Output: false
Explanation: Refer to the diagram above.
An X-Matrix should have the green elements (diagonals) be non-zero and the red elements be 0.
Thus, grid is not an X-Matrix.
``````

Constraints:

• `n == grid.length == grid[i].length`
• `3 <= n <= 100`
• `0 <= grid[i][j] <= 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

class Solution {
public:
bool checkXMatrix(vector<vector<int>> &grid) {
int n = grid.size();

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
if (grid[i][j] == 0)
return false;
} else if (i + j == n - 1) {
if (grid[i][j] == 0)
return false;
} else if (grid[i][j] != 0) {
return false;
}
}
}

return true;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

``````输入：n = 1

1. 所有地块都不放置房子。
2. 一所房子放在街道的某一侧。
3. 一所房子放在街道的另一侧。
4. 放置两所房子，街道两侧各放置一所。
``````

``````输入：n = 2

``````

• `1 <= n <= 104`

There is a street with `n * 2` plots, where there are `n` plots on each side of the street. The plots on each side are numbered from `1` to `n`. On each plot, a house can be placed.

Return the number of ways houses can be placed such that no two houses are adjacent to each other on the same side of the street. Since the answer may be very large, return it modulo `109 + 7`.

Note that if a house is placed on the `ith` plot on one side of the street, a house can also be placed on the `ith` plot on the other side of the street.

Example 1:

``````Input: n = 1
Output: 4
Explanation:
Possible arrangements:
1. All plots are empty.
2. A house is placed on one side of the street.
3. A house is placed on the other side of the street.
4. Two houses are placed, one on each side of the street.
``````

Example 2:

``````Input: n = 2
Output: 9
Explanation: The 9 possible arrangements are shown in the diagram above.
``````

Constraints:

• `1 <= n <= 104`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <vector>

#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

const int mod = 1e9 + 7;

class Solution {
public:
int countHousePlacements(int n) {
static auto f = std::invoke([]() {
const int n = 1e4;

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

f[0][0] = 1;

for (int i = 1; i <= n; i++) {
f[i][0] = f[i - 1][0] + f[i - 1][1];
f[i][0] %= mod;
f[i][1] = f[i - 1][0];
}

return f;
});

ll res = f[n][0] + f[n][1];
res %= mod;
res *= res;
res %= mod;

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

• 例如，设 `nums1 = [1,2,3,4,5]``nums2 = [11,12,13,14,15]` ，整数选择 `left = 1``right = 2`，那么 `nums1` 会变为 `[1,12,13,4,5]``nums2` 会变为 `[11,2,3,14,15]`

``````输入：nums1 = [60,60,60], nums2 = [10,90,10]

``````输入：nums1 = [20,40,20,70,30], nums2 = [50,20,50,40,20]

``````

``````输入：nums1 = [7,11,13], nums2 = [1,1,1]

``````

• `n == nums1.length == nums2.length`
• `1 <= n <= 105`
• `1 <= nums1[i], nums2[i] <= 104`

You are given two 0-indexed integer arrays `nums1` and `nums2`, both of length `n`.

You can choose two integers `left` and `right` where `0 <= left <= right < n` and swap the subarray `nums1[left…right]` with the subarray `nums2[left…right]`.

• For example, if `nums1 = [1,2,3,4,5]` and `nums2 = [11,12,13,14,15]` and you choose `left = 1` and `right = 2`, `nums1` becomes `[1,12,13,4,5]` and `nums2` becomes `[11,2,3,14,15]`.

You may choose to apply the mentioned operation once or not do anything.

The score of the arrays is the maximum of `sum(nums1)` and `sum(nums2)`, where `sum(arr)` is the sum of all the elements in the array `arr`.

Return the maximum possible score.

A subarray is a contiguous sequence of elements within an array. `arr[left…right]` denotes the subarray that contains the elements of `nums` between indices `left` and `right` (inclusive).

Example 1:

``````Input: nums1 = [60,60,60], nums2 = [10,90,10]
Output: 210
Explanation: Choosing left = 1 and right = 1, we have nums1 = [60,90,60] and nums2 = [10,60,10].
The score is max(sum(nums1), sum(nums2)) = max(210, 80) = 210.``````

Example 2:

``````Input: nums1 = [20,40,20,70,30], nums2 = [50,20,50,40,20]
Output: 220
Explanation: Choosing left = 3, right = 4, we have nums1 = [20,40,20,40,20] and nums2 = [50,20,50,70,30].
The score is max(sum(nums1), sum(nums2)) = max(140, 220) = 220.
``````

Example 3:

``````Input: nums1 = [7,11,13], nums2 = [1,1,1]
Output: 31
Explanation: We choose not to swap any subarray.
The score is max(sum(nums1), sum(nums2)) = max(31, 3) = 31.
``````

Constraints:

• `n == nums1.length == nums2.length`
• `1 <= n <= 105`
• `1 <= nums1[i], nums2[i] <= 104`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <numeric>
#include <vector>

#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 maximumsSplicedArray(vector<int> &nums1, vector<int> &nums2) {
auto f = [](vector<int> &nums1, vector<int> &nums2) {
int res = accumulate(nums1.begin(), nums1.end(), 0);
res = max(res, accumulate(nums2.begin(), nums2.end(), 0));

int n = int(nums1.size());

auto f = vector<int>(n + 5, 0);
for (int i = n; i >= 1; i--) {
f[i] = f[i + 1] + nums1[i - 1];
}

auto g = vector<vector<int>>(2, vector<int>(n + 5, 0));
for (int i = 1; i <= n; i++) {
g[0][i] = g[0][i - 1] + nums1[i - 1];
g[1][i] = g[1][i - 1] + nums2[i - 1];
}

int mx = 0;

for (int i = 1; i <= n; i++) {
mx = max(mx, g[0][i] - g[1][i]);
res = max(res, g[1][i] + f[i + 1] + mx);
}

return res;
};

int res = f(nums1, nums2);
res = max(res, f(nums2, nums1));
return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

1. 分别获取三个组件 每个 组件中所有节点值的异或值。
2. 最大 异或值和 最小 异或值的 差值 就是这一种删除边方案的分数。
• 例如，三个组件的节点值分别是：`[4,5,7]``[1,9]``[3,3,3]` 。三个异或值分别是 `4 ^ 5 ^ 7 = 6``1 ^ 9 = 8``3 ^ 3 ^ 3 = 3` 。最大异或值是 `8` ，最小异或值是 `3` ，分数是 `8 - 3 = 5`

``````输入：nums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]]

- 第 1 个组件的节点是 [1,3,4] ，值是 [5,4,11] 。异或值是 5 ^ 4 ^ 11 = 10 。
- 第 2 个组件的节点是 [0] ，值是 [1] 。异或值是 1 = 1 。
- 第 3 个组件的节点是 [2] ，值是 [5] 。异或值是 5 = 5 。

``````

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

- 第 1 个组件的节点是 [3,4] ，值是 [4,4] 。异或值是 4 ^ 4 = 0 。
- 第 2 个组件的节点是 [1,0] ，值是 [5,5] 。异或值是 5 ^ 5 = 0 。
- 第 3 个组件的节点是 [2,5] ，值是 [2,2] 。异或值是 2 ^ 2 = 0 。

``````

• `n == nums.length`
• `3 <= n <= 1000`
• `1 <= nums[i] <= 108`
• `edges.length == n - 1`
• `edges[i].length == 2`
• `0 <= ai, bi < n`
• `ai != bi`
• `edges` 表示一棵有效的树

There is an undirected connected tree with `n` nodes labeled from `0` to `n - 1` and `n - 1` edges.

You are given a 0-indexed integer array `nums` of length `n` where `nums[i]` represents the value of the `ith` node. You are also given a 2D integer array `edges` of length `n - 1` where `edges[i] = [ai, bi]` indicates that there is an edge between nodes `ai` and `bi` in the tree.

Remove two distinct edges of the tree to form three connected components. For a pair of removed edges, the following steps are defined:

1. Get the XOR of all the values of the nodes for each of the three components respectively.
2. The difference between the largest XOR value and the smallest XOR value is the score of the pair.
• For example, say the three components have the node values: `[4,5,7]`, `[1,9]`, and `[3,3,3]`. The three XOR values are `4 ^ 5 ^ 7 = 6`, `1 ^ 9 = 8`, and `3 ^ 3 ^ 3 = 3`. The largest XOR value is `8` and the smallest XOR value is `3`. The score is then `8 - 3 = 5`.

Return the minimum score of any possible pair of edge removals on the given tree.

Example 1:

``````Input: nums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]]
Output: 9
Explanation: The diagram above shows a way to make a pair of removals.
- The 1st component has nodes [1,3,4] with values [5,4,11]. Its XOR value is 5 ^ 4 ^ 11 = 10.
- The 2nd component has node [0] with value [1]. Its XOR value is 1 = 1.
- The 3rd component has node [2] with value [5]. Its XOR value is 5 = 5.
The score is the difference between the largest and smallest XOR value which is 10 - 1 = 9.
It can be shown that no other pair of removals will obtain a smaller score than 9.
``````

Example 2:

``````Input: nums = [5,5,2,4,4,2], edges = [[0,1],[1,2],[5,2],[4,3],[1,3]]
Output: 0
Explanation: The diagram above shows a way to make a pair of removals.
- The 1st component has nodes [3,4] with values [4,4]. Its XOR value is 4 ^ 4 = 0.
- The 2nd component has nodes [1,0] with values [5,5]. Its XOR value is 5 ^ 5 = 0.
- The 3rd component has nodes [2,5] with values [2,2]. Its XOR value is 2 ^ 2 = 0.
The score is the difference between the largest and smallest XOR value which is 0 - 0 = 0.
We cannot obtain a smaller score than 0.
``````

Constraints:

• `n == nums.length`
• `3 <= n <= 1000`
• `1 <= nums[i] <= 108`
• `edges.length == n - 1`
• `edges[i].length == 2`
• `0 <= ai, bi < n`
• `ai != bi`
• `edges` represents a valid tree.

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <vector>

#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<int> f, w;
vector<vector<int>> g, h;

void dfs(int u, int fa, vector<int> &fas) {
int xor_sum = w[u];

h[u] = vector<int>(fas);
fas[u] = 1;

for (auto &v : g[u]) {
if (v == fa) {
continue;
}

dfs(v, u, fas);
xor_sum ^= f[v];
}

f[u] = xor_sum;
fas[u] = 0;
}

int minimumScore(vector<int> &nums, vector<vector<int>> &edges) {
int n = int(nums.size());

w = vector<int>(nums);
f = vector<int>(n + 1, 0);
g = vector<vector<int>>(n + 1, vector<int>());
h = vector<vector<int>>(n + 1, vector<int>());

for (auto &e : edges) {
g[e[0]].push_back(e[1]);
g[e[1]].push_back(e[0]);
}

auto fas = vector<int>(n + 1, 0);
dfs(0, 0, fas);

int res = 2e9;
for (int i = 1; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int x = i;
int y = j;

if (h[y][x]) {
swap(x, y);
}

auto t = vector<int>();
t.reserve(3);

if (h[x][y] == 1) {
t.push_back(f[0] ^ f[y]);
t.push_back(f[x]);
t.push_back(f[y] ^ f[x]);
} else {
t.push_back(f[0] ^ f[x] ^ f[y]);
t.push_back(f[x]);
t.push_back(f[y]);
}

sort(t.begin(), t.end());

res = min(res, t[2] - t[0]);
}
}

return res;
}
};

#ifdef LOCAL

int main() {
{
auto nums = vector<int>({1, 5, 5, 4, 11});
auto edges = vector<vector<int>>({{0, 1}, {1, 2}, {1, 3}, {3, 4}});
auto s = Solution();
auto res = s.minimumScore(nums, edges);
cout << res << endl;
}
return 0;
}

#endif
``````