(曾经被一道这样的题目难住)[https://ac.nowcoder.com/acm/problem/285517]
多少连续子段是等差数列
1
2
3
4
5
6
7
8
9
10
| 给定长度为 n 的数列，问其中多少连续子段是等差数列？
输入描述：
第一行输入一个整数 n，表示数列长度。
第二行输入 n 个整数，其中第 i 个整数代表数列第 i 个位置的元素。
输出描述：
输出一行一个整数表示答案。
说明：
所有连续子段都是等差数列
|
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+100;
int n;
int a[N];
int b[N];
ll solve(){
ll ans = n;
for(int i = 1; i < n; ){
int temp = i;
while(temp < n && b[i] == b[temp])temp++ ;
ll cnt = temp - i + 1;
ans += cnt * (cnt - 1) / 2;
i = temp;
}
return ans;
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1;i < n;++ i)
{
b[i] = a[i+1]-a[i];
}
printf("%lld\n", 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
| #include<bits/stdc++.h>
using namespace std;
int n;
const int maxn = 1e5+10;
using ll = long long ;
int a[maxn];
int b[maxn];
ll ans = 0;
ll tempans;
int main()
{
cin >> n;
for(int i = 1;i <= n;++ i)
{
cin >> a[i];
}
for(int i = 1;i < n;++ i)
{
b[i] = (a[i+1] - a[i]);
}
for(int i = 1;i <= n-1;i++)
{
tempans = 1;
while(i < n-1 && b[i+1]==b[i])
{
tempans ++ ;
i ++ ;
}
ans += (tempans)*(tempans+1) / 2;
}
ans = ans + n;
cout << ans << endl;
return 0;
}
|
感觉有三个坑点，
一个是对题目的理解，连续子段都是等差数列但是等差数列不一定都是连续子段
连续子段可以重叠，通过差分数组的计算可以避开这种繁琐。
还有就是连续子段可以是任意两个，也就是说，不仅需要单个处理连续长度为1的情况（答案+n），遍历时还要注意考虑到任意两个数都是连续子序列，也就是说每个差分数组的元素对答案都至少有1的贡献。
还有一次在python中遇到这个问题：同样是利用差分数组
连续整数的最大长度
输入一个整数的Numpy数组，返回其中严格递增连续整数子数组的最大长度，正向是指递增方向。例如，输入[1,2,5,6,7]，[5,6,7]为具有最大长度的连续整数子数组，因此输出3；输入[3,2,1,2,3,4,6]，[1,2,3,4]为具有最大长度的连续整数子数组，因此输出4。请充分利用Numpy的内置函数完成。（提示：考虑使用nonzero, diff函数）
1
2
3
| f = lambda x:np.diff(np.nonzero(np.r_[1,np.diff(x)!=1,1])).max()
f([1,2,5,6,7])
|