Codeforces Round 968 (Div. 2 ABCD1D2题) 视频讲解

A. Turtle and Good Strings

Problem Statement

Turtle thinks a string $s$ is a good string if there exists a sequence of strings $t_1,t_2,\dots ,t_k$ ($k$ is an arbitrary integer) such that:

• $k\ge 2$.
• $s=t_1+t_2+\dots +t_k$, where $+$ represents the concatenation operation. For example, $\text{abc}=\text{a}+\text{bc}$.
• For all $1\le i<j\le k$, the first character of $t_i$ isn’t equal to the last character of $t_j$.

Turtle is given a string $s$ consisting of lowercase Latin letters. Please tell him whether the string $s$ is a good string!

Input

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

The first line of each test case contains a single integer $n$ ($2\le n\le 100$) — the length of the string.

The second line of each test case contains a string $s$ of length $n$, consisting of lowercase Latin letters.

Output

For each test case, output “YES” if the string $s$ is a good string, 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

Note

In the first test case, the sequence of strings $\text{a},\text{a}$ satisfies the condition $s=t_1+t_2+\dots +t_k$, but the first character of $t_1$ is equal to the last character of $t_2$. It can be seen that there doesn’t exist any sequence of strings which satisfies all of the conditions, so the answer is “NO”.

In the third test case, the sequence of strings $\text{ab},\text{cb}$ satisfies all of the conditions.

In the fourth test case, the sequence of strings $\text{abca},\text{bcab},\text{cabc}$ satisfies all of the conditions.

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;
	string s;
	cin >> s;

	if (s[0] != s.back()) 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;
}

B. Turtle and Piggy Are Playing a Game 2

Problem Statement

Turtle and Piggy are playing a game on a sequence. They are given a sequence $a_1,a_2,\dots ,a_n$, and Turtle goes first. Turtle and Piggy alternate in turns (so, Turtle does the first turn, Piggy does the second, Turtle does the third, etc.).

The game goes as follows:

• Let the current length of the sequence be $m$. If $m=1$, the game ends.
• If the game does not end and it’s Turtle’s turn, then Turtle must choose an integer $i$ such that $1\le i\le m-1$, set $a_i$ to $\max (a_i,a_{i+1})$, and remove $a_{i+1}$.
• If the game does not end and it’s Piggy’s turn, then Piggy must choose an integer $i$ such that $1\le i\le m-1$, set $a_i$ to $\min (a_i,a_{i+1})$, and remove $a_{i+1}$.

Turtle wants to maximize the value of $a_1$ in the end, while Piggy wants to minimize the value of $a_1$ in the end. Find the value of $a_1$ in the end if both players play optimally.

You can refer to notes for further clarification.

Input

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

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

The second line of each test case contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^5$) — the elements of the sequence $a$.

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

Output

For each test case, output a single integer — the value of $a_1$ in the end if both players play optimally.

Example

Note

In the first test case, initially $a=[1,2]$. Turtle can only choose $i=1$. Then he will set $a_1$ to $\max (a_1,a_2)=2$ and remove $a_2$. The sequence $a$ becomes $[2]$. Then the length of the sequence becomes $1$, and the game will end. The value of $a_1$ is $2$, so you should output $2$.

In the second test case, one of the possible game processes is as follows:

• Initially $a=[1,1,2]$.
• Turtle can choose $i=2$. Then he will set $a_2$ to $\max (a_2,a_3)=2$ and remove $a_3$. The sequence $a$ will become $[1,2]$.
• Piggy can choose $i=1$. Then he will set $a_1$ to $\min (a_1,a_2)=1$ and remove $a_2$. The sequence $a$ will become $[1]$.
• The length of the sequence becomes $1$, so the game will end. The value of $a_1$ will be $1$ in the end.

In the fourth test case, one of the possible game processes is as follows:

• Initially $a=[3,1,2,2,3]$.
• Turtle can choose $i=4$. Then he will set $a_4$ to $\max (a_4,a_5)=3$ and remove $a_5$. The sequence $a$ will become $[3,1,2,3]$.
• Piggy can choose $i=3$. Then he will set $a_3$ to $\min (a_3,a_4)=2$ and remove $a_4$. The sequence $a$ will become $[3,1,2]$.
• Turtle can choose $i=2$. Then he will set $a_2$ to $\max (a_2,a_3)=2$ and remove $a_3$. The sequence $a$ will become $[3,2]$.
• Piggy can choose $i=1$. Then he will set $a_1$ to $\min (a_1,a_2)=2$ and remove $a_2$. The sequence $a$ will become $[2]$.
• The length of the sequence becomes $1$, so the game will end. The value of $a_1$ will be $2$ in the end.

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> a(n);
	for (int i = 0; i < n; i ++)
		cin >> a[i];
	sort(a.begin(), a.end());

	cout << a[n / 2] << endl;
}

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

	int dt;
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

C. Turtle and Good Pairs

Problem Statement

Turtle gives you a string $s$, consisting of lowercase Latin letters.

Turtle considers a pair of integers $(i,j)$ ($1\le i<j\le n$) to be a pleasant pair if and only if there exists an integer $k$ such that $i\le k<j$ and both of the following two conditions hold:

• $s_k\ne s_{k+1}$;
• $s_k\ne s_i$ or $s_{k+1}\ne s_j$.

Besides, Turtle considers a pair of integers $(i,j)$ ($1\le i<j\le n$) to be a good pair if and only if $s_i=s_j$ or $(i,j)$ is a pleasant pair.

Turtle wants to reorder the string $s$ so that the number of good pairs is maximized. Please help him!

Input

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

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

The second line of each test case contains a string $s$ of length $n$, consisting of lowercase Latin letters.

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 the string $s$ after reordering so that the number of good pairs is maximized. If there are multiple answers, print any of them.

Example

Note

In the first test case, $(1,3)$ is a good pair in the reordered string. It can be seen that we can’t reorder the string so that the number of good pairs is greater than $1$. bac and cab can also be the answer.

In the second test case, $(1,2)$, $(1,4)$, $(1,5)$, $(2,4)$, $(2,5)$, $(3,5)$ are good pairs in the reordered string. efddd can also be the answer.

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 cnt[27] = {0};
	for (int i = 0; i < n; i ++) cnt[s[i] - 'a'] ++;
	for (int i = 0, j = 0; i < n; i ++, j = (j + 1) % 26) {
		while (!cnt[j]) j = (j + 1) % 26;
		cout << char(j + 'a'), cnt[j] --;
	}
	cout << endl;
}

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

	int dt;
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

D1. Turtle and a MEX Problem (Easy Version)

Problem Statement

The two versions are different problems. In this version of the problem, you can choose the same integer twice or more. You can make hacks only if both versions are solved.

One day, Turtle was playing with $n$ sequences. Let the length of the $i$-th sequence be $l_i$. Then the $i$-th sequence was $a_{i,1},a_{i,2},\dots ,a_{i,l_i}$.

Piggy gave Turtle a problem to solve when Turtle was playing. The statement of the problem was:

• There was a non-negative integer $x$ at first. Turtle would perform an arbitrary number (possibly zero) of operations on the integer.
• In each operation, Turtle could choose an integer $i$ such that $1\le i\le n$, and set $x$ to ${\text{mex}}^{†}(x,a_{i,1},a_{i,2},\dots ,a_{i,l_i})$.
• Turtle was asked to find the answer, which was the maximum value of $x$ after performing an arbitrary number of operations.

Turtle solved the above problem without difficulty. He defined $f(k)$ as the answer to the above problem when the initial value of $x$ was $k$.

Then Piggy gave Turtle a non-negative integer $m$ and asked Turtle to find the value of $\sum _{i=0}^{m}f(i)$ (i.e., the value of $f(0)+f(1)+\dots +f(m)$). Unfortunately, he couldn’t solve this problem. Please help him!

${}^{†}\text{mex}(c_1,c_2,\dots ,c_k)$ is defined as the smallest non-negative integer $x$ which does not occur in the sequence $c$. For example, $\text{mex}(2,2,0,3)$ is $1$, $\text{mex}(1,2)$ is $0$.

Input

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

The first line of each test case contains two integers $n,m$ ($1\le n\le 2\cdot 10^5,0\le m\le 10^9$).

Each of the following $n$ lines contains several integers. The first integer $l_i$ ($1\le l_i\le 2\cdot 10^5$) represents the length of the $i$-th sequence, and the following $l_i$ integers $a_{i,1},a_{i,2},\dots ,a_{i,l_i}$ ($0\le a_{i,j}\le 10^9$) represent the elements of the $i$-th sequence.

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

Output

For each test case, output a single integer — the value of $\sum _{i=0}^{m}f(i)$.

Example

Note

In the first test case, when $x$ is initially $2$, Turtle can choose $i=3$ and set $x$ to $\text{mex}(x,a_{3,1},a_{3,2},a_{3,3},a_{3,4})=\text{mex}(2,7,0,1,5)=3$. It can be proved that Turtle can’t make the value of $x$ greater than $3$, so $f(2)=3$.

It can be seen that $f(0)=3$, $f(1)=3$, $f(2)=3$, $f(3)=3$, and $f(4)=4$. So $f(0)+f(1)+f(2)+f(3)+f(4)=3+3+3+3+4=16$.

In the second test case, when $x$ is initially $1$, Turtle can choose $i=3$ and set $x$ to $\text{mex}(x,a_{3,1},a_{3,2},a_{3,3},a_{3,4},a_{3,5})=\text{mex}(1,1,3,0,3,3)=2$, and choose $i=3$ and set $x$ to $\text{mex}(x,a_{3,1},a_{3,2},a_{3,3},a_{3,4},a_{3,5})=\text{mex}(2,1,3,0,3,3)=4$. It can be proved that Turtle can’t make the value of $x$ greater than $4$, so $f(1)=4$.

It can be seen that $f(0)=4$, $f(1)=4$, $f(2)=4$, $f(3)=4$, and $f(4)=4$. So $f(0)+f(1)+f(2)+f(3)+f(4)=4+4+4+4+4=20$.

In the fourth test case, it can be seen that $f(0)=3$ and $f(1)=3$. So $f(0)+f(1)=3+3=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;

void solve() {
	int n, m;
	cin >> n >> m;
	std::vector<int> len(n), mx1(n), mx2(n);
	std::vector<vector<int>> a(n);
	int tot = 0;
	for (int i = 0; i < n; i ++) {
		cin >> len[i], a[i].resize(len[i]), tot += len[i];
		set<int> S;
		int flg = 0;
		for (int j = 0; j < len[i]; j ++)
			cin >> a[i][j], S.insert(a[i][j]);
		for (int j = 0; j <= len[i] + 5; j ++)
			if (!S.count(j)) {
				if (!flg) mx1[i] = j, flg = 1;
				else {
					mx2[i] = j;
					break;
				}
			}
	}
	std::vector<vector<int>> g(tot + 5);
	std::vector<int> dp(tot + 5, 0);
	for (int i = 0; i < n; i ++) g[mx1[i]].push_back(mx2[i]), dp[mx1[i]] = mx1[i];
	for (int i = tot + 4; i >= 0; i --)
		for (auto j : g[i]) dp[i] = max({dp[i], dp[j], j});

	int mx = 0, res = 0;
	for (int i = 0; i < n; i ++ ) mx = max(mx, dp[mx1[i]]);
	for (int i = 0; i <= min(tot + 4, m); i ++)
		res += max({mx, dp[i], i});
	cout << res + max(0ll, m - tot - 4) * (tot + 5 + m) / 2 << endl;
}

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

	int dt;
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

D2. Turtle and a MEX Problem (Hard Version)

Problem Statement

The two versions are different problems. In this version of the problem, you can’t choose the same integer twice or more. You can make hacks only if both versions are solved.

One day, Turtle was playing with $n$ sequences. Let the length of the $i$-th sequence be $l_i$. Then the $i$-th sequence was $a_{i,1},a_{i,2},\dots ,a_{i,l_i}$.

Piggy gave Turtle a problem to solve when Turtle was playing. The statement of the problem was:

• There was a non-negative integer $x$ at first. Turtle would perform an arbitrary number (possibly zero) of operations on the integer.
• In each operation, Turtle could choose an integer $i$ such that $1\le i\le n$ and $i$ wasn’t chosen before, and set $x$ to ${\text{mex}}^{†}(x,a_{i,1},a_{i,2},\dots ,a_{i,l_i})$.
• Turtle was asked to find the answer, which was the maximum value of $x$ after performing an arbitrary number of operations.

Turtle solved the above problem without difficulty. He defined $f(k)$ as the answer to the above problem when the initial value of $x$ was $k$.

Then Piggy gave Turtle a non-negative integer $m$ and asked Turtle to find the value of $\sum _{i=0}^{m}f(i)$ (i.e., the value of $f(0)+f(1)+\dots +f(m)$). Unfortunately, he couldn’t solve this problem. Please help him!

${}^{†}\text{mex}(c_1,c_2,\dots ,c_k)$ is defined as the smallest non-negative integer $x$ which does not occur in the sequence $c$. For example, $\text{mex}(2,2,0,3)$ is $1$, $\text{mex}(1,2)$ is $0$.

Input

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

The first line of each test case contains two integers $n,m$ ($1\le n\le 2\cdot 10^5,0\le m\le 10^9$).

Each of the following $n$ lines contains several integers. The first integer $l_i$ ($1\le l_i\le 2\cdot 10^5$) represents the length of the $i$-th sequence, and the following $l_i$ integers $a_{i,1},a_{i,2},\dots ,a_{i,l_i}$ ($0\le a_{i,j}\le 10^9$) represent the elements of the $i$-th sequence.

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

Output

For each test case, output a single integer — the value of $\sum _{i=0}^{m}f(i)$.

Example

Note

In the first test case, when $x$ is initially $2$, Turtle can choose $i=3$ and set $x$ to $\text{mex}(x,a_{3,1},a_{3,2},a_{3,3},a_{3,4})=\text{mex}(2,7,0,1,5)=3$. It can be proved that Turtle can’t make the value of $x$ greater than $3$, so $f(2)=3$.

It can be seen that $f(0)=3$, $f(1)=3$, $f(2)=3$, $f(3)=3$, and $f(4)=4$. So $f(0)+f(1)+f(2)+f(3)+f(4)=3+3+3+3+4=16$.

In the second test case, when $x$ is initially $1$, Turtle can choose $i=1$ and set $x$ to $\text{mex}(x,a_{1,1},a_{1,2},a_{1,3},a_{1,4},a_{1,5})=\text{mex}(1,0,2,0,4,11)=3$. It can be proved that Turtle can’t make the value of $x$ greater than $3$, so $f(1)=3$.

It can be seen that $f(0)=4$, $f(1)=3$, $f(2)=4$, $f(3)=3$, and $f(4)=4$. So $f(0)+f(1)+f(2)+f(3)+f(4)=4+3+4+3+4=18$.

In the fourth test case, it can be seen that $f(0)=3$ and $f(1)=1$. So $f(0)+f(1)=3+1=4$.

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, m;
	cin >> n >> m;
	std::vector<int> len(n), mx1(n), mx2(n);
	std::vector<vector<int>> a(n);
	int tot = 0;
	for (int i = 0; i < n; i ++) {
		cin >> len[i], a[i].resize(len[i]), tot += len[i];
		set<int> S;
		int flg = 0;
		for (int j = 0; j < len[i]; j ++)
			cin >> a[i][j], S.insert(a[i][j]);
		for (int j = 0; j <= len[i] + 5; j ++)
			if (!S.count(j)) {
				if (!flg) mx1[i] = j, flg = 1;
				else {
					mx2[i] = j;
					break;
				}
			}
	}
	std::vector<vector<int>> g(tot + 5);
	std::vector<int> dp(tot + 5, 0), f(n, 0), st(tot + 5, 0);
	vector<multiset<PII>> S(tot + 5);
	for (int i = 0; i < n; i ++) g[mx1[i]].push_back(mx2[i]);
	for (int i = tot + 4; i >= 0; i --)
		for (auto j : g[i]) dp[i] = max({dp[i], dp[j], j}), S[i].insert({max(dp[j], j), j});
	int mx = 0, cnt = 1;
	for (int i = 0; i < n; i ++) {
		S[mx1[i]].erase(S[mx1[i]].lower_bound(make_pair(max(dp[mx2[i]], mx2[i]), mx2[i])));
		mx = max({mx, mx1[i]});
		if (S[mx1[i]].size()) mx = max(mx, (*S[mx1[i]].rbegin()).fi);
		S[mx1[i]].insert({max(dp[mx2[i]], mx2[i]), mx2[i]});
	}

	int res = 0;
	for (int i = 0; i <= min(tot + 4, m); i ++)
		res += max({mx, i, dp[i]});
	cout << res + max(0ll, m - tot - 4) * (tot + 5 + m) / 2 << endl;
}

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

	int dt;
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

视频讲解

最后祝大家早日