本文主要是介绍[ABC369C] Count Arithmetic Subarrays，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
首先看了下题意 大致题意就是让你在长度为的序列找出所有的等差数列。
-----------------------------------------------------------------------------------------我是分界线
我的思路了，就是先从2开始计算等差数列，从3开始判断，如果是等差数列的话就继续累加，如果不是判断它是否是第一个等差数列，是就直接，如果不是就减1去除掉重复的部分。最后把未处理的部分加上去就行了。
注意题目上给出的限制
- 1≤ N ≤ 2× 105
- 1≤ Ai ≤ 1091≤ Ai ≤ 109
要开long long,否则会爆int。
#include<bits/stdc++.h>
#define int long long
#define fast register int using namespace std;const int N=2e5+100;int a[N],n,m,b[N],cnt=2,ans=0,d=0,flag=1;
//cnt代表着现在等差数列包含的数的数量，ans代表最终答案，d就是等差数列的差，flag代表着是否是$A$序列是一个完整的等差数列signed main(){std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0); //不喜欢标准输入输出的人的专用cin>>n;if (n==1){cout<<1;return 0;}//n=1直接输出1for (fast i=1;i<=n;i++){cin>>a[i];if (i==2){cnt=2;qwq=a[i]-a[i-1];continue;}if (i>=3){if (a[i]-a[i-1]==d){//如果相等就继续累加cnt++;continue;//跳过下个步骤}else {if (flag==1){//如果是一串从a[1]开始就不减1ans+=cnt*(cnt+1)/2;flag++;//flag更改}else {//反之要去除掉重复的部分，就要减1ans+=cnt*(cnt+1)/2-1;}cnt=2;//重新从a[i-1]开始一个新的等差数列d=a[i]-a[i-1];//更新qcontinue;}}}//将最后的数列也要算进去if (flag!=1){//如果不是一条从a[1]到a[n]的连续的等差数列就减1ans+=cnt*(cnt+1)/2-1;}else {//反之不减ans+=cnt*(cnt+1)/2;}cout<<ans;return 0;
}这篇关于[ABC369C] Count Arithmetic Subarrays的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
