跳转至

biweekly-contest-95

A

Statement

Metadata

给你四个整数 length ,width ,height 和 mass ,分别表示一个箱子的三个维度和质量,请你返回一个表示箱子 类别 的字符串。

  • 如果满足以下条件,那么箱子是 "Bulky" 的:
    • 箱子 至少有一个 维度大于等于 104 。
    • 或者箱子的 体积 大于等于 109 。
  • 如果箱子的质量大于等于 100 ,那么箱子是 "Heavy" 的。
  • 如果箱子同时是 "Bulky" 和 "Heavy" ,那么返回类别为 "Both" 。
  • 如果箱子既不是 "Bulky" ,也不是 "Heavy" ,那么返回类别为 "Neither" 。
  • 如果箱子是 "Bulky" 但不是 "Heavy" ,那么返回类别为 "Bulky" 。
  • 如果箱子是 "Heavy" 但不是 "Bulky" ,那么返回类别为 "Heavy" 。

注意,箱子的体积等于箱子的长度、宽度和高度的乘积。

 

示例 1:

输入:length = 1000, width = 35, height = 700, mass = 300
输出:"Heavy"
解释:
箱子没有任何维度大于等于 104 。
体积为 24500000 <= 109 。所以不能归类为 "Bulky" 。
但是质量 >= 100 ,所以箱子是 "Heavy" 的。
由于箱子不是 "Bulky" 但是是 "Heavy" ,所以我们返回 "Heavy" 。

示例 2:

输入:length = 200, width = 50, height = 800, mass = 50
输出:"Neither"
解释:
箱子没有任何维度大于等于 104 。
体积为 8 * 106 <= 109 。所以不能归类为 "Bulky" 。
质量小于 100 ,所以不能归类为 "Heavy" 。
由于不属于上述两者任何一类,所以我们返回 "Neither" 。

 

提示:

  • 1 <= length, width, height <= 105
  • 1 <= mass <= 103

Metadata

Given four integers length, width, height, and mass, representing the dimensions and mass of a box, respectively, return a string representing the category of the box.

  • The box is "Bulky" if:
    • Any of the dimensions of the box is greater or equal to 104.
    • Or, the volume of the box is greater or equal to 109.
  • If the mass of the box is greater or equal to 100, it is "Heavy".
  • If the box is both "Bulky" and "Heavy", then its category is "Both".
  • If the box is neither "Bulky" nor "Heavy", then its category is "Neither".
  • If the box is "Bulky" but not "Heavy", then its category is "Bulky".
  • If the box is "Heavy" but not "Bulky", then its category is "Heavy".

Note that the volume of the box is the product of its length, width and height.

 

Example 1:

Input: length = 1000, width = 35, height = 700, mass = 300
Output: "Heavy"
Explanation: 
None of the dimensions of the box is greater or equal to 104. 
Its volume = 24500000 <= 109. So it cannot be categorized as "Bulky".
However mass >= 100, so the box is "Heavy".
Since the box is not "Bulky" but "Heavy", we return "Heavy".

Example 2:

Input: length = 200, width = 50, height = 800, mass = 50
Output: "Neither"
Explanation: 
None of the dimensions of the box is greater or equal to 104.
Its volume = 8 * 106 <= 109. So it cannot be categorized as "Bulky".
Its mass is also less than 100, so it cannot be categorized as "Heavy" either. 
Since its neither of the two above categories, we return "Neither".

 

Constraints:

  • 1 <= length, width, height <= 105
  • 1 <= mass <= 103

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
// head

class Solution {
public:
    string categorizeBox(int l, int w, int h, int mass) {
        const int E2 = 1e2;
        const int E4 = 1e4;
        const int E9 = 1e9;

        ll v = 1ll * l * w * h;

        bool b = (l >= E4 || w >= E4 || h >= E4 || v >= E9);
        bool e = (mass >= E2);

        if (b && e) {
            return "Both";
        }

        if (!b && !e) {
            return "Neither";
        }

        if (b) {
            return "Bulky";
        }

        if (e) {
            return "Heavy";
        }

        return "";
    }
};

#ifdef LOCAL

int main() {
    return 0;
}

#endif

B

Statement

Metadata

给你一个整数数据流,请你实现一个数据结构,检查数据流中最后 k 个整数是否 等于 给定值 value 。

请你实现 DataStream 类:

  • DataStream(int value, int k) 用两个整数 value 和 k 初始化一个空的整数数据流。
  • boolean consec(int num) 将 num 添加到整数数据流。如果后 k 个整数都等于 value ,返回 true ,否则返回 false 。如果少于 k 个整数,条件不满足,所以也返回 false 。

 

示例 1:

输入:
["DataStream", "consec", "consec", "consec", "consec"]
[[4, 3], [4], [4], [4], [3]]
输出:
[null, false, false, true, false]
解释:
DataStream dataStream = new DataStream(4, 3); // value = 4, k = 3 
dataStream.consec(4); // 数据流中只有 1 个整数,所以返回 False 。
dataStream.consec(4); // 数据流中只有 2 个整数
                      // 由于 2 小于 k ,返回 False 。
dataStream.consec(4); // 数据流最后 3 个整数都等于 value, 所以返回 True 。
dataStream.consec(3); // 最后 k 个整数分别是 [4,4,3] 。
                      // 由于 3 不等于 value ,返回 False 。

 

提示:

  • 1 <= value, num <= 109
  • 1 <= k <= 105
  • 至多调用 consec 次数为 105 次。

Metadata

For a stream of integers, implement a data structure that checks if the last k integers parsed in the stream are equal to value.

Implement the DataStream class:

  • DataStream(int value, int k) Initializes the object with an empty integer stream and the two integers value and k.
  • boolean consec(int num) Adds num to the stream of integers. Returns true if the last k integers are equal to value, and false otherwise. If there are less than k integers, the condition does not hold true, so returns false.

 

Example 1:

Input
["DataStream", "consec", "consec", "consec", "consec"]
[[4, 3], [4], [4], [4], [3]]
Output
[null, false, false, true, false]
Explanation
DataStream dataStream = new DataStream(4, 3); //value = 4, k = 3 
dataStream.consec(4); // Only 1 integer is parsed, so returns False. 
dataStream.consec(4); // Only 2 integers are parsed.
                      // Since 2 is less than k, returns False. 
dataStream.consec(4); // The 3 integers parsed are all equal to value, so returns True. 
dataStream.consec(3); // The last k integers parsed in the stream are [4,4,3].
                      // Since 3 is not equal to value, it returns False.

 

Constraints:

  • 1 <= value, num <= 109
  • 1 <= k <= 105
  • At most 105 calls will be made to consec.

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
// head

class DataStream {
public:
    int value{0};
    int k{0};
    int has{0};
    queue<int> q;

    DataStream(int value, int k) {
        this->value = value;
        this->k = k;
        this->has = 0;
    }

    bool consec(int num) {
        if (num == value) {
            ++has;
        }

        q.push(num);
        while (q.size() > size_t(k)) {
            int x = q.front();
            q.pop();

            if (x == value) {
                --has;
            }
        }

        return has == k;
    }
};

/**
 * Your DataStream object will be instantiated and called as such:
 * DataStream* obj = new DataStream(value, k);
 * bool param_1 = obj->consec(num);
 */

#ifdef LOCAL

int main() {
    return 0;
}

#endif

C

Statement

Metadata

给你一个下标从 0 开始的整数数组 nums 。

三个下标 i ,j 和 k 的 有效值 定义为 ((nums[i] | nums[j]) & nums[k]) 。

一个数组的 xor 美丽值 是数组中所有满足 0 <= i, j, k < n  的三元组 (i, j, k) 的 有效值 的异或结果。

请你返回 nums 的 xor 美丽值。

注意:

  • val1 | val2 是 val1 和 val2 的按位或。
  • val1 & val2 是 val1 和 val2 的按位与。

 

示例 1:

输入:nums = [1,4]
输出:5
解释:
三元组和它们对应的有效值如下:
- (0,0,0) 有效值为 ((1 | 1) & 1) = 1
- (0,0,1) 有效值为 ((1 | 1) & 4) = 0
- (0,1,0) 有效值为 ((1 | 4) & 1) = 1
- (0,1,1) 有效值为 ((1 | 4) & 4) = 4
- (1,0,0) 有效值为 ((4 | 1) & 1) = 1
- (1,0,1) 有效值为 ((4 | 1) & 4) = 4
- (1,1,0) 有效值为 ((4 | 4) & 1) = 0
- (1,1,1) 有效值为 ((4 | 4) & 4) = 4 
数组的 xor 美丽值为所有有效值的按位异或 1 ^ 0 ^ 1 ^ 4 ^ 1 ^ 4 ^ 0 ^ 4 = 5 。

示例 2:

输入:nums = [15,45,20,2,34,35,5,44,32,30]
输出:34
解释:数组的 xor 美丽值为 34 。

 

提示:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109

Metadata

You are given a 0-indexed integer array nums.

The effective value of three indices i, j, and k is defined as ((nums[i] | nums[j]) & nums[k]).

The xor-beauty of the array is the XORing of the effective values of all the possible triplets of indices (i, j, k) where 0 <= i, j, k < n.

Return the xor-beauty of nums.

Note that:

  • val1 | val2 is bitwise OR of val1 and val2.
  • val1 & val2 is bitwise AND of val1 and val2.

 

Example 1:

Input: nums = [1,4]
Output: 5
Explanation: 
The triplets and their corresponding effective values are listed below:
- (0,0,0) with effective value ((1 | 1) & 1) = 1
- (0,0,1) with effective value ((1 | 1) & 4) = 0
- (0,1,0) with effective value ((1 | 4) & 1) = 1
- (0,1,1) with effective value ((1 | 4) & 4) = 4
- (1,0,0) with effective value ((4 | 1) & 1) = 1
- (1,0,1) with effective value ((4 | 1) & 4) = 4
- (1,1,0) with effective value ((4 | 4) & 1) = 0
- (1,1,1) with effective value ((4 | 4) & 4) = 4 
Xor-beauty of array will be bitwise XOR of all beauties = 1 ^ 0 ^ 1 ^ 4 ^ 1 ^ 4 ^ 0 ^ 4 = 5.

Example 2:

Input: nums = [15,45,20,2,34,35,5,44,32,30]
Output: 34
Explanation: The xor-beauty of the given array is 34.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109

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
// head

// 1 1 0 1

class Solution {
public:
    ll s(int x) {
        return 1ll * x * x;
    }

    int xorBeauty(vector<int> &nums) {
        int n = int(nums.size());
        auto f = vector<int>(50, 0);

        for (int x : nums) {
            for (int j = 0; j < 31; j++) {
                if ((x >> j) & 1) {
                    ++f[j];
                }
            }
        }

        int res = 0;
        for (const auto &x : nums) {
            int cur_res = 0;

            for (int j = 0; j < 31; j++) {
                int b = (x >> j) & 1;
                if (b) {
                    ll r = s(n) - s(n - f[j]);
                    if (r & 1) {
                        cur_res |= (1 << j);
                    }
                }
            }

            res ^= cur_res;
        }

        return res;
    }
};

#ifdef LOCAL

int main() {
    return 0;
}

#endif

D

Statement

Metadata

给你一个下标从 0 开始长度为 n 的整数数组 stations ,其中 stations[i] 表示第 i 座城市的供电站数目。

每个供电站可以在一定 范围 内给所有城市提供电力。换句话说,如果给定的范围是 r ,在城市 i 处的供电站可以给所有满足 |i - j| <= r 且 0 <= i, j <= n - 1 的城市 j 供电。

  • |x| 表示 x 的 绝对值 。比方说,|7 - 5| = 2 ,|3 - 10| = 7 。

一座城市的 电量 是所有能给它供电的供电站数目。

政府批准了可以额外建造 k 座供电站,你需要决定这些供电站分别应该建在哪里,这些供电站与已经存在的供电站有相同的供电范围。

给你两个整数 r 和 k ,如果以最优策略建造额外的发电站,返回所有城市中,最小供电站数目的最大值是多少。

k 座供电站可以建在多个城市。

 

示例 1:

输入:stations = [1,2,4,5,0], r = 1, k = 2
输出:5
解释:
最优方案之一是把 2 座供电站都建在城市 1 。
每座城市的供电站数目分别为 [1,4,4,5,0] 。
- 城市 0 的供电站数目为 1 + 4 = 5 。
- 城市 1 的供电站数目为 1 + 4 + 4 = 9 。
- 城市 2 的供电站数目为 4 + 4 + 5 = 13 。
- 城市 3 的供电站数目为 5 + 4 = 9 。
- 城市 4 的供电站数目为 5 + 0 = 5 。
供电站数目最少是 5 。
无法得到更优解,所以我们返回 5 。

示例 2:

输入:stations = [4,4,4,4], r = 0, k = 3
输出:4
解释:
无论如何安排,总有一座城市的供电站数目是 4 ,所以最优解是 4 。

 

提示:

  • n == stations.length
  • 1 <= n <= 105
  • 0 <= stations[i] <= 105
  • 0 <= r <= n - 1
  • 0 <= k <= 109

Metadata

You are given a 0-indexed integer array stations of length n, where stations[i] represents the number of power stations in the ith city.

Each power station can provide power to every city in a fixed range. In other words, if the range is denoted by r, then a power station at city i can provide power to all cities j such that |i - j| <= r and 0 <= i, j <= n - 1.

  • Note that |x| denotes absolute value. For example, |7 - 5| = 2 and |3 - 10| = 7.

The power of a city is the total number of power stations it is being provided power from.

The government has sanctioned building k more power stations, each of which can be built in any city, and have the same range as the pre-existing ones.

Given the two integers r and k, return the maximum possible minimum power of a city, if the additional power stations are built optimally.

Note that you can build the k power stations in multiple cities.

 

Example 1:

Input: stations = [1,2,4,5,0], r = 1, k = 2
Output: 5
Explanation: 
One of the optimal ways is to install both the power stations at city 1. 
So stations will become [1,4,4,5,0].
- City 0 is provided by 1 + 4 = 5 power stations.
- City 1 is provided by 1 + 4 + 4 = 9 power stations.
- City 2 is provided by 4 + 4 + 5 = 13 power stations.
- City 3 is provided by 5 + 4 = 9 power stations.
- City 4 is provided by 5 + 0 = 5 power stations.
So the minimum power of a city is 5.
Since it is not possible to obtain a larger power, we return 5.

Example 2:

Input: stations = [4,4,4,4], r = 0, k = 3
Output: 4
Explanation: 
It can be proved that we cannot make the minimum power of a city greater than 4.

 

Constraints:

  • n == stations.length
  • 1 <= n <= 105
  • 0 <= stations[i] <= 105
  • 0 <= r <= n - 1
  • 0 <= k <= 109

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
// head

const ll INF = 0x3f3f3f3f3f3f3f3f;

class Solution {
public:
    long long maxPower(vector<int> &sta, int r, int k) {
        int n = int(sta.size());

        auto need_ori = vector<ll>(n + 5, 0);
        for (int i = 0; i < n; i++) {
            int _l = max(0, i - r);
            int _r = min(n, i + r + 1);
            need_ori[_l] += sta[i];
            need_ori[_r] -= sta[i];
        }

        auto ok = [&](ll x) -> bool {
            ll cur = 0;
            auto need = need_ori;
            ll has = k;

            for (int i = 0; i < n; i++) {
                cur += need[i];

                if (cur >= x) {
                    continue;
                }

                ll diff = x - cur;
                if (has < diff) {
                    return false;
                }

                has -= diff;

                int pos = min(n, i + r + r + 1);
                need[pos] -= diff;

                cur += diff;
            }

            return true;
        };

        ll l = 0, rr = INF, res = -1;
        while (rr - l >= 0) {
            ll mid = (l + rr) >> 1;
            if (ok(mid)) {
                l = mid + 1;
                res = mid;
            } else {
                rr = mid - 1;
            }
        }

        return res;
    }
};

#ifdef LOCAL

int main() {
    return 0;
}

#endif

最后更新: October 11, 2023
回到页面顶部