Codeforces Round 958 (Div. 2 ABCDE题) 视频讲解

A. Split the Multiset

Problem Statement

A multiset is a set of numbers in which there can be equal elements, and the order of the numbers does not matter. For example, { 2 , 2 , 4 } \{2,2,4\} {2,2,4} is a multiset.

You have a multiset $S$. Initially, the multiset contains only one positive integer $n$. That is, S = { n } S=\{n\} S={n}. Additionally, there is a given positive integer $k$.

In one operation, you can select any positive integer $u$ in $S$ and remove one copy of $u$ from $S$. Then, insert no more than $k$ positive integers into $S$ so that the sum of all inserted integers is equal to $u$.

Find the minimum number of operations to make $S$ contain $n$ ones.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 1000$). Description of the test cases follows.

The only line of each testcase contains two integers $n,k$ ($1\le n\le 1000,2\le k\le 1000$).

Output

For each testcase, print one integer, which is the required answer.

Example

input
4
1 5
5 2
6 3
16 4

output
0
4
3
5

Note

For the first test case, initially S = { 1 } S=\{1\} S={1}, already satisfying the requirement. Therefore, we need zero operations.

For the second test case, initially S = { 5 } S=\{5\} S={5}. We can apply the following operations:

• Select $u=5$, remove $u$ from $S$, and insert $2,3$ into $S$. Now, S = { 2 , 3 } S=\{2,3\} S={2,3}.
• Select $u=2$, remove $u$ from $S$, and insert $1,1$ into $S$. Now, S = { 1 , 1 , 3 } S=\{1,1,3\} S={1,1,3}.
• Select $u=3$, remove $u$ from $S$, and insert $1,2$ into $S$. Now, S = { 1 , 1 , 1 , 2 } S=\{1,1,1,2\} S={1,1,1,2}.
• Select $u=2$, remove $u$ from $S$, and insert $1,1$ into $S$. Now, S = { 1 , 1 , 1 , 1 , 1 } S=\{1,1,1,1,1\} S={1,1,1,1,1}.

Using $4$ operations in total, we achieve the goal.

For the third test case, initially S = { 6 } S=\{6\} S={6}. We can apply the following operations:

• Select $u=6$, remove $u$ from $S$, and insert $1,2,3$ into $S$. Now, S = { 1 , 2 , 3 } S=\{1,2,3\} S={1,2,3}.
• Select $u=2$, remove $u$ from $S$, and insert $1,1$ into $S$. Now, S = { 1 , 1 , 1 , 3 } S=\{1,1,1,3\} S={1,1,1,3}.
• Select $u=3$, remove $u$ from $S$, and insert $1,1,1$ into $S$. Now, S = { 1 , 1 , 1 , 1 , 1 , 1 } S=\{1,1,1,1,1,1\} S={1,1,1,1,1,1}.

Using $3$ operations in total, we achieve the goal.

For the fourth test case, initially S = { 16 } S=\{16\} S={16}. We can apply the following operations:

• Select $u=16$, remove $u$ from $S$, and insert $4,4,4,4$ into $S$. Now, S = { 4 , 4 , 4 , 4 } S=\{4,4,4,4\} S={4,4,4,4}.
• Repeat for $4$ times: select $u=4$, remove $u$ from $S$, and insert $1,1,1,1$ into $S$.

Using $5$ operations in total, we achieve the goal.

Solution

具体见文后视频。

---

Code

#include <bits/stdc++.h>
 
void solve() {
    int n, k;
    std::cin >> n >> k;
    
    std::cout << (n + k - 3) / (k - 1) << "\n";
}
 
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

---

B. Make Majority

Problem Statement

You are given a sequence $[a_1,\dots ,a_n]$ where each element $a_i$ is either $0$ or $1$. You can apply several (possibly zero) operations to the sequence. In each operation, you select two integers $1\le l\le r\le |a|$ (where $|a|$ is the current length of $a$) and replace $[a_l,\dots ,a_r]$ with a single element $x$, where $x$ is the majority of $[a_l,\dots ,a_r]$.

Here, the majority of a sequence consisting of $0$ and $1$ is defined as follows: suppose there are $c_0$ zeros and $c_1$ ones in the sequence, respectively.

• If $c_0\ge c_1$, the majority is $0$.
• If $c_0<c_1$, the majority is $1$.

For example, suppose $a=[1,0,0,0,1,1]$. If we select $l=1,r=2$, the resulting sequence will be $[0,0,0,1,1]$. If we select $l=4,r=6$, the resulting sequence will be $[1,0,0,1]$.

Determine if you can make $a=[1]$ with a finite number of operations.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 4\cdot 10^4$). Description of the test cases follows.

The first line of each testcase contains one integer $n$ ($1\le n\le 2\cdot 10^5$).

The second line of each testcase contains a string consisting of $0$ and $1$, describing the sequence $a$.

It’s guaranteed that the sum of $n$ over all testcases does not exceed $2\cdot 10^5$.

Output

For each testcase, if it’s possible to make $a=[1]$, print YES. Otherwise, print NO. You can output the answer in any case (upper or lower). For example, the strings yEs, yes, Yes, and YES will be recognized as positive responses.

Example

input
5
1
0
1
1
2
01
9
100000001
9
000011000

output
No
Yes
No
Yes
No

Note

In the fourth testcase of the example, initially $a=[1,0,0,0,0,0,0,0,1]$. A valid sequence of operations is:

1. Select $l=2,r=8$ and apply the operation. $a$ becomes $[1,0,1]$.
2. Select $l=1,r=3$ and apply the operation. $a$ becomes $[1]$.

Solution

具体见文后视频。

---

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

void solve() {
	int n;
	string s;
	cin >> n >> s;
	int one = 0, zero = 0, len = 0;
	for (int i = 0; i < s.size(); i ++)
		if (s[i] == '0') len ++;
		else {
			if (len) zero ++;
			one ++, len = 0;
		}
	if (len) zero ++;

	if (one > zero) cout << "Yes" << endl;
	else cout << "No" << endl;
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

---

C. Increasing Sequence with Fixed OR

Problem Statement

You are given a positive integer $n$. Find the longest sequence of positive integers $a=[a_1,a_2,\dots ,a_k]$ that satisfies the following conditions, and print the sequence:

• $a_i\le n$ for all $1\le i\le k$.
• $a$ is strictly increasing. That is, $a_i>a_{i-1}$ for all $2\le i\le k$.
• $a_i|a_{i-1}=n$ for all $2\le i\le k$, where $|$ denotes the bitwise OR operation.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 1000$). Description of the test cases follows.

The only line of each test case contains one integer $n$ ($1\le n\le 10^{18}$).

It’s guaranteed that the sum of lengths of the longest valid sequences does not exceed $5\cdot 10^5$.

Output

For each testcase, print two lines. In the first line, print the length of your constructed sequence, $k$. In the second line, print $k$ positive integers, denoting the sequence. If there are multiple longest sequences, you can print any of them.

Example

input
4
1
3
14
23

output
1
1
3
1 2 3
4
4 10 12 14
5
7 18 21 22 23

Solution

具体见文后视频。

---

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

void solve() {
	int n;
	cin >> n;
	std::vector<int> pos;
	for (int i = 0; i < 62; i ++)
		if (n >> i & 1) pos.push_back(i);
	int m = pos.size();
	std::vector<int> way;
	for (int i = m - 1; i >= 0; i --) {
		int tmp = 0;
		for (int j = m - 1; j > i; j --)
			tmp |= (1ll << j);
		for (int j = i - 1, k = 1; j >= 0; j --)
			tmp |= (k << j), k ^= 1;
		if (tmp) way.push_back(tmp);
	}
	way.push_back((1ll << m) - 1);
	std::vector<int> res;
	for (auto v : way) {
		int tmp = 0;
		for (int i = 0; i < pos.size(); i ++)
			tmp += ((v >> i & 1) << pos[i]);
		res.push_back(tmp);
	}
	cout << res.size() << endl;
	for (auto v : res)
		cout << v << " ";
	cout << endl;
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

---

D. The Omnipotent Monster Killer

Problem Statement

You, the monster killer, want to kill a group of monsters. The monsters are on a tree with $n$ vertices. On vertex with number $i$ ($1\le i\le n$), there is a monster with $a_i$ attack points. You want to battle with monsters for $10^{100}$ rounds.

In each round, the following happens in order:

1. All living monsters attack you. Your health decreases by the sum of attack points of all living monsters.
2. You select some (possibly all or none) monsters and kill them. After being killed, the monster will not be able to do any attacks in the future.

There is a restriction: in one round, you cannot kill two monsters that are directly connected by an edge.

If you choose what monsters to attack optimally, what is the smallest health decrement you can have after all rounds?

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 10^4$). Description of the test cases follows.

The first line of each test case contains an integer $n$ ($1\le n\le 3\cdot 10^5$).

The second line of each test case contains $n$ integers $a_1,\dots ,a_n$ ($1\le a_i\le 10^{12}$).

The following $n-1$ lines each contain two integers $x,y$ ($1\le x,y\le n$), denoting an edge on the tree connecting vertex $x$ and $y$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3\cdot 10^5$.

Output

For each test case, print one integer: the minimum possible health decrement.

Example

input
3
1
1000000000000
5
47 15 32 29 23
1 2
1 3
2 4
2 5
7
8 10 2 3 5 7 4
1 2
1 4
3 2
5 3
6 2
7 5

output
1000000000000
193
57

Note

In the first test case, an optimal sequence of operations would be:

• In the first round: first, receive the attack from the monster on vertex $1$, so your health decreases by $10^{12}$. Then kill the monster on vertex $1$.
• In the second round to the $10^{100}$-th round: all monsters have been killed, so nothing happens.

The total health decrement is $10^{12}$.

In the second test case, an optimal sequence of operations would be:

• In the first round: first, receive the attack from the monster on vertex $1,2,3,4,5$, so your health decreases by $47+15+32+29+23=146$. Then kill the monsters on vertex $1,4,5$.
• In the second round: first, receive the attack from the monster on vertex $2,3$, so your health decreases by $15+32=47$. Then kill the monsters on vertex $2,3$.
• In the third round to the $10^{100}$-th round: all monsters have been killed, so nothing happens.

The total health decrement is $193$.

In the third test case, an optimal sequence of operations would be:

• In the first round: first, receive the attack from the monster on vertex $1,2,3,4,5,6,7$, so your health decreases by $8+10+2+3+5+7+4=39$. Then kill the monsters on vertex $1,3,6,7$.
• In the second round: first, receive the attack from the monster on vertex $2,4,5$, so your health decreases by $10+3+5=18$. Then kill the monsters on vertex $2,4,5$.
• In the third round to the $10^{100}$-th round: all monsters have been killed, so nothing happens.

The total health decrement is $57$.

Solution

具体见文后视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 3e5 + 10;

int n;
int a[N], dp[N][30];
std::vector<int> g[N];

void dfs(int u, int fa) {
	for (int i = 1; i <= 25; i ++) dp[u][i] = a[u] * i;
	for (auto v : g[u]) {
		if (v == fa) continue;
		dfs(v, u);
		for (int i = 1; i <= 25; i ++) {
			int mn = 9e18;
			for (int j = 1; j <= 25; j ++)
				if (i != j) mn = min(mn, dp[v][j]);
			dp[u][i] += mn;
		}
	}
}
void solve() {
	cin >> n;
	int tot = 0;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	for (int i = 1; i < n; i ++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v), g[v].push_back(u);
	}

	dfs(1, -1);
	int res = 9e18;
	for (int i = 1; i <= 25; i ++) res = min(res, dp[1][i]);
	cout << res << endl;
	for (int i = 1; i <= n; i ++) g[i].clear();
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

---

E. Range Minimum Sum

Problem Statement

For an array $[a_1,a_2,\dots ,a_n]$ of length $n$, define $f(a)$ as the sum of the minimum element over all subsegments. That is,

$$f(a)=\sum _{l=1}^n\sum _{r=l}^n\underset{l\le i\le r}{\min }{a}_i.$$

A permutation is a sequence of integers from $1$ to $n$ of length $n$ containing each number exactly once. You are given a permutation $[a_1,a_2,\dots ,a_n]$. For each $i$, solve the following problem independently:

• Erase $a_i$ from $a$, concatenating the remaining parts, resulting in $b=[a_1,a_2,\dots ,a_{i-1},a_{i+1},\dots ,a_n]$.
• Calculate $f(b)$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 10^5$). Description of the test cases follows.

The first line of each test case contains an integer $n$ ($1\le n\le 5\cdot 10^5$).

The second line of each test case contains $n$ distinct integers $a_1,\dots ,a_n$ ($1\le a_i\le n$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

Output

For each test case, print one line containing $n$ integers. The $i$-th integer should be the answer when erasing $a_i$.

Example

input
4
1
1
3
3 1 2
5
4 2 1 5 3
8
8 1 4 6 7 3 5 2

output
0
4 7 5
19 21 27 17 19
79 100 72 68 67 80 73 80

Note

In the second test case, $a=[3,1,2]$.

• When removing $a_1$, $b=[1,2]$. f ( b ) = 1 + 2 + min ⁡ { 1 , 2 } = 4 f(b)=1+2+\min\{1,2\}=4 f(b)=1+2+min{1,2}=4.
• When removing $a_2$, $b=[3,2]$. f ( b ) = 3 + 2 + min ⁡ { 3 , 2 } = 7 f(b)=3+2+\min\{3,2\}=7 f(b)=3+2+min{3,2}=7.
• When removing $a_3$, $b=[3,1]$. f ( b ) = 3 + 1 + min ⁡ { 3 , 1 } = 5 f(b)=3+1+\min\{3,1\}=5 f(b)=3+1+min{3,1}=5.

Solution

具体见文后视频。

---

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 5e5 + 10;

int n;
int a[N], l[N], r[N], dcr[N];
int f[N][22];

void build() {
	for (int j = 0; j <= log2(n); j ++)
		for (int i = 1; i + (1ll << j) - 1 <= n; i ++)
			if (!j) f[i][j] = a[i];
			else f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
int query(int l, int r) {
	int k = log2(r - l + 1);
	return min(f[l][k], f[r - (1ll << k) + 1][k]);
}

void solve() {
	cin >> n;
	for (int i = 1; i <= n; i ++) cin >> a[i];

	stack<int> stk;
	for (int i = 1; i <= n; i ++) {
		while (stk.size() && a[stk.top()] >= a[i]) stk.pop();
		if (stk.size()) l[i] = i - stk.top();
		else l[i] = i;
		stk.push(i);
	}
	while (stk.size()) stk.pop();
	for (int i = n; i >= 1; i --) {
		while (stk.size() && a[stk.top()] >= a[i]) stk.pop();
		if (stk.size()) r[i] = stk.top() - i;
		else r[i] = n - i + 1;
		stk.push(i);
	}
	build();
	int tot = 0;
	for (int i = 1; i <= n; i ++) tot += a[i] * l[i] * r[i];
	for (int i = 1; i <= n; i ++) dcr[i] = 0;
	for (int i = 1; i <= n; i ++) dcr[i - l[i] + 1] += r[i] * a[i], dcr[i] -= r[i] * a[i];
	for (int i = 1; i <= n; i ++) dcr[i + 1] += l[i] * a[i], dcr[i + r[i]] -= l[i] * a[i];
	for (int i = 1; i <= n; i ++) dcr[i] += dcr[i - 1];
	for (int i = 1; i <= n; i ++) {
		if (i - l[i] > 1) {
			int L = 1, R = i - l[i] - 1, res = i - l[i];
			while (L <= R) {
				int mid = L + R >> 1;
				if (query(mid, i - l[i] - 1) > a[i]) R = mid - 1, res = min(res, mid);
				else L = mid + 1;
			}
			dcr[i - l[i]] -= (i - l[i] - res) * a[i] * r[i];
		}
		if (i + r[i] < n) {
			int L = i + r[i] + 1, R = n, res = i + r[i];
			while (L <= R) {
				int mid = L + R >> 1;
				if (query(i + r[i] + 1, mid) > a[i]) L = mid + 1, res = max(res, mid);
				else R = mid - 1;
			}
			dcr[i + r[i]] -= (res - i - r[i]) * a[i] * l[i];
		}
	}

	for (int i = 1; i <= n; i ++)
		cout << tot - a[i] * l[i] * r[i] - dcr[i] << " ";
	cout << endl;
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

---

视频讲解

---

最后祝大家早日