多校第九场Arithmetic Sequence题解

题目链接：http://acm.hdu.edu.cn/showproblem.php?

pid=5400

题意：给定等差数列的差值d1，d2。问长度为n的数列中有多少个满足条件的子序列，条件为子序列中存在一个xi满足前半段是差值为d1的等差数列，后半段是差值为d2的等差数列

思路：

首先预处理出来出 $i$ 这个位置向前 $d_1$ 的等差序列和向后 $d_2$ 的等差数列能延续到多长，记作 $l_i,r_i$ 。

假设 $d_1 eq d_2$ ，那么枚举中间位置。答案为 $l_i*r_i$ 。

假设 $d_1=d_2$ 。枚举開始位置，答案为 $r_i$ 。

代码：

#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <cassert>
#include <complex>
using namespace std;
#define ll long long
const int N=101000;
int n,d1,d2,a[N],l[N],r[N];
ll ans;
int main()
{
while (scanf("%d%d%d",&n,&d1,&d2)!=EOF)
{
for(int i=0; i<n; i++)
scanf("%d",&a[i]);
for(int i=0; i<n; i++)
{
if (i==0||a[i-1]+d1!=a[i])
l[i]=1;
else
l[i]=l[i-1]+1;
}

for(int i=n-1; i>=0; i--)
{
if (i==n-1||a[i]+d2!=a[i+1])
r[i]=1;
else
r[i]=r[i+1]+1;
}
ans=0;
for(int i=0; i<n; i++)
{
if (d1!=d2)
ans+=(ll)l[i]*r[i];
else
ans+=r[i];
}
printf("%lld ",ans);
}
}