算法练习专栏——Codeforces——Codeforces Round 923 (Div. 3)

Codeforces Round 923 (Div. 3)

A. Make it White(模拟)

Problem - A - Codeforces

You have a horizontal strip of $n$ cells. Each cell is either white or black.

You can choose a continuous segment of cells once and paint them all white. After this action, all the black cells in this segment will become white, and the white ones will remain white.

What is the minimum length of the segment that needs to be painted white in order for all $n$ cells to become white?

Input

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

The first line of each test case contains a single integer $n$ ($1 \le n \le 10$) — the length of the strip.

The second line of each test case contains a string $s$, consisting of $n$ characters, each of which is either ‘W’ or ‘B’. The symbol ‘W’ denotes a white cell, and ‘B’ — a black one. It is guaranteed that at least one cell of the given strip is black.

Output

For each test case, output a single number — the minimum length of a continuous segment of cells that needs to be painted white in order for the entire strip to become white.

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
8
6
WBBWBW
1
B
2
WB
3
BBW
4
BWWB
6
BWBWWB
6
WWBBWB
9
WBWBWWWBW

output

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

Note

In the first test case of the example for the strip “WBBWBW”, the minimum length of the segment to be repainted white is $4$. It is necessary to repaint to white the segment from the $2$-nd to the $5$-th cell (the cells are numbered from $1$ from left to right).

翻译

您有一条水平的 $n$单元格带。每个单元格要么是白色，要么是黑色。

您可以选择一个 连续 单元格段，然后将它们全部涂成白色。执行此操作后，此段中的所有黑色单元格将变为白色，而白色单元格将保持白色。

为了让所有 $n$单元格都变成白色，需要涂成白色的段的最小长度是多少？

输入

输入的第一行包含一个整数 $t$( $1 \le t \le 10^4$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $n$( $1 \le n \le 10$) — 条纹的长度。

每个测试用例的第二行包含一个字符串 $s$，由 $n$个字符组成，每个字符都是“W”或“B”。符号“W”表示白色单元格，“B”表示黑色单元格。保证给定条纹中至少有一个单元格是黑色的。

输出

对于每个测试用例，输出一个数字——为了让整个条带变成白色，需要涂成白色的连续单元格段的最小长度。

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
8
6
WBBWBW
1
B
2
WB
3
BBW
4
BWWB
6
BWBWWB
6
WWBBWB
9
WBWBWWWBW

output

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

注意

在“WBBWBW”条带示例的第一个测试案例中，需要重新绘制成白色的线段的最小长度为 $4$。需要将第 $2$个单元格到第 $5$个单元格的线段重新绘制成白色(单元格从左到右编号为 $1$)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>


using namespace std;
const int N = 2e5 + 10;
char a[N];


void solve(){
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	int l = 1, r = n;
	while (l <= n) {
		if (a[l] == 'B') break;
		else l++;
	}
	while (r >= 1) {
		if (a[r] == 'B') break;
		else r--;
	}
	cout << r - l + 1 << '\n';
	
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}

	return 0;
}

B. Following the String(模拟)

Problem - B - Codeforces

Polycarp lost the string $s$ of length $n$ consisting of lowercase Latin letters, but he still has its trace.

The trace of the string $s$ is an array $a$ of $n$ integers, where $a_i$ is the number of such indices $j$ ($j \lt i$) that $s_i=s_j$. For example, the trace of the string abracadabra is the array [$0, 0, 0, 1, 0, 2, 0, 3, 1, 1, 4$].

Given a trace of a string, find any string $s$ from which it could have been obtained. The string $s$ should consist only of lowercase Latin letters a-z.

Input

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

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

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \lt n$) — the trace of the string. It is guaranteed that for the given trace, there exists a suitable string $s$.

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

输出

对于每个测试用例，输出与给定轨迹相对应的字符串 $s$。如果有多个这样的字符串 $s$，则输出其中任何一个。

字符串 $s$应由小写拉丁字母 a-z 组成。

保证对于每个测试用例，都存在一个有效答案。

Example

input

1
2
3
4
5
6
7
8
9
10
11
5
11
0 0 0 1 0 2 0 3 1 1 4
10
0 0 0 0 0 1 0 1 1 0
1
0
8
0 1 2 3 4 5 6 7
8
0 0 0 0 0 0 0 0

output

1
2
3
4
5
abracadabra
codeforces
a
aaaaaaaa
dijkstra

Polycarp 丢失了长度为 $n$ 且由小写拉丁字母组成的字符串 $s$ ，但他仍然保留了它的踪迹。

字符串 $s$ 的踪迹是一个由 $n$ 个整数组成的数组 $a$ ，其中 $a_i$ 是这样的索引 $j$ ( $j \lt i$ ) 的数量，即 $s_i=s_j$ 。例如，字符串 abracadabra 的踪迹是数组 [ $0, 0, 0, 1, 0, 2, 0, 3, 1, 1, 4$ ]。

给定一个字符串的踪迹，找到可以从中获得该踪迹的任何字符串 $s$ 。字符串 $s$ 应该只由小写拉丁字母 a-z 组成。

输入

输入的第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ( $1 \le n \le 2 \cdot 10^5$ ) — 丢失字符串的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ( $0 \le a_i \lt n$ ) — 字符串的踪迹。保证对于给定的踪迹，存在一个合适的字符串 $s$ 。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$ 。

输出

对于每个测试用例，输出与给定轨迹相对应的字符串 $s$。如果有多个这样的字符串 $s$，则输出其中任何一个。

字符串 $s$应由小写拉丁字母 a-z 组成。

保证对于每个测试用例，都存在一个有效答案。

Example

input

1
2
3
4
5
6
7
8
9
10
11
5
11
0 0 0 1 0 2 0 3 1 1 4
10
0 0 0 0 0 1 0 1 1 0
1
0
8
0 1 2 3 4 5 6 7
8
0 0 0 0 0 0 0 0

output

1
2
3
4
5
abracadabra
codeforces
a
aaaaaaaa
dijkstra

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>


using namespace std;
const int N = 2e5 + 10;
int a[N];
int cnt[30];

void solve(){
	memset(cnt, 0, sizeof cnt);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) {
		char c;
		if (a[i] == 0) {
			for (int j = 0; j < 26; j++) {
				if (cnt[j] == 0) {
					c = 'a' + j;
					cnt[j]++;
					break;
				}
			}
		} else {
			for (int j = 0; j < 26; j++) {
				if (cnt[j] == a[i]) {
					c = 'a' + j;
					cnt[j]++;
					break;
				}
			}
		}
		cout << c;
	}
	
	cout << '\n';
	
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}

	return 0;
}

C. Choose the Different Ones!

Given an array $a$ of $n$ integers, an array $b$ of $m$ integers, and an even number $k$.

Your task is to determine whether it is possible to choose exactly $\frac{k}{2}$ elements from both arrays in such a way that among the chosen elements, every integer from $1$ to $k$ is included.

For example:

  • If $a=[2, 3, 8, 5, 6, 5]$, $b=[1, 3, 4, 10, 5]$, $k=6$, then it is possible to choose elements with values $2, 3, 6$ from array $a$ and elements with values $1, 4, 5$ from array $b$. In this case, all numbers from $1$ to $k=6$ will be included among the chosen elements.
  • If $a=[2, 3, 4, 5, 6, 5]$, $b=[1, 3, 8, 10, 3]$, $k=6$, then it is not possible to choose elements in the required way.

Note that you are not required to find a way to choose the elements — your program should only check whether it is possible to choose the elements in the required way.

Input

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

The first line of each test case contains three integers $n$, $m$, and $k$ ($1 \le n, m \le 2\cdot10^5$, $2 \le k \le 2 \cdot \min(n, m)$, $k$ is even) — the length of array $a$, the length of array $b$, and the number of elements to be chosen, respectively.

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

The third line of each test case contains $m$ integers $b_1, b_2, \dots, b_m$ ($1 \le b_j \le 10^6$) — the elements of array $b$.

It is guaranteed that the sum of values $n$ and $m$ over all test cases in a test does not exceed $4 \cdot 10^5$.

Output

Output $t$ lines, each of which is the answer to the corresponding test case. As the answer, output “YES” if it is possible to choose $\frac{k}{2}$ numbers from each array in such a way that among the chosen elements, every integer from $1$ to $k$ is included. Otherwise, output “NO”.

You can output each letter in any case (lowercase or uppercase). For example, the strings “yEs”, “yes”, “Yes”, and “YES” will be accepted as a positive answer.

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
6
6 5 6
2 3 8 5 6 5
1 3 4 10 5
6 5 6
2 3 4 5 6 5
1 3 8 10 3
3 3 4
1 3 5
2 4 6
2 5 4
1 4
7 3 4 4 2
1 4 2
2
6 4 4 2
1 5 2
3
2 2 1 4 3

output

1
2
3
4
5
6
YES
NO
YES
YES
NO
NO

Note

In the first test case of the example, it is possible to choose elements equal to $2$, $3$, and $6$ from array $a$ and elements equal to $1$, $4$, and $5$ from array $b$. Thus, all numbers from $1$ to $k=6$ are included among the chosen elements.

In the second test case of the example, it can be shown that it is not possible to choose exactly three elements from each array in the required way.

In the third test case of the example, it is possible to choose elements equal to $1$ and $3$ from array $a$ and elements equal to $2$ and $4$ from array $b$. Thus, all numbers from $1$ to $k=4$ are included among the chosen elements.

翻译

给定一个包含 $n$个整数的数组 $a$、一个包含 $m$个整数的数组 $b$和一个偶数 $k$。

您的任务是确定是否可以从两个数组中选择 精确 $\frac{k}{2}$$ 个元素，使得在所选元素中，包含从 $1$到 $k$的每个整数。

例如：

  • 如果是 $a=[2, 3, 8, 5, 6, 5]$、 $b=[1, 3, 4, 10, 5]$、 $k=6$，则可以从数组 $a$中选择值为 $2, 3, 6$的元素，从数组 $b$中选择值为 $1, 4, 5$的元素。在这种情况下，从 $1$到 $k=6$的所有数字都将包含在所选元素中。
  • 如果是 $a=[2, 3, 4, 5, 6, 5]$、 $b=[1, 3, 8, 10, 3]$、 $k=6$，则无法以所需的方式选择元素。

请注意，您不需要找到选择元素的方法——您的程序只需检查是否可以以所需的方式选择元素。

输入

输入的第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $n$ 、 $m$ 和 $k$ ( $1 \le n, m \le 2\cdot10^5$ 、 $2 \le k \le 2 \cdot \min(n, m)$ 、 $k$ 为偶数) — 分别表示数组 $a$ 的长度、数组 $b$ 的长度和要选择的元素数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^6$ ) — 数组 $a$ 的元素。

每个测试用例的第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$ ( $1 \le b_j \le 10^6$ ) — 数组 $b$ 的元素。

保证测试中所有测试用例的值 $n$ 和 $m$ 的总和不超过 $4 \cdot 10^5$ 。

输出

输出 $t$ 行，每行都是对应测试用例的答案。如果可以从每个数组中选择 $\frac{k}{2}$ 个数字，使得在所选元素中包括从 $1$ 到 $k$ 的每个整数，则输出“YES”作为答案。否则，输出“NO”。

您可以以任何大小写（小写或大写）输出每个字母。例如，字符串“yEs”、“yes”、“Yes”和“YES”将被接受为肯定答案。

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
6
6 5 6
2 3 8 5 6 5
1 3 4 10 5
6 5 6
2 3 4 5 6 5
1 3 8 10 3
3 3 4
1 3 5
2 4 6
2 5 4
1 4
7 3 4 4 2
1 4 2
2
6 4 4 2
1 5 2
3
2 2 1 4 3

output

1
2
3
4
5
6
YES
NO
YES
YES
NO
NO

注意

在示例的第一个测试用例中，可以从数组 $a$中选择等于 $2$、 $3$和 $6$的元素，从数组 $b$中选择等于 $1$、 $4$和 $5$的元素。因此，从 $1$到 $k=6$的所有数字都包含在所选元素中。

在示例的第二个测试用例中，可以证明不可能以所需的方式从每个数组中选择恰好三个元素。

在示例的第三个测试用例中，可以从数组 $a$中选择等于 $1$和 $3$的元素，从数组 $b$中选择等于 $2$和 $4$的元素。因此，从 $1$到 $k=4$的所有数字都包含在所选元素中。

思路

​ 首先每个数组中要有至少k/2个不同的1k间的元素，其次这些元素放在一起要正好能组合出一个1k的排列。

​ 有想不明白的同学可以考虑自己任意设置情况，去找一下反面情况。因为只要元素数量大于等于k/2并且能能全部出现排列，总有一种选择方式能使得全部出现。

代码一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>

using namespace std;
const int N = 2e5 + 10;


void solve() {
	int n, m, k;
	cin >> n >> m >> k;
	set<int>s1, s2, s; 
	
	s1.clear();
	s.clear();
	s2.clear();
	
	int ans1 = 0,ans2 = 0;
	for(int i = 0 ;i < n ;i ++)
	{
		int x;
		cin >> x;
		if(x <= k)
		{
			s1.insert(x);
			s.insert(x);
		}
	}
	for(int i = 0 ;i < m ;i ++)
	{
		int x;
		cin >> x;
		if(x <= k)
		{
	        s2.insert(x);
			s.insert(x);
		}
	}
	if(s.size() == k && s1.size() >= k / 2 && s2.size() >= k / 2) cout << "YES" << endl;
	else cout << "NO" << endl;
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}

	return 0;
}

代码二（思路其实差不了太大）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>


using namespace std;

void solve(){
	int n, m, k, t;
    cin >> n >> m >> k;
 
    vector<int> flag(k + 10);
 
    for (int i = 0; i < n; i++) {
        std::cin >> t;
        if (t <= k) {
            flag[t] |= 1;
        }
    }
 
    for (int i = 0; i < m; i++) {
        cin >> t;
        if (t <= k) {
            flag[t] |= 2;
        }
    }
 
    int a = 0, b = 0;
    for (int i = 1; i <= k; i++) {
        if (flag[i] == 0) {
            cout << "NO\n";
            return;
        }
        
        // a有b没有
        if (flag[i] == 1) {
            ++a;
            flag[i] = -1;
        } 
        // a没有b有
        else if (flag[i] == 2) {
            ++b;
            flag[i] = -1;
        }
    }
 
    int check = 0;
    for (int i = 1; i <= k; i++) {
        // 二者都有
        if (flag[i] != -1) {
            ++check;
        }
    }
 
    if (a <= k / 2 && b <= k / 2 && k - a - b == check) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}

	return 0;
}

D. Find the Different Ones!

You are given an array $a$ of $n$ integers, and $q$ queries.

Each query is represented by two integers $l$ and $r$ ($1 \le l \le r \le n$). Your task is to find, for each query, two indices $i$ and $j$ (or determine that they do not exist) such that:

  • $l \le i \le r$;
  • $l \le j \le r$;
  • $a_i \ne a_j$.

In other words, for each query, you need to find a pair of different elements among $a_l, a_{l+1}, \dots, a_r$, or report that such a pair does not exist.

Input

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

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

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

The third line of each test case contains a single integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries.

The next $q$ lines contain two integers each, $l$ and $r$ ($1 \le l \lt r \le n$) — the boundaries of the query.

It is guaranteed that the sum of the values of $n$ across all test cases does not exceed $2 \cdot 10^5$. Similarly, it is guaranteed that the sum of the values of $q$ across all test cases does not exceed $2 \cdot 10^5$.

Output

For each query, output two integers separated by space: $i$ and $j$ ($l \le i, j \le r$), for which $a_i \ne a_j$. If such a pair does not exist, output $i=-1$ and $j=-1$.

You may separate the outputs for the test cases with empty lines. This is not a mandatory requirement.

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
5
5
1 1 2 1 1
3
1 5
1 2
1 3
6
30 20 20 10 10 20
5
1 2
2 3
2 4
2 6
3 5
4
5 2 3 4
4
1 2
1 4
2 3
2 4
5
1 4 3 2 4
5
1 5
2 4
3 4
3 5
4 5
5
2 3 1 4 2
7
1 2
1 4
1 5
2 4
2 5
3 5
4 5

output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
2 3
-1 -1
1 3

2 1
-1 -1
4 2
4 6
5 3

1 2
1 2
2 3
3 2

1 3
2 4
3 4
5 3
5 4

1 2
4 2
1 3
2 3
3 2
5 4
5 4

翻译

您将获得一个包含 $n$ 个整数的数组 $a$ 和 $q$ 个查询。

每个查询由两个整数 $l$ 和 $r$ ( $1 \le l \le r \le n$ ) 表示。您的任务是为每个查询找到两个索引 $i$ 和 $j$ （或确定它们不存在），使得：

  • $l \le i \le r$ ;
  • $l \le j \le r$ ;
  • $a_i \ne a_j$ 。

换句话说，对于每个查询，您需要在 $a_l, a_{l+1}, \dots, a_r$ 中找到一对不同的元素，或者报告这样的一对不存在。

输入

输入的第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $n$ ( $2 \le n \le 2 \cdot 10^5$ ) — 数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^6$ ) — 数组 $a$ 的元素。

每个测试用例的第三行包含一个整数 $q$ ( $1 \le q \le 2 \cdot 10^5$ ) — 查询的数量。

接下来的 $q$ 行每行包含两个整数， $l$ 和 $r$ ( $1 \le l \lt r \le n$ ) — 查询的边界。

保证所有测试用例中 $n$ 的值的总和不超过 $2 \cdot 10^5$ 。同样，保证所有测试用例中 $q$ 的值的总和不超过 $2 \cdot 10^5$ 。

输出

对于每个查询，输出两个用空格分隔的整数： $i$ 和 $j$ ( $l \le i, j \le r$ )，其中 $a_i \ne a_j$ 。如果不存在这样的对，则输出 $i=-1$ 和 $j=-1$ 。

您可以用空行分隔测试用例的输出。这不是强制性要求。

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
5
5
1 1 2 1 1
3
1 5
1 2
1 3
6
30 20 20 10 10 20
5
1 2
2 3
2 4
2 6
3 5
4
5 2 3 4
4
1 2
1 4
2 3
2 4
5
1 4 3 2 4
5
1 5
2 4
3 4
3 5
4 5
5
2 3 1 4 2
7
1 2
1 4
1 5
2 4
2 5
3 5
4 5

output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
2 3
-1 -1
1 3

2 1
-1 -1
4 2
4 6
5 3

1 2
1 2
2 3
3 2

1 3
2 4
3 4
5 3
5 4

1 2
4 2
1 3
2 3
3 2
5 4
5 4

思路

​ 我们只需要从后往前记录每个位置元素最远可以延伸到右边元素下标位置，随后在进行l和r判断一下大小关系即可了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>


using namespace std;
const int N = 2e5 + 10;
int pos[N], a[N];

void solve(){
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	
	pos[n] = n + 1;
	for (int i = n - 1; i >= 1; i--) {
		if (a[i] == a[i + 1]) pos[i] = pos[i + 1];
		else {
			pos[i] = i + 1;
		}
	}
	
	int q;
	cin >> q;
	while (q--) {
		int l, r;
		cin >> l >> r;
		if (pos[l] > r) {
			cout << "-1 -1\n";
		} else {
			cout << l << " " << pos[l] << '\n';
		}
	}
	cout << '\n';
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}

	return 0;
}

E. Klever Permutation

Problem - E - Codeforces

You are given two integers $n$ and $k$ ($k \le n$), where $k$ is even.

A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in any order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation (as $2$ appears twice in the array) and $[0,1,2]$ is also not a permutation (as $n=3$, but $3$ is not present in the array).

Your task is to construct a $k$-level permutation of length $n$.

A permutation is called $k$-level if, among all the sums of continuous segments of length $k$ (of which there are exactly $n - k + 1$), any two sums differ by no more than $1$.

More formally, to determine if the permutation $p$ is $k$-level, first construct an array $s$ of length $n - k + 1$, where $s_i=\sum_{j=i}^{i+k-1} p_j$, i.e., the $i$-th element is equal to the sum of $p_i, p_{i+1}, \dots, p_{i+k-1}$.

A permutation is called $k$-level if $\max(s) - \min(s) \le 1$.

Find any $k$-level permutation of length $n$.

Input

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

The first and only line of each test case contains two integers $n$ and $k$ ($2 \le k \le n \le 2 \cdot 10^5$, $k$ is even), where $n$ is the length of the desired permutation.

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

Output

For each test case, output any $k$-level permutation of length $n$.

It is guaranteed that such a permutation always exists given the constraints.

Example

input

1
2
3
4
5
6
5
2 2
3 2
10 4
13 4
7 4

output

1
2
3
4
5
2 1
1 3 2
1 8 4 10 2 7 5 9 3 6
4 10 1 13 5 9 2 12 6 8 3 11 7
1 6 3 7 2 5 4

Note

In the second test case of the example:

  • $p_1 + p_2 = 3 + 1 = 4$;
  • $p_2 + p_3 = 1 + 2 = 3$.

The maximum among the sums is $4$, and the minimum is $3$.

翻译

给定两个整数 $n$ 和 $k$ ( $k \le n$ )，其中 $k$ 为偶数。

长度为 $n$ 的排列是一个数组，由 $n$ 个不同整数组成，这些整数从 $1$ 到 $n$ ，以任意顺序排列。例如， $[2,3,1,5,4]$ 是排列，但 $[1,2,2]$ 不是排列（因为 $2$ 在数组中出现两次），并且 $[0,1,2]$ 也不是排列（因为 $n=3$ ，但 $3$ 不存在于数组中）。

您的任务是构造一个长度为 $n$ 的 $k$ -level 排列。

如果在所有长度为 $k$ 的连续段（其中恰好有 $n - k + 1$ ）的和中，任何两个和相差不超过 $1$ ，则该排列称为 $k$ -level。

更正式地说，要确定排列 $p$ 是否为 $k$ -level，首先构造一个长度为 $n - k + 1$ 的数组 $s$ ，其中 $s_i=\sum_{j=i}^{i+k-1} p_j$ ，即第 $i$ -th 元素等于 $p_i, p_{i+1}, \dots, p_{i+k-1}$ 的和。

如果 $\max(s) - \min(s) \le 1$ ，则排列称为 $k$ -level。

查找长度为 $n$ 的任何 $k$ -level 排列。

输入

输入的第一行包含一个整数 $t$( $1 \le t \le 10^4$) — 测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行也是唯一一行包含两个整数 $n$和 $k$( $2 \le k \le n \le 2 \cdot 10^5$, $k$为偶数)，其中 $n$是所需排列的长度。

保证所有测试用例的 $n$之和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，输出长度为 $n$的 任何 $k$\ 级排列。

保证在给定约束的情况下始终存在这样的排列。

Example

input

1
2
3
4
5
6
5
2 2
3 2
10 4
13 4
7 4

output

1
2
3
4
5
2 1
1 3 2
1 8 4 10 2 7 5 9 3 6
4 10 1 13 5 9 2 12 6 8 3 11 7
1 6 3 7 2 5 4

注意

示例的第二个测试用例中：

  • $p_1 + p_2 = 3 + 1 = 4$ ;
  • $p_2 + p_3 = 1 + 2 = 3$ 。

总和中最大值为 $4$ ，最小值为 $3$ 。

思路

​ 这道题目的思路中间就卡了一个小壳，首先这道题目就是给我们2个数n和k，问$\sum{i-i+k-1}(i + k - 1 <= n)$的最大值和最小值相差要小于等于1,输出合法序列.

​ 这样我们只需要每次移动1,即可,同时每当+1一次我们就要-1一次,这样可以保证我们所有的数的和保持一致,上下浮动为1.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>

using namespace std;
const int N = 2e5 + 10;


void solve() {
	int n, m, k;
	cin >> n >> m >> k;
	set<int>s1, s2, s; 
	
	s1.clear();
	s.clear();
	s2.clear();
	
	int ans1 = 0,ans2 = 0;
	for(int i = 0 ;i < n ;i ++)
	{
		int x;
		cin >> x;
		if(x <= k)
		{
			s1.insert(x);
			s.insert(x);
		}
	}
	for(int i = 0 ;i < m ;i ++)
	{
		int x;
		cin >> x;
		if(x <= k)
		{
	        s2.insert(x);
			s.insert(x);
		}
	}
	if(s.size() == k && s1.size() >= k / 2 && s2.size() >= k / 2) cout << "YES" << endl;
	else cout << "NO" << endl;
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}

	return 0;
}

F. Microcycle(并查集 + DFS)

Given an undirected weighted graph with $n$ vertices and $m$ edges. There is at most one edge between each pair of vertices in the graph, and the graph does not contain loops (edges from a vertex to itself). The graph is not necessarily connected.

A cycle in the graph is called simple if it doesn’t pass through the same vertex twice and doesn’t contain the same edge twice.

Find any simple cycle in this graph in which the weight of the lightest edge is minimal.

Input

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

The first line of each test case contains two integers $n$ and $m$ ($3 \le n \le m \le \min(\frac{n\cdot(n - 1)}{2}, 2 \cdot 10^5)$) — the size of the graph and the number of edges.

The next $m$ lines of the test case contain three integers $u$, $v$, and $w$ ($1 \le u, v \le n$, $u \ne v$, $1 \le w \le 10^6$) — vertices $u$ and $v$ are connected by an edge of weight $w$.

It is guaranteed that there is at most one edge between each pair of vertices. Note that under the given constraints, there is always at least one simple cycle in the graph.

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

Output

For each test case, output a pair of numbers $b$ and $k$, where:

  • $b$ — the minimum weight of the edge in the found cycle,
  • $k$ — the number of vertices in the found cycle.

On the next line, output $k$ numbers from $1$ to $n$ — the vertices of the cycle in traversal order.

Note that the answer always exists, as under the given constraints, there is always at least one simple cycle in the graph.

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
5
6 6
1 2 1
2 3 1
3 1 1
4 5 1
5 6 1
6 4 1
6 6
1 2 10
2 3 8
3 1 5
4 5 100
5 6 40
6 4 3
6 15
1 2 4
5 2 8
6 1 7
6 3 10
6 5 1
3 2 8
4 3 4
5 3 6
2 6 6
5 4 5
4 1 3
6 4 5
4 2 1
3 1 7
1 5 5
4 6
2 3 2
1 3 10
1 4 1
3 4 7
2 4 5
1 2 2
4 5
2 1 10
3 1 3
4 2 6
1 4 7
2 3 3

output

1
2
3
4
5
6
7
8
9
10
1 3
1 2 3 
3 3
6 4 5 
1 5
4 2 1 6 3 
1 4
1 4 3 2 
3 3
2 3 1

翻译

给定一个无向加权图，其中有 $n$ 个顶点和 $m$ 个边。图中每对顶点之间最多有一条边，并且图中不包含环路（从顶点到自身的边）。图不一定是连通的。

如果图中的环路不会经过同一个顶点两次，也不会包含同一条边两次，则称其为简单环路。

在此图中找出任何简单环路，其中最轻边的权重最小。

输入

输入的第一行包含一个整数 $t$( $1 \le t \le 10^4$) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$和 $m$( $3 \le n \le m \le \min(\frac{n\cdot(n - 1)}{2}, 2 \cdot 10^5)$) — 图形的大小和边的数量。

测试用例的接下来的 $m$行包含三个整数 $u$、 $v$和 $w$( $1 \le u, v \le n$、 $u \ne v$、 $1 \le w \le 10^6$) — 顶点 $u$和 $v$由权重为 $w$的边连接。

保证每对顶点之间最多有一条边。请注意，在给定的约束条件下，图中始终至少有一个简单循环。

保证所有测试用例的 $m$值的总和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，输出一对数字 $b$和 $k$，其中：

  • $b$— 找到的循环中边的最小权重，
  • $k$— 找到的循环中的顶点数。

在下一行，输出 $k$个数字，从 $1$到 $n$— 按遍历顺序排列的循环顶点。

请注意，答案始终存在，因为在给定的约束下，图中始终至少有一个简单循环。

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
5
6 6
1 2 1
2 3 1
3 1 1
4 5 1
5 6 1
6 4 1
6 6
1 2 10
2 3 8
3 1 5
4 5 100
5 6 40
6 4 3
6 15
1 2 4
5 2 8
6 1 7
6 3 10
6 5 1
3 2 8
4 3 4
5 3 6
2 6 6
5 4 5
4 1 3
6 4 5
4 2 1
3 1 7
1 5 5
4 6
2 3 2
1 3 10
1 4 1
3 4 7
2 4 5
1 2 2
4 5
2 1 10
3 1 3
4 2 6
1 4 7
2 3 3

output

1
2
3
4
5
6
7
8
9
10
1 3
1 2 3 
3 3
6 4 5 
1 5
4 2 1 6 3 
1 4
1 4 3 2 
3 3
2 3 1

思路

​

代码

1