# weekly-contest-279

## A

### Statement

1. 非递增 顺序排列 nums 奇数下标 上的所有值。
• 举个例子，如果排序前 nums = [4,1,2,3] ，对奇数下标的值排序后变为 [4,3,2,1] 。奇数下标 13 的值按照非递增顺序重排。
2. 非递减 顺序排列 nums 偶数下标 上的所有值。
• 举个例子，如果排序前 nums = [4,1,2,3] ，对偶数下标的值排序后变为 [2,1,4,3] 。偶数下标 02 的值按照非递减顺序重排。

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



输入：nums = [2,1]



• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

You are given a 0-indexed integer array nums. Rearrange the values of nums according to the following rules:

1. Sort the values at odd indices of nums in non-increasing order.
• For example, if nums = [4,1,2,3] before this step, it becomes [4,3,2,1] after. The values at odd indices 1 and 3 are sorted in non-increasing order.
2. Sort the values at even indices of nums in non-decreasing order.
• For example, if nums = [4,1,2,3] before this step, it becomes [2,1,4,3] after. The values at even indices 0 and 2 are sorted in non-decreasing order.

Return the array formed after rearranging the values of nums.

Example 1:

Input: nums = [4,1,2,3]
Output: [2,3,4,1]
Explanation:
First, we sort the values present at odd indices (1 and 3) in non-increasing order.
So, nums changes from [4,1,2,3] to [4,3,2,1].
Next, we sort the values present at even indices (0 and 2) in non-decreasing order.
So, nums changes from [4,1,2,3] to [2,3,4,1].
Thus, the array formed after rearranging the values is [2,3,4,1].


Example 2:

Input: nums = [2,1]
Output: [2,1]
Explanation:
Since there is exactly one odd index and one even index, no rearrangement of values takes place.
The resultant array formed is [2,1], which is the same as the initial array.


Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

### 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 lowbit(x) ((x) & (-(x)))
#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:
vector<int> sortEvenOdd(vector<int> &nums) {
int n = nums.size();
vector<int> a[2];
for (int i = 0; i < n; i++) {
a[i & 1].push_back(nums[i]);
}

sort(all(a[0]), greater<int>());
sort(all(a[1]));

vector<int> res;
for (int i = 0; i < n; i++) {
res.push_back(a[i & 1].back());
a[i & 1].pop_back();
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif


## B

### Statement

输入：num = 310



输入：num = -7605

• -1015 <= num <= 1015

You are given an integer num. Rearrange the digits of num such that its value is minimized and it does not contain any leading zeros.

Return the rearranged number with minimal value.

Note that the sign of the number does not change after rearranging the digits.

Example 1:

Input: num = 310
Output: 103
Explanation: The possible arrangements for the digits of 310 are 013, 031, 103, 130, 301, 310.
The arrangement with the smallest value that does not contain any leading zeros is 103.


Example 2:

Input: num = -7605
Output: -7650
Explanation: Some possible arrangements for the digits of -7605 are -7650, -6705, -5076, -0567.
The arrangement with the smallest value that does not contain any leading zeros is -7650.


Constraints:

• -1015 <= num <= 1015

### 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 lowbit(x) ((x) & (-(x)))
#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:
long long smallestNumber(long long num) {
if (num == 0) {
return 0;
}

int f = 0;
if (num < 0) {
f = 1;
num = -num;
}

string s = to_string(num);
int n = s.size();
sort(all(s));
if (f) {
reverse(all(s));
} else {
int zero = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '0') {
++zero;
} else {
break;
}
}

s = s.substr(zero, n - zero);
reverse(all(s));

char t = s.back();
s.pop_back();

s += string(zero, '0');
s += string(1, t);
reverse(all(s));
}

ll res = 0;
for (auto &c : s) {
res = res * 10 + (c - '0');
}

return res * (f ? -1 : 1);
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif


## C

### Statement

• Difficulty: Medium
• Tag: 设计 数组 哈希表

• Bitset(int size)size 个位初始化 Bitset ，所有位都是 0
• void fix(int idx) 将下标为 idx 的位上的值更新为 1 。如果值已经是 1 ，则不会发生任何改变。
• void unfix(int idx) 将下标为 idx 的位上的值更新为 0 。如果值已经是 0 ，则不会发生任何改变。
• void flip() 翻转 Bitset 中每一位上的值。换句话说，所有值为 0 的位将会变成 1 ，反之亦然。
• boolean all() 检查 Bitset 中 每一位 的值是否都是 1 。如果满足此条件，返回 true ；否则，返回 false
• boolean one() 检查 Bitset 中 是否 至少一位 的值是 1 。如果满足此条件，返回 true ；否则，返回 false
• int count() 返回 Bitset 中值为 1 的位的 总数
• String toString() 返回 Bitset 的当前组成情况。注意，在结果字符串中，第 i 个下标处的字符应该与 Bitset 中的第 i 位一致。

输入
["Bitset", "fix", "fix", "flip", "all", "unfix", "flip", "one", "unfix", "count", "toString"]
[[5], [3], [1], [], [], [0], [], [], [0], [], []]

[null, null, null, null, false, null, null, true, null, 2, "01010"]

Bitset bs = new Bitset(5); // bitset = "00000".
bs.fix(3);     // 将 idx = 3 处的值更新为 1 ，此时 bitset = "00010" 。
bs.fix(1);     // 将 idx = 1 处的值更新为 1 ，此时 bitset = "01010" 。
bs.flip();     // 翻转每一位上的值，此时 bitset = "10101" 。
bs.all();      // 返回 False ，bitset 中的值不全为 1 。
bs.unfix(0);   // 将 idx = 0 处的值更新为 0 ，此时 bitset = "00101" 。
bs.flip();     // 翻转每一位上的值，此时 bitset = "11010" 。
bs.one();      // 返回 True ，至少存在一位的值为 1 。
bs.unfix(0);   // 将 idx = 0 处的值更新为 0 ，此时 bitset = "01010" 。
bs.count();    // 返回 2 ，当前有 2 位的值为 1 。
bs.toString(); // 返回 "01010" ，即 bitset 的当前组成情况。


• 1 <= size <= 105
• 0 <= idx <= size - 1
• 至多调用 fixunfixflipallonecounttoString 方法 总共 105
• 至少调用 allonecounttoString 方法一次
• 至多调用 toString 方法 5

• Difficulty: Medium
• Tag: Design Array Hash Table

A Bitset is a data structure that compactly stores bits.

Implement the Bitset class:

• Bitset(int size) Initializes the Bitset with size bits, all of which are 0.
• void fix(int idx) Updates the value of the bit at the index idx to 1. If the value was already 1, no change occurs.
• void unfix(int idx) Updates the value of the bit at the index idx to 0. If the value was already 0, no change occurs.
• void flip() Flips the values of each bit in the Bitset. In other words, all bits with value 0 will now have value 1 and vice versa.
• boolean all() Checks if the value of each bit in the Bitset is 1. Returns true if it satisfies the condition, false otherwise.
• boolean one() Checks if there is at least one bit in the Bitset with value 1. Returns true if it satisfies the condition, false otherwise.
• int count() Returns the total number of bits in the Bitset which have value 1.
• String toString() Returns the current composition of the Bitset. Note that in the resultant string, the character at the ith index should coincide with the value at the ith bit of the Bitset.

Example 1:

Input
["Bitset", "fix", "fix", "flip", "all", "unfix", "flip", "one", "unfix", "count", "toString"]
[[5], [3], [1], [], [], [0], [], [], [0], [], []]
Output
[null, null, null, null, false, null, null, true, null, 2, "01010"]
Explanation
Bitset bs = new Bitset(5); // bitset = "00000".
bs.fix(3);     // the value at idx = 3 is updated to 1, so bitset = "00010".
bs.fix(1);     // the value at idx = 1 is updated to 1, so bitset = "01010".
bs.flip();     // the value of each bit is flipped, so bitset = "10101".
bs.all();      // return False, as not all values of the bitset are 1.
bs.unfix(0);   // the value at idx = 0 is updated to 0, so bitset = "00101".
bs.flip();     // the value of each bit is flipped, so bitset = "11010".
bs.one();      // return True, as there is at least 1 index with value 1.
bs.unfix(0);   // the value at idx = 0 is updated to 0, so bitset = "01010".
bs.count();    // return 2, as there are 2 bits with value 1.
bs.toString(); // return "01010", which is the composition of bitset.


Constraints:

• 1 <= size <= 105
• 0 <= idx <= size - 1
• At most 105 calls will be made in total to fix, unfix, flip, all, one, count, and toString.
• At least one call will be made to all, one, count, or toString.
• At most 5 calls will be made to toString.

### 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 rall rbegin(a), rend(a)
#define lowbit(x) ((x) & (-(x)))
#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 Bitset {
public:
vector<bool> bit;
int f;
int cnt[2];
int n;

Bitset(int size) {
bit = vector<bool>(size, 0);
cnt[0] = size;
cnt[1] = 0;
n = size;
f = 0;
}

void fix(int idx) {
--cnt[bit[idx]];
bit[idx] = f ^ 1;
++cnt[bit[idx]];
}

void unfix(int idx) {
--cnt[bit[idx]];
bit[idx] = f;
++cnt[bit[idx]];
}

void flip() {
f ^= 1;
}

bool all() {
return cnt[f ^ 1] == n;
}

bool one() {
return bool(cnt[f ^ 1] > 0);
}

int count() {
return cnt[f ^ 1];
}

string toString() {
string res = "";
for (int i = 0; i < n; i++) {
res += (bit[i] ^ f) + '0';
}

return res;
}
};

/**
* Your Bitset object will be instantiated and called as such:
* Bitset* obj = new Bitset(size);
* obj->fix(idx);
* obj->unfix(idx);
* obj->flip();
* bool param_4 = obj->all();
* bool param_5 = obj->one();
* int param_6 = obj->count();
* string param_7 = obj->toString();
*/

#ifdef LOCAL

int main() {
return 0;
}

#endif


## D

### Statement

1. 从列车 端移除一节车厢（即移除 s[0]），用去 1 单位时间。
2. 从列车 端移除一节车厢（即移除 s[s.length - 1]），用去 1 单位时间。
3. 从列车车厢序列的 任意位置 移除一节车厢，用去 2 单位时间。

输入：s = "1100101"

- 从左端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
- 从右端移除一节车厢 1 次。所用时间是 1 。
- 移除序列中间位置载有违禁货物的车厢。所用时间是 2 。

- 从左端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
- 从右端移除一节车厢 3 次。所用时间是 3 * 1 = 3 。

5 是移除所有载有违禁货物的车厢所需要的最少单位时间数。

输入：s = "0010"

- 从左端移除一节车厢 3 次。所用时间是 3 * 1 = 3 。

- 移除序列中间位置载有违禁货物的车厢。所用时间是 2 。

- 从右端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。

2 是移除所有载有违禁货物的车厢所需要的最少单位时间数。

• 1 <= s.length <= 2 * 105
• s[i]'0''1'

You are given a 0-indexed binary string s which represents a sequence of train cars. s[i] = '0' denotes that the ith car does not contain illegal goods and s[i] = '1' denotes that the ith car does contain illegal goods.

As the train conductor, you would like to get rid of all the cars containing illegal goods. You can do any of the following three operations any number of times:

1. Remove a train car from the left end (i.e., remove s[0]) which takes 1 unit of time.
2. Remove a train car from the right end (i.e., remove s[s.length - 1]) which takes 1 unit of time.
3. Remove a train car from anywhere in the sequence which takes 2 units of time.

Return the minimum time to remove all the cars containing illegal goods.

Note that an empty sequence of cars is considered to have no cars containing illegal goods.

Example 1:

Input: s = "1100101"
Output: 5
Explanation:
One way to remove all the cars containing illegal goods from the sequence is to
- remove a car from the left end 2 times. Time taken is 2 * 1 = 2.
- remove a car from the right end. Time taken is 1.
- remove the car containing illegal goods found in the middle. Time taken is 2.
This obtains a total time of 2 + 1 + 2 = 5.
An alternative way is to
- remove a car from the left end 2 times. Time taken is 2 * 1 = 2.
- remove a car from the right end 3 times. Time taken is 3 * 1 = 3.
This also obtains a total time of 2 + 3 = 5.
5 is the minimum time taken to remove all the cars containing illegal goods.
There are no other ways to remove them with less time.


Example 2:

Input: s = "0010"
Output: 2
Explanation:
One way to remove all the cars containing illegal goods from the sequence is to
- remove a car from the left end 3 times. Time taken is 3 * 1 = 3.
This obtains a total time of 3.
Another way to remove all the cars containing illegal goods from the sequence is to
- remove the car containing illegal goods found in the middle. Time taken is 2.
This obtains a total time of 2.
Another way to remove all the cars containing illegal goods from the sequence is to
- remove a car from the right end 2 times. Time taken is 2 * 1 = 2.
This obtains a total time of 2.
2 is the minimum time taken to remove all the cars containing illegal goods.
There are no other ways to remove them with less time.

Constraints:

• 1 <= s.length <= 2 * 105
• s[i] is either '0' or '1'.

### Tutorial

• 考虑最优情况下应该是：
• 最左边移除连续一段车厢，长度为 , 用去 单位时间。
• 最右边移除连续一段车厢，长度为 , 用去 单位时间。
• 然后移除掉中间那部分不连续的含有违禁货物的车厢，假设数量为 ，用去 单位时间。

• 枚举 ，然后维护出合法的并且最小的
• 或者枚举 ，然后维护出合法的并且最小的
• 注意其实不用维护一下 数组，只需要遍历过程中维护一个前缀和变量即可，可以做到空间复杂度

### 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 lowbit(x) ((x) & (-(x)))
#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

const int INF = 0x3f3f3f3f;

class Solution {
public:
int minimumTime(string &s) {
int n = s.size();
int res = n;

int pre = 0;
int Min = 0;

for (int i = 1; i <= n; i++) {
if (s[i - 1] == '1') {
pre += 2;
}

chmin(Min, i - pre);
chmin(res, Min + pre + n - i);
}

return res;
}
};

#ifdef LOCAL

int main() {
auto s = new Solution();

{
string t = "1100101";
auto ans = s->minimumTime(t);
assert_eq(ans, 5);
}

{
string t = "0010";
auto ans = s->minimumTime(t);
assert_eq(ans, 2);
}

{
string t = "00000010000000";
auto ans = s->minimumTime(t);
assert_eq(ans, 2);
}

return 0;
}

#endif