我再也不用 set 了

userId_undefined

复仇者_帅童

CSP-J一等奖出题人

2025-08-17 11:00:53

发布于：浙江

40阅读
0回复
0点赞

题目：给定两个长度分别为 N,MN,M 的数组 A,BA,B。

对于任意两个长度相等的数组 X,YX,Y，定义函数 f(X,Y)f(X,Y) 如下：

生成一个数列 CC，使 Ci=Xi+YiC_i=X_i+Y_i。如果 CC 是回文数列，则 f(X,Y)=1f(X,Y)=1，否则 f(X,Y)=0f(X,Y)=0。

请你求出最大的 ll，使得存在 A,BA,B 分别长度为 ll 的子数组 A′,B′A',B'，使 f(A′,B′)=1f(A',B')=1。

好的，我们遇到题先看部分分：

对于所有数据，1≤N,M≤105,1≤Ai,Bi≤1001\le N,M\le 10^5,1\le A_i,B_i\le 100。

好的，注意到没有部分分。这启发我们直接想正解。

有一个结论：如果存在一个数 ll 符合要求，则 l−2l-2 也符合这个要求。因为只需要让 A′,B′A',B' 删除最左边和最右边的数即可。但 l−1l-1 就不一定符合要求了，比如这里有一个 hack（我才不会告诉你这是样例）：

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

显然当 A′=[3,3,2],B′=[1,3,2]A'=[3,3,2],B'=[1,3,2] 可以使 f(A′,B′)=1f(A',B')=1，但不存在 l=2l=2 的情况使得存在子数组满足条件。

考虑奇偶分开二分，选择长度最大值。

现在的问题是：如何以 O(n)O(n) 左右的时间复杂度是否存在判断长度为 ll 的数使得子数组满足条件？

注意到 Ai,BiA_i,B_i 非常小，故考虑字符串哈希。

我们又注意到当长度为 nn 的数组 CC 为回文数组时，∑i=1nCi×Pi=∑i=1nCi×Pn−i+1\sum_{i=1}^{n} C_i\times P^i=\sum_{i=1}^{n} C_i\times P^{n-i+1}，其中 PP 为任意正整数。所以我们可以通过这个特殊性质来判断，我们记录每个长度为 ll 的子数组的正反哈希值之差，然后 O(nlog⁡n)O(n\log n) 查找即可。时间复杂度 O(nlog⁡2n)O(n\log^2 n)。由于 105×(log⁡2105)2≈3×10710^5\times (\log_2 10^5)^2\approx 3\times 10^7，而且奇偶分开二分本身带了 22 的常数，所以就不能使用大常数的 map set 了，应该使用排序二分代替。

如果你用 set，

100→72100\rarr 72

还有，不能用单模哈希，冲突概率巨大，随机生成两个 10510^5 的数组它会说最长的 l≈9×104l\approx 9\times 10^4，但真正的答案在 99 左右！

#include <iostream>
#include <cstdio>
#include <vector>
#include <random>
#include <ctime>
#include <algorithm>
#define int long long
using namespace std;
mt19937 rng;
int a[100005], b[100005];
int n, m;
int inv(int n, int mod){
	int t = mod - 2, ans = 1;
	while(t){
		if(t & 1) ans = ans * n % mod;
		n = n * n % mod, t >>= 1;
	}
	return ans;
}
struct hashhh{
	int Hsha1[100005], Hsha2[100005];
	int Hshb1[100005], Hshb2[100005];
	int ksm[100005], ksminv[100005];
	int mul, mod;
	void init(int mul, int mod){
		this -> mul = mul, this -> mod = mod;
		ksm[0] = 1;
		ksminv[0] = 1;
		ksminv[1] = inv(mul, mod);
		for(int i = 1; i <= 100000; i++) ksm[i] = ksm[i - 1] * mul % mod;
		for(int i = 1; i <= 100000; i++){
			ksminv[i] = ksminv[i - 1] * ksminv[1] % mod;
		}
		for(int i = 1; i <= n; i++){
			Hsha1[i] = (Hsha1[i - 1] * mul + a[i]) % mod;
			Hsha2[i] = (Hsha2[i - 1] + a[i] * ksm[i - 1]) % mod;		
		}
		for(int i = 1; i <= m; i++){
			Hshb1[i] = (Hshb1[i - 1] * mul + b[i]) % mod;
			Hshb2[i] = (Hshb2[i - 1] + b[i] * ksm[i - 1]) % mod;
		}
	}
	int get(int n, int i, int val){
		if(n == 1) return ((Hsha1[i] - Hsha1[i - val] * ksm[val]) % mod + mod) % mod;
		if(n == 2) return ((Hsha2[i] - Hsha2[i - val]) % mod + mod) % mod * ksminv[i - val] % mod;
		if(n == 3) return ((Hshb1[i] - Hshb1[i - val] * ksm[val]) % mod + mod) % mod;
		if(n == 4) return ((Hshb2[i] - Hshb2[i - val]) % mod + mod) % mod * ksminv[i - val] % mod;
	}
}test1, test2, test3;


int func(int hsh1, int hsh2, int mod){
	return ((hsh1 - hsh2) % mod + mod) % mod;
}

bool check(int val){
	vector <pair <pair <int, int>, int>> v;
	for(int i = val; i <= n; i++){
		int hsh11 = test1.get(1, i, val);
		int hsh12 = test1.get(2, i, val);
		int hsh21 = test2.get(1, i, val);
		int hsh22 = test2.get(2, i, val);
		int hsh31 = test3.get(1, i, val);
		int hsh32 = test3.get(2, i, val);
		v.push_back({{func(hsh11, hsh12, test1.mod), func(hsh21, hsh22, test2.mod)}, func(hsh31, hsh32, test3.mod)});
	}
	sort(v.begin(), v.end());
	for(int i = val; i <= m; i++){
		int hsh11 = test1.get(4, i, val);
		int hsh12 = test1.get(3, i, val);
		int hsh21 = test2.get(4, i, val);
		int hsh22 = test2.get(3, i, val);
		int hsh31 = test3.get(4, i, val);
		int hsh32 = test3.get(3, i, val);
		pair <pair <int, int>, int> tmp = {{func(hsh11, hsh12, test1.mod), func(hsh21, hsh22, test2.mod)}, func(hsh31, hsh32, test3.mod)};
		if((*lower_bound(v.begin(), v.end(), tmp)) == tmp) return 1;
	}
	return 0;
}
signed main(){
	freopen("palindrome.in", "r", stdin);
	freopen("palindrome.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	rng.seed(time(0));
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= m; i++) cin >> b[i];
	test1.init(rng() % (998244352 / 2) + (998244352 / 2), 998244353);
	test2.init(rng() % (1000000006 / 2) + (1000000006 / 2), 1000000007);
	test3.init(rng() % (1000002 / 2) + (1000002 / 2), 1000003);
	int l = 1, r = min(n, m);
	while(l <= r){
		int mid = l + r >> 1;
		int tmp = mid * 2 - 1;
		if(tmp <= min(n, m) && check(tmp)) l = mid + 1;
		else r = mid - 1;
	}
	int ans = r * 2 - 1;
	l = 1, r = min(n, m);
	while(l <= r){
		int mid = l + r >> 1;
		int tmp = mid * 2;
		if(tmp <= min(n, m) && check(tmp)) l = mid + 1;
		else r = mid - 1;
	}
	ans = max(ans, r * 2);
	cout << ans << '\n';
	
	cout.flush();
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}

时间复杂度 O(nlog⁡2n)O(n\log^2 n)。

userId_undefined
去预览
0/2000

全部评论 11

热门讨论