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

A. Card Exchange

Problem Statement

You have a hand of $n$ cards, where each card has a number written on it, and a fixed integer $k$. You can perform the following operation any number of times:

• Choose any $k$ cards from your hand that all have the same number.
• Exchange these cards for $k-1$ cards, each of which can have any number you choose (including the number written on the cards you just exchanged).

Here is one possible sequence of operations for the first example case, which has $k=3$:

What is the minimum number of cards you can have in your hand at the end of this process?

Input

Input

The first line of the input contains a single integer $t$ ($1\le t\le 500$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1\le n\le 100$, $2\le k\le 100$) — the number of cards you have, and the number of cards you exchange during each operation, respectively.

The next line of each test case contains $n$ integers $c_1,c_2,\dots c_n$ ($1\le c_i\le 100$) — the numbers written on your cards.

Output

For each test case, output a single integer — the minimum number of cards you can have left in your hand after any number of operations.

Example

Example

Note

The first example case corresponds to the picture above. The sequence of operations displayed there is optimal, so the answer is $2$.

In the second example case, no operations can be performed, so the answer is $1$.

In the fourth example case, you can repeatedly select $4$ cards numbered with $1$ and replace them with $3$ cards numbered with $1$, until there are $3$ cards left.

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 = 1e2 + 10;

int cnt[N];

void solve() {
	memset(cnt, 0, sizeof cnt);
	int n, k;
	cin >> n >> k;

	std::vector<int> a(n + 1);
	int mx = 0;
	for (int i = 1; i <= n; i ++)
		cin >> a[i], cnt[a[i]] ++, mx = max(mx, cnt[a[i]]);

	if (mx < k) {
		cout << n << endl;
	} else {
		cout << k - 1 << endl;
	}
}

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

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

B. Rectangle Filling

Problem Statement

There is an $n\times m$ grid of white and black squares. In one operation, you can select any two squares of the same color, and color all squares in the subrectangle between them that color.

Formally, if you select positions $(x_1,y_1)$ and $(x_2,y_2)$, both of which are currently the same color $c$, set the color of all $(x,y)$ where $\min (x_1,x_2)\le x\le \max (x_1,x_2)$ and $\min (y_1,y_2)\le y\le \max (y_1,y_2)$ to $c$.

This diagram shows a sequence of two possible operations on a grid:

Is it possible for all squares in the grid to be the same color, after performing any number of operations (possibly zero)?

Input

The first line of the input contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1\le n,m\le 500$) — the number of rows and columns in the grid, respectively.

Each of the next $n$ lines contains $m$ characters ‘W’ and ‘B’ — the initial colors of the squares of the grid.

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

Output

For each test case, print “YES” if it is possible to make all squares in the grid the same color, and “NO” otherwise.

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

Example

Note

In the first example, it is impossible to ever change the color of any square with an operation, so we output NO.

The second example is the case pictured above. As shown in that diagram, it is possible for all squares to be white after two operations, so we output YES.

In the third and fourth examples, all squares are already the same color, so we output YES.

In the fifth example we can do everything in two operations. First, select positions $(2,1)$ and $(1,4)$ and color all squares with $1\le x\le 2$ and $1\le y\le 4$ to white. Then, select positions $(2,1)$ and $(3,4)$ and color all squares with $2\le x\le 3$ and $1\le y\le 4$ to white. After these two operations all squares are white.

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 = 5e2 + 10;

int n, m;
int g[N][N], s[N][N];

int sum(int x1, int y1, int x2, int y2) {
	return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
}

void solve() {
	cin >> n >> m;

	char x;
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++) {
			cin >> x;
			g[i][j] = (x == 'B');
		}
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + g[i][j];

	int flg = 1;
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			if (!g[i][j] && ((sum(1, 1, i, j) && sum(i, j, n, m)) || (sum(i, 1, n, j) && sum(1, j, i, m))))
				continue;
			else if (!g[i][j]) {
				flg = 0;
				break;
			}
	if (flg) {
		cout << "YES" << endl;
		return;
	}
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + (!g[i][j]);

	flg = 1;
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			if (g[i][j] && ((sum(1, 1, i, j) && sum(i, j, n, m)) || (sum(i, 1, n, j) && sum(1, j, i, m))))
				continue;
			else if (g[i][j]) {
				flg = 0;
				break;
			}
	if (flg) {
		cout << "YES" << endl;
		return;
	}
	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. Everything Nim

Problem Statement

Alice and Bob are playing a game on $n$ piles of stones. On each player’s turn, they select a positive integer $k$ that is at most the size of the smallest nonempty pile and remove $k$ stones from each nonempty pile at once. The first player who is unable to make a move (because all piles are empty) loses.

Given that Alice goes first, who will win the game if both players play optimally?

Input

The first line of the input contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1\le n\le 2\cdot 10^5$) — the number of piles in the game.

The next line of each test case contains $n$ integers $a_1,a_2,\dots a_n$ ($1\le a_i\le 10^9$), where $a_i$ is the initial number of stones in the $i$-th pile.

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

Output

For each test case, print a single line with the name of the winner, assuming both players play optimally. If Alice wins, print “Alice”, otherwise print “Bob” (without quotes).

Example

Note

In the first test case, Alice can win by choosing $k=3$ on her first turn, which will empty all of the piles at once.

In the second test case, Alice must choose $k=1$ on her first turn since there is a pile of size $1$, so Bob can win on the next turn by choosing $k=6$.

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 = 2e5 + 10;

int n;
int a[N];

void solve() {
	cin >> n;

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

	sort(a + 1, a + 1 + n);
	n = unique(a + 1, a + 1 + n) - a - 1;

	int cnt = 0;
	for (int i = 1; i <= n; i ++)
		if (a[i] == a[i - 1] + 1)
			cnt ++;
		else
			break;

	if (n - cnt == 0) {
		if (n & 1) cout << "Alice" << endl;
		else cout << "Bob" << endl;
	}
	else if (cnt & 1) {
		cout << "Bob" << endl;
	} else {
		cout << "Alice" << endl;
	}
}

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

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

D. Missing Subsequence Sum

Problem Statement

You are given two integers $n$ and $k$. Find a sequence $a$ of non-negative integers of size at most $25$ such that the following conditions hold.

• There is no subsequence of $a$ with a sum of $k$.
• For all $1\le v\le n$ where $v\ne k$, there is a subsequence of $a$ with a sum of $v$.

A sequence $b$ is a subsequence of $a$ if $b$ can be obtained from $a$ by the deletion of several (possibly, zero or all) elements, without changing the order of the remaining elements. For example, $[5,2,3]$ is a subsequence of $[1,5,7,8,2,4,3]$.

It can be shown that under the given constraints, a solution always exists.

Input

The first line of the input contains a single integer $t$ ($1\le t\le 1000$) — the number of test cases. The description of the test cases follows.

Each test case consists of a single line containing two integers $n$ and $k$ ($2\le n\le 10^6$, $1\le k\le n$) — the parameters described above.

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

Output

The first line of output for each test case should contain a single integer $m$ ($1\le m\le 25$) — the size of your chosen sequence.

The second line of output for each test case should contain $m$ integers $a_i$ ($0\le a_i\le 10^9$) — the elements of your chosen sequence.

If there are multiple solutions, print any.

Example

Example

Note

In the first example, we just need a subsequence that adds up to $1$, but not one that adds up to $2$. So the array $a=[1]$ suffices.

In the second example, all elements are greater than $k=1$, so no subsequence adds up to $1$. Every other integer between $1$ and $n$ is present in the array, so there is a subsequence of size $1$ adding up to each of those numbers.

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 = 1e6 + 10;

int n, k;
int f[N];

void solve() {
	cin >> n >> k;

	f[0] = 1;
	std::vector<int> res;
	int i;
	for (i = 1; i * 2 - 1 < k; i *= 2) {
		res.emplace_back(i);
		for (int j = n; j >= i; j --)
			f[j] |= f[j - i];
	}
	if (k - i > 0) {
		res.emplace_back(k - i);
		for (int j = n; j >= k - i; j --)
			f[j] |= f[j - (k - i)];
	}

	for (i = k + 1; i <= n; i ++)
		if (!f[i]) {
			res.emplace_back(i);
			for (int j = n; j >= i; j --)
				f[j] |= f[j - i];
		}

	cout << res.size() << endl;
	for (auto v : res)
		cout << v << " ";
	cout << endl;
	for (int i = 0; i <= n; i ++)
		f[i] = 0;
}

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

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

E. Folding Strip

Problem Statement

You have a strip of paper with a binary string $s$ of length $n$. You can fold the paper in between any pair of adjacent digits.

A set of folds is considered valid if after the folds, all characters that are on top of or below each other match. Note that all folds are made at the same time, so the characters don’t have to match in between folds.

For example, these are valid foldings of $s=110110110011$ and $s=01110$:

The length of the folded strip is the length seen from above after all folds are made. So for the two above examples, after the folds shown above, the lengths would be $7$ and $3$, respectively.

Notice that for the above folding of $s=01110$, if we made either of the two folds on their own, that would not be a valid folding. However, because we don’t check for validity until all folds are made, this folding is valid.

After performing a set of valid folds, what is the minimum length strip you can form?

Input

The first line of the input contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1\le n\le 2\cdot 10^5$) — the size of the strip.

The second line of each test case contains a string $s$ of $n$ characters ‘0’ and ‘1’ — a description of the digits on the strip.

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

Output

For each test case, output a single integer — the minimum possible length of the strip after a valid folding.

Example

Note

For the first example case, one optimal folding is to fold the strip in the middle, which produces a strip of length 3.

The third and fourth example cases correspond to the images above. Note that the folding shown above for $s=110110110011$ is not of minimal length.

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, s = ' ' + s;

	int mn = 0, mx = 0, cur = 0;
	for (int i = 1; i <= n; i ++) {
		if ((cur & 1) == (s[i] == '1'))
			cur ++;
		else
			cur --;
		mn = min(mn, cur), mx = max(mx, cur);
	}

	cout << mx - mn << endl;
}

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

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

视频讲解

最后祝大家早日