专栏文章

小埋的最大差值 题解

NNecessary
个人记录参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mir2nis8
此快照首次捕获于
2025/12/04 14:45
3 个月前
此快照最后确认于
2025/12/04 14:45
3 个月前
查看原文

小埋的最大差值 题解

前置芝士：前缀和，小学数学，脑子

正片开始！

题意：找出一个极差，使得maxmax{ ak−ala_k - a_l} (k=∑s=0nii∗k,l=k−ik = \sum_{s = 0}^{\frac{n}{i}}i * k, l = k - i )最大。
举个例子：
CPP
6
10 2 3 6 1 3
k123456
101215
2
39
610
14
3
ans985
所以，最终输出9；
我们发现，本题只要维护aia_i数组的区间和，并按题目要求依次模拟。
但怎样维护区间和呢？
对了，前缀和！
CPP
s[i] = s[i-1] + a[i];
但一次一次枚举太慢了,时间复杂度达到了O(T∗n)O(T * n),无法通过此题。
但我们注意到：nn 的 因子最多只有 2n2 \sqrt{n}个。
所以时间复杂度来到了O(T∗2n)O(T * 2\sqrt{n}),可以通过此题。
所以，代码就打出来了！
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
int t, n, a[1000005], s[1000005];
int check (int k) {
	int x = LLONG_MIN, y = LLONG_MAX;
	for(int i = k; i <= n; i += k) {
		x = max(abs(s[i] - s[i - k]), x);
		y = min(abs(s[i] - s[i - k]), y);
	}
	return x - y;
}
signed main (void) {
	cin >> t; int ans = 0;
	while(t--) { 
		ans = 0; memset(s, 0, sizeof(s));
		cin >> n;
		for(int i = 1; i <= n; i++) {
			cin >> a[i]; s[i] = s[i - 1] + a[i];
		}
		for(int i = 1; i <= 2 * sqrt(n); i++) {
			if(n % i == 0) {
				ans = max(ans, check(i));
        ans = max(ans, check(n / i));
			}
		}
		cout << ans << endl;
	}
	return 0;
}
你会发现，WAWA了（哭）
注意到，如上述例子的情况，无法得出正确结果。
所以我们需要打一个补丁：
CPP
int l, r;
l = LLONG_MAX, r = LLONG_MIN;
for(......) {
  ......
  l =  (r = min(r, a[i]), max(l, a[i]));
}
终于ACAC勒！！！！！
贴上代码：
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
int t, n, a[1000005], s[1000005];
int check (int k) {
	int x = LLONG_MIN, y = LLONG_MAX;
	for(int i = k; i <= n; i += k) {
		x = max(abs(s[i] - s[i - k]), x);
		y = min(abs(s[i] - s[i - k]), y);
	}
	return x - y;
}
signed main (void) {
	cin >> t; int ans = 0;
	while(t--) { 
		ans = 0; memset(s, 0, sizeof(s));
		cin >> n; int l = LLONG_MAX, r = LLONG_MIN;
		for(int i = 1; i <= n; i++) {
			cin >> a[i]; s[i] = s[i - 1] + a[i];
			l = min(l, a[i]); r = max(r, a[i]);
		}
		ans = max(ans, r - l);
		for(int i = 1; i <= 2 * sqrt(n); i++) {
			if(n % i == 0) {
				ans = max(ans, check(i));
				ans = max(ans, check(n / i));
			}
		}
		cout << ans << endl;
	}
	return 0;
}
(注意本题的阴间数据, n≤1.5∗105n \le 1.5 * 10^5 ,不要开1e5!!!1e5!!!)

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...