补题 [CF1831B] Array merging

题面翻译

题目描述

给定两个长度为 $n$ 的数组 $a$ 和 $b$。

猫猫让你合并这些数组，形成另一个长度为 $2n$ 的数组 $c$。你需要找到所有 $c$ 中元素值相同的子串长度的最大值。

合并两个数组的过程是：取出并删除 $a$ 或 $b$ 的第一个值，然后把取出的值追加到 $c$ 数组的末尾，具体删除顺序可以自由指定。这个过程重复 $2n$ 次，从而构造出长度为 $2n$ 的数组 $c$。

输入格式

第一行包含整数 $t$，表示测试数据的数量。

对于每组测试数据：

第一行一个整数 $n$，表示数组 $a$ 和 $b$ 的长度。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示数组 $a$ 的元素。

第三行 $n$ 个整数 $b_1,b_2,\dots,b_n$，表示数组 $b$ 的元素。

保证所有测试数据中 $n$ 的总和不超过 $ 2 \cdot 10^5 $。

输出格式

对于每个测试数据，输出跨所有合并数组 $c$ 的相等值的最大子数组的长度。

题目描述

You are given two arrays $ a $ and $ b $ both of length $ n $ .

You will merge $ ^\dagger $ these arrays forming another array $ c $ of length $ 2 \cdot n $ . You have to find the maximum length of a subarray consisting of equal values across all arrays $ c $ that could be obtained.

$ ^\dagger $ A merge of two arrays results in an array $ c $ composed by successively taking the first element of either array (as long as that array is nonempty) and removing it. After this step, the element is appended to the back of $ c $ . We repeat this operation as long as we can (i.e. at least one array is nonempty).

输入格式

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

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

The second line of each test case contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 1 \le a_i \le 2 \cdot n $ ) — the elements of array $ a $ .

The third line of each test case contains $ n $ integers $ b_1,b_2,\ldots,b_n $ ( $ 1 \le b_i \le 2 \cdot n $ ) — the elements of array $ b $ .

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

输出格式

For each test case, output the maximum length of a subarray consisting of equal values across all merges.

样例 #1

样例输入 #1

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

样例输出 #1

1
2
3
4
2
1
2
5

提示

In the first test case, we can only make $ c=[2,2] $ , thus the answer is $ 2 $ .

In the second test case, since all values are distinct, the answer must be $ 1 $ .

In the third test case, the arrays $ c $ we can make are $ [1,2,1,2] $ , $ [1,2,2,1] $ , $ [2,1,1,2] $ , $ [2,1,2,1] $ . We can see that the answer is $ 2 $ when we choose $ c=[1,2,2,1] $ .

题解

题目解析

一直没读懂题,导致自己寄的非常惨.这道题其实不难,可以证明想要连续最长,就得上下最长连续的加起来.总之就是找到某个数字在上下两个数列中的最长的连续个数的和.看看哪个数字会组成最长的序列.

AC代码

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
#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;

#define endl "\n"
#define MAXN(size) const long long MAXN = size + 100
#define var(size) int p[size]{}
#define mem(name,value) memset(name,value,sizeof(name))
#define fora(a,n,p) for(int i=a;i<=n;i+=p)
#define cin(length,var) for(int i=1;i<=length;i++) cin >> var[i]

typedef long long ll;

MAXN(2e5);
int a[MAXN],b[MAXN],cunt[MAXN*2];

int main(){
	int T;
	cin >> T;
	while(T--){
		int n;
		cin >> n;
		cin(n,a);cin(n,b);
		mem(cunt,0);
		int r=0,ans=0;
		fora(1,n,1){
			if(i != n && a[i] == a[i+1]) continue;
			cunt[a[i]] = max(cunt[a[i]],i-r);
			r = i;
			ans = max(ans,cunt[a[i]]);
		}
		r = 0;
		fora(1,n,1){
			if(i != n && b[i] == b[i+1]) continue;
			ans = max(ans,cunt[b[i]] + i - r);
			r = i;
		}
		cout << ans << endl;
	}
	return 0;
}