【马蹄集】第十二周作业-Toy模板网

这篇具有很好参考价值的文章主要介绍了【马蹄集】第十二周作业。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前缀和与差分专题

MT2056 二阶前缀和

难度：黄金时间限制：1秒占用内存：128M

题目描述

在一个直角坐标系上，有 $n$ 个坐标上有元素值（其余坐标的元素值为0），现给定一些点的坐标 $\left(x_i,y_i\right)$ 和这个坐标的元素值 $v_i$ ，计算用一个边长为 $R$ 的正矩形能囊括坐标元素值的和的最大值。不包括正方形的边界。

格式

输入格式：输入文件的第一行为两个正整数 $n$ 和 $R$ ；；
接下来的 $n$ 行每行有 3 个自然数，分别表示 $x_i,y_i,v_i$ 。
输出格式：输出文件仅有一个正整数，表示一个正方形最多能囊括地图上的最大的元素值之和。

样例 1

输入：2 1

0 0 1
1 1 1

输出：1

备注

不保证给出的数据坐标不重复，如果有相同坐标的输入，请将他们的 $v_i$ 进行累加，视为一个坐标；
$1\le n,R\le1000,\ 0\le x_i,y_i\le1000,\ 0\le v_i\le{10}^8$

正方形的边必须与 $x, y$ 轴平行。

相关知识点： 前缀和与差分

题解

题如其名，考察的是二维前缀和（有尚不清楚此数据结构的同学请移步至：前缀和与差分）。下面直接给出构建二维前缀和的数学公式：

$prefix\left[i\right][j]=\sum_{x=1}^i\sum_{y=1}^jmatrix[x][y]$

它表示从位置 $ma t r i x [1] [1]$ 到 $ma t r i x [i] [j]$ 这之间所有元素的总和。
在给定两个指示位置的序数对 $\left(x_1,y_1\right),\ \left(x_2,y_2\right)$ 后，通过二维前缀和数组求解指定子阵元素和的公式为：
$S=prefix[x_2][y_2]-prefix[x_1-1][y_2]-prefix[x_2][y_1-1]+prefix[x_1-1][y_1-1]$

下面直接给出基于上述公式得到的完整代码（已 AC）：

/*
    MT2056 二阶前缀和 
    
*/

#include<bits/stdc++.h> 
using namespace std;

const int MAX = 1005;
int ary[MAX][MAX], prefix[MAX][MAX], ans;

int main( )
{
    // 录入数组内容的同时构建二维前缀和
    int n,R,x,y,v; cin>>n>>R;
    while(n--){
        cin>>x>>y>>v;
        ary[++x][++y] += v;
    }

    // 计算二维前缀和
    for(int i=1;i<1001;i++)
        for(int j=1;j<=1001;j++)
            prefix[i][j] += prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1]+ary[i][j];
            
     // 寻找指定范围的最大子阵
     for(int i=R;i<1001;i++)
        for(int j=R;j<=1001;j++)
            ans = max(ans, prefix[i][j]-prefix[i-R][j]-prefix[i][j-R]+prefix[i-R][j-R]); 
    
    // 输出结果 
    cout<<ans<<endl;
    
    return 0;
}

MT2057 门票

难度：钻石时间限制：1秒占用内存：128M

题目描述

小码哥家附近的一个主题公园最近搞了一个活动，小码哥在活动中获得了一等奖。而一等奖是一长串的纸条，上面有 $n$ 个格子，每个格子里有一个数字，活动人员告诉小码哥，只要他裁下一段连续的格子，格子内数字的总和除以裁下的格子的数量大于等于门票费 $t$ ，那么小码哥就能用这段格子抵消门票费。
小码哥想要尽可能多的利用这个奖品，为此他想先知道有多少种裁剪的方案能裁出一段能抵消门票费的格子。
由于方案数可能很大所以需要你输出方案数对1e9＋7取模的结果。

格式

输入格式：第一行两个正整数整数 $n$ 和 $t$ ，分别表示格子的数量和门票费；
第二行 $n$ 个整数 $a_i$ ，表示格子内的数字。
输出格式：输出一个整数，表示总方案数对1e9＋7取模的结果。

样例1

输入： 5 4
3 4 2 3 5

输出：3

备注

其中： $1\le n\le{10}^6,1\le t\le{10}^8,\ 0\le a_i\le{2\times10}^8$

相关知识点：前缀和与差分、归并排序

题解

实际上，题目的要求是找出指定序列中所有“均值不低于指 $t$ 的子序列”个数。一个很直观的想法是，既然你要求序列均值不低于 $t$ ，那我们可以将原序列中的每个数都与 $t$ 做差，这样一来，得到的新序列里一旦存在某串序列之和大于 0，那就说明这段序列的均值是大于 $t$ 的（即符合要求的序列）：

【马蹄集】第十二周作业

但是，要枚举一个序列中的子序列，其时间复杂度度为 $O\left(n^2\right)$ ，如果还要对每个子序列求和 $O\left(n\right)$ ，时间复杂度就攀升至 $O\left(n^3\right)$ ，这对本题而言必定超时。说起“区间求和”，或许你会很快地想到“前缀和”这一结构。当加入前缀和后，区间求和就从 $O\left(n\right)$ 降至常数级，这将大大加快搜索速度。所以，在数据输入时我们可直接构建原数组与 $t$ 之差的前缀和：

for(int i=1;i<=n;i++){
   cin>>num;
   prefix[i] = prefix[i-1] + num - t;
}

但加入前缀和后也仅仅是加快了区间求和的过程，查找子序列还是 $O\left(n^2\right)$ ，依然会超时。所以现在的问题关键在于：怎么从原始序列中快速找到均值大于 $t$ 的子序列？或者说怎么从前缀和数组中找到递增的子序列。为什么是递增？因为对前缀和数组而言，只要当 $i < j$ ，存在 $prefix\left[i\right]\le prefix\left[j\right]$ ，就说明区间 $[i + 1, j]$ 中的所有数之和不低于0。而根据上面的分析可知（prefix[] 数组为“原数组与 $t$ 之差的前缀和”），则这样的 $p re f i x []$ 在出现 $prefix\left[i\right]\le prefix\left[j\right]\ (i<j)$ 时就表明其均值大于 $t$ 。例如，对于题目给出的数列（假设数组索引均从 1 开始）：
${3, 4, 2, 3, 5\}$

其对应的 “与 $t = 4$ 之差的前缀和” 数组为：
${-1, -1, -3, -4, -3\}$

在该数组中，递增区间为 $[4, 5]$ ，对应前缀和中的取值为 $p re f i x [4] = - 4, p re f i x [5] = - 3$ ，而 $prefix\left[5\right]\geq prefix\left[4\right]$ ，因此认为当前找到了一个均值不低于 $t = 4$ 的子区间，其相较 $t$ 增加了 $p re f i x [j] - p re f i x [i] = p re f i x [5] - p re f i x [4] = p re f i x [5] - p re f i x [4] = 1$ 。下面我们从原数组中对其进行验证：

原数组中， $a ry [4 + 1] = a ry [5] = 5, a ry [5] = 5$ ，因此该子段的均值为 $(5 + 5) /2 = 5$ ，这与我们通过前缀和得到的结论一致（均值增加了1）。

到这一步，我们实际上将原问题转换为：“求原数组与 $t$ 之差的前缀和数组中，所有 $i < j$ 且 $prefix\left[i\right]\le prefix\left[j\right]$ 的数对个数”。以题目给出的数列为例，可以发现，其与 $t$ 之差的前缀和数组中，符合要求的数对有：

$i=1,\ j=2$ 时， $prefix\left[1\right]=-1\le-1=prefix\left[2\right]$ ，对应原序列区间 $[i + 1, j] = [2, 2]$ ，均值为 $4/1 = 4$ ；
$i=3,\ j=5$ 时， $prefix\left[3\right]=-3\le-3=prefix\left[5\right]$ ，对应原序列区间 $[i + 1, j] = [4, 5]$ ，均值为 $(3 + 5) /2 = 4$ ；
$i=4,\ j=5$ 时， $prefix\left[4\right]=-4\le-3=prefix\left[5\right]$ ，对应原序列区间 $[i + 1, j] = [5, 5]$ ，均值为 $5/1 = 5$ 。

而 “所有 $i < j$ 且 $prefix\left[i\right]\le prefix\left[j\right]$ 的数对个数” 实际上表达的是 “非逆序对” 的含义。

问：什么是“非逆序对”？
答：只要不是“逆序对”那就是“非逆序对”。
问：那什么是“逆序对”？
答：在一个数组 $ary[\ ]=\{a_1,a_2,…,a_n\}$ 中，如果有 $i < j$ （ $i, j$ 为非负整数），且 $a ry [i] > a ry [j]$ ，则称 $(a ry [i], a ry [j])$ 为数组 $ary[\ ]$ 中的一个逆序对。

所以，可将原问题转换为：“求原数组与 $t$ 之差的前缀和数组中，非逆序对的数量”。
求解非逆序对最原始的办法就是利用两重循环进行枚举，其时间复杂度为 $O\left(n^2\right)$ 。当然，有优化算法：利用归并排序求解逆序对数量，此算法的时间复杂度为 $O\left(nlogn\right)$ 。

归并排序是九大排序算法之一，属于稳定的排序算法，其实现方式主要有自上而下和自下而上两种（参考博客：https://blog.csdn.net/u012294613/article/details/125527224），从代码的实现角度来看，更常用的是基于递归思想的自上而下算法。其主要思路如下：

划分问题：把序列划分为元素个数尽量相等的两个序列；
递归求解：对子序列继续执行归并排序；
归并问题：将2中得到的两个有序序列进行合并。

从上面可以看出，序列被传入函数的一开始并不会执行排序，因为“排序”这个操作的处理对象是 “有序序列”，而第一次将待排序序列传入时，其总是会被视为 “无序序列” ，因此被传入的序列首先执行的操作永远是划分。而当某个 “序列” 的长度为1时，这个序列就一定是有序的，此时算法才真正开始执行排序（也就是步骤 3，该步在执行合并的过程实际上正是对序列排序）。下面用一个例子来说明归并排序的流程：
$\left\{24,\ 5,\ 4,\ 37,\ 12,\ 16,\ 7,\ 9,\ 6\right\}$
此序列在传入归并排序的递归函数时，会首先将其进行划分，并得到两个子序列： $\left\{24,\ 5,\ 4,\ 37\},\{12,\ 16,\ 7,\ 9,\ 6\right\}$ ，接下来这两个子序列也会被传入递归函数中，并不断执行递归分解，如此往复，直到该序列最终被划分为若干个长度为1的子序列，即： $\left\{24\right\},\ \left\{5\right\},\{4\},\{37\},\{12\},\{16\},\{7\},\{9\},\{6\}$ 。此时，对于每个子序列（其都已经走到了各自递归函数的尽头，即不会再被划分），说明其长度为1，也就是说每个序列现在都是有序的，于是开始执行步骤3（注：归并时，选择的两个子序列是相邻的）。

第一次归并： $\left\{5,\ 24\right\},\{4,\ 37\},\{12,\ 16\},\{7,\ 9\},\{6\}$ ；
第二次归并： $\left\{4,\ 5,\ 24,\ 37\right\},\{7,\ 9,\ 12,\ 16\},\{6\}$ ；
第三次归并： $\left\{4,\ 5,\ 7,\ 9,\ 12,\ 16,\ 24,\ 37\right\},\{6\}$ ；
第四次归并： $\left\{4,\ 5,\ 6,\ 7,\ 9,\ 12,\ 16,\ 24,\ 37\right\}$ ；

算法结束，完成排序。

归并排序的核心就是第三步执行归并的过程，其实现方式很简单，由于每次处理的两个序列都是有序的，那么他每次都从这两个序列中取出当前的最值，在进行比较后，再将比较结果中的最值插入临时数组，如此往复，直到两个序列均为空时即完成了对两个子序列的排序（最终的有序数组暂存于该临时数组中）。

下面给出归并排序的完整代码：

/**
* 对 ary 数组中 [l,r] 区间内的元素进行排序
*
* @param l 区间左边界，闭区间
* @param r 区间右边界，闭区间
*/
void merge_sort(int ary[], int l , int r)
{
    // 递归终止条件 
    if(l >= r) return;
    
    // 划分区间的中间位置
    int mid = (l+r) >> 1;
    
    // 对两个子序列分别排序
    merge_sort(ary,l,mid);
    merge_sort(ary,mid+1,r);
    
    // 定义两个子序列的指针以及合并数组的指针
    int i = l, j = mid+1, pos=0; 
    
	// 归并子序列
	while(i<=mid && j<=r){
        if(ary[i] <= ary[j]) mergeAry[pos++] = ary[i++];
        else mergeAry[pos++] = ary[j++];
    }
    while(i<=mid) mergeAry[pos++] = ary[i++];
    while(j<=r) mergeAry[pos++] = ary[j++];
    
    // 将归并数组中排好序的元素复制到原始数组中（以供迭代），使原始数组中[l,r]区间内的元素有序 
    for(i=l, j=0; i<=r;i++,j++) ary[i] = mergeAry[j];
}

从归并排序的算法流程中注意到一件事：每次在对子序列执行归并时，都涉及到若干次的数字比较（比较两个子序列中各数的大小关系）。而各个子序列最终都会被归并至一个数组中，那这就是说，全部的数字都会参与到相对大小的比较中，这正好可用于统计逆序数！需要注意的是，如果采用归并排序统计逆序数，应当要构建升序序列；反之，如果要统计非逆序数，则应当构建降序序列。

于是，根据上述代码可写出求解本题的完整代码（已 AC）：

/*
    MT2057 门票 
*/

#include<bits/stdc++.h> 
using namespace std;

const int MAX = 1e6+5;
const int MOD = 1e9+7; 
long ans=0, prefix[MAX], tmp[MAX]; 

void merge_sort(int l, int r, long ary[])
{
    // 递归终止条件 
    if(l>=r) return;
    // 序列划分中点 
    int mid = (l+r) >> 1;
    // 对子序列分别排序 
    merge_sort(l, mid, ary);
    merge_sort(mid+1, r, ary);
    // 定义两个子序列的指针以及合并数组的指针
    int i=l, j=mid+1, t=0;
    // 归并子序列
    while(i<=mid && j<=r){
        // 构建降序序列，直接统计非逆序数 
        if(ary[i] <= ary[j]){
            tmp[t++] = ary[j++];
            ans += mid-i+1;
            ans %= MOD;
        }
        else tmp[t++] = ary[i++];
    }
    while(i<=mid) tmp[t++] = ary[i++];
    while(j<=r) tmp[t++] = ary[j++];
    // 将归并数组中排好序的元素复制到原始数组中（以供迭代），使原始数组中[l,r]区间内的元素有序
    for(int i=l, j=0; i<=r;i++,j++) ary[i] = tmp[j];
}

int main( )
{
    // 录入数据 
    int n,t,num; cin>>n>>t; 
    for(int i=1;i<=n;i++){
        cin>>num;
        // 构建原数组与 t 之差的前缀和数组
        prefix[i] = prefix[i-1] + num - t;
    }
    // 利用归并排序计算非逆序数 
    merge_sort(0,n,prefix);
    // 输出结果 
    cout<<ans%MOD<<endl;
    
    return 0;
}

MT2058 最大的平均值

难度：黄金时间限制：1秒占用内存：128M

题目描述

给一个长度为 $n$ 的数组，找一个长度大于等于 $m$ 的子区间，使这个区间的元素的平均值最大。

格式

输入格式：第一行输入整数 $n$ 和 $m$ ，数据用空格隔开；
接下来输入 $n$ 个整数。
输出格式：输出一个整数，表示平均值的最大值乘以1000再向下取整之后得到的结果。

样例 1

输入：10 6
6 4 2 10 3 8 5 9 4 1
输出：6500

备注

其中： $1\le n\le100000,\ 1\le m\le n,\ 0\le a_i\le{10}^7$ 。

相关知识点：前缀和与差分、分治

题解

这道题和【洛谷】P1404 平均数完全一致，该题我单独写了题解：☞ 传送门

下面直接给出求解本题的完整代码（已 AC）：

/*
    MT2058 最大的平均值 
    洛谷 P1404
*/

#include<bits/stdc++.h> 
using namespace std;

const int MAX = 1e5+5;
int ary[MAX];
double prefix[MAX],eps=1e-8;

// 此函数用于判断：原数组中是否存在长度不低于 m 的子序列，使得其均值大于 thresold 
bool anySeq(int ary[], int n, int m, double thresold){
    double minGap = 0;
    
    // 计算以 thresold 为基准值得到的差值数组的前缀和数组
    for(int i=1;i<=n;i++){
        prefix[i] = prefix[i-1] + (ary[i]-thresold);
        
        // 当 i 不低于 m 时，就能检测子序列的存在情况了
        if(i>=m) {
            minGap = min(minGap, prefix[i-m]);
            
            // 只要该前缀和数组中存在不低于 0 的值，说明一定存在某个序列能使其均值大于 thresold 
            if(prefix[i]>minGap) return true;
        }
    } 
    
    return false; 
}

int main( )
{
    // 录入数据 
    int n,m,maxtmp=-1; cin>>n>>m; 
    
    // 录入原始数组，并记录最大值（该最大值表明此数组能取到的最大平均值即为该值） 
    for(int i=1;i<=n;i++){
        cin>>ary[i];
        maxtmp = max(maxtmp, ary[i]);
    }
    
    // 对最大平均值进行二分查找
    double minave = 0, maxave = maxtmp, midave;
    
    // 这里必须用精度进行控制，否则会超时 
    while(maxave - minave >= eps){
        
        // 设置当前的均值 
        midave = (minave+maxave) / 2;
        
        // 判断当前数组是否存在能大于该平均值的序列（长度不低于 m） 
        if(anySeq(ary, n, m, midave)) minave = midave;
        else maxave = midave;
    } 
    
    // 进行放大后再输出 
    cout<<int(maxave*1000)<<endl;
    
    return 0;
}

MT2068 高数考试

难度：黄金时间限制：1秒占用内存：128M

题目描述

高数考完了，又到了数学老师难办的时候。数学老师想捞同学一把，她总是要一遍遍地给某些同学增加分数（均为正整数），又要注意最低分是多少。由于工作量很大，你能帮帮她吗?

格式

输入格式：第一行有两个整数 $n,\ p$ 分别表示学生数与增加分数的次数；
第二行有 $n$ 个整数 $a_1-a_n$ ，代表各个学生的初始成绩；
接下来 $p$ 行，每行有三个数 $x, y, z$ 表示给第 $x$ 个到第 $y$ 个学生每人增加 $z$ 分。
输出格式：输出仅一行，代表更改分数后，全班的最低分。

样例 1

输入：3 2
1 1 1
1 2 1
2 3 1

输出：2

备注

对于40%的数据，有 $n\le{10}^3；
对于60%的数据，有 $n\le{10}^4；
对于80%的数据，有 $n\le{10}^5；
对于100%的数据，有 $n\le{5\times10}^6；
$p\le n，学生初试成绩 \le100,\ z\le100$

相关知识点： 前缀和与差分

题解

这道题的要求是，系统给出若干组操作请求（三个参数 $x, y, z$ ），每次请求都要求你将区间 $\left[x,y\right]$ 中的所有数加上 $z$ ，其本质更像一道 “模拟” 类型的题。但是看数据范围， $n$ 最大能取到 $5×10^6$ ，且 $p\le n$ 。所以，若真的每次都对区间 $\left[x,y\right]$ 进行加法运算肯定会超时。因此，这需要用到一些特殊的数据结构。

对于要对连续数组进行统一增减操作的情形，有一个专门的数据结构：差分（尚不清楚这一数据结构的同学可移步至：前缀和与差分）。

下面对其进行简单的讲解。首先，差分数组的定义如下：
$s u b f i x [i] = a ry [i] - a ry [i - 1]$
其中， $subfix[\ ]$ 为差分数组， $ary[\ ]$ 为输入的原数组。

从差分数组的定义不难看出，其记录了连续数组中的差值情况。如果我们对数组中的某段连续子段进行统一增减操作，那对这一系列的数据而言，他们的相对大小是不会发生改变的；放眼整个数组，其仅会影响该子段首尾两个数在其边界处的相对大小。例如，对以下数组（假设数组的索引从1开始计数）：
$ary[\ ]=\{1,2,3,4,5,6,7,8\}$

可得到其对应的差分数组为：
$subfix[\ ]=\{1,1,1,1,1,1,1,1\}$

若我们对原数组在区间\left[3,\ 6\right]\ 的数都增加4，则得到：
$ary[\ ]=\{1,2,7,8,9,10,7,8\}$
其对应的差分数组为：
$subfix[\ ]=\{1,1,5,1,1,1,-3,1\}$
观察数组 $ary[\ ]$ 在进行区间增值操作前后，尽管 $ary[\ ]$ 发生了相当多的变动（即指定区间中的所有数），但在其对应的差分数组中，仅有两处发生改变：一是指定增值操作区间的起始位置，二是指定增值操作区间结尾处的下一个位置。由此可知，利用差分数组来记录原始数组时，当对原始数组进行长度为 $m$ 的统一增减操作时，其能将时间复杂度由 $O\left(m\right)$ 降至常数级。

同时，基于差分数组公式，我们将其移项可得到：
$a ry [i] = s u b f i x [i] + a ry [i - 1]$

又因为差分数组在构建时，有： $a ry [1] = s u b f i x [1]$ ，于是可得到从差分数组还原原始数组的公式如下：
$ary[i]=\sum_{j=1}^isubfix[j]$

于是，可写出求解本题的完整代码如下（已 AC）：

/*
    MT2068 高数考试 
*/

#include<bits/stdc++.h> 
using namespace std;

const int MAX = 5e6+5;
int ary[MAX], sub[MAX];

int main( )
{
    // 录入数据 
    int n,p,x,y,z,minScore=MAX; 
	cin>>n>>p; 

    // 录入分数时同时记录差分数组 
    for(int i=1;i<=n;i++){
        cin>>ary[i];
        sub[i] = ary[i] - ary[i-1];
	}

	// 录入操作时只需要对差分数组进行修改 
    while(p--){
        cin>>x>>y>>z;
        sub[x] += z;
        sub[y+1] -=z;
	}

    // 还原数组并找出最小值 
    for(int i=1;i<=n;i++){
        ary[i] = ary[i-1] + sub[i];
        minScore = min(minScore, ary[i]);
	}

    // 输出最低分数 
	cout<<minScore<<endl;

    return 0;
}

MT2069 等差

难度：钻石时间限制：1秒占用内存：256M

题目描述

学完等差数列的小码哥神清气爽，他想在一长串数中找到等差的部分。
他给你一个整数数组 nums，要求该数组中所有为等差数组的子数组个数（等差数组子数组，指的是至少 3 个数的连续数组成等差数列）。

格式

输入格式：一个整数数组；
输出格式：一个非负整数。

样例1

输入：1 2 3 4

输出：3

备注

数组长度不超过 5000，元素范围在 -1000 到 1000 之间。

相关知识点：前缀和与差分

题解

这道题要求我们寻找指定数列中的等差子序列个数（子序列长度不低于 3）。
等差数列要求每个数之间的差值相同，如： ${1, 2, 3, 4\}$ 是一个等差数列，其差分数组为 ${1,1,1,1\}$ ；而 ${1, 3, 2, 4\}$ 不是，因为它的差分数组为 ${1,2,-1,2\}$ 。同时，这道题还有一个点需要注意，比如数列 ${1, 2, 3, 4\}$ ，其实该数列含有 3 个等差子序列，分别是：

${1, 2, 3\}$
${1, 2, 3, 4\}$
${2, 3, 4\}$

这在编码时可用一个二重循环得到。但其实这里存在规律：对于长度为 $n$ 的序列，其包含的子序列个数为： $1+2+\ldots+(n-1)\ =\frac{n(n-1)\ }{2}$ 。所以，为加快计算速度这里可直接用此公式进行计算。但是需要注意一点，在本题中，由于限制了子序列的长度不低于 3，因此我们在拿到长度为 $n(n\geq3)$ 的序列时，其子序列的个数应该为： $1+2+\ldots+(n-2)=\frac{(n-1)(n-2)}{2}$ 。

总结一下求解思路：

录入数据并构建差分数组；
扫描差分数组，当存在不低于2个相同元素时，说明当前出现了一个等差序列。接下来通过一个指针向后扫描，直到找到一个与该元素不同的值（或超出数组范围）为止；
叠加当前等差子序列个数： $\frac{(n-1)(n-2)}{2}$ ；
输出全部子序列个数。

下面给出基于以上思路得到的完整代码（已 AC）：文章来源地址https://www.toymoban.com/news/detail-457122.html

/*
    MT2069 等差 
*/

#include<bits/stdc++.h> 
using namespace std;

const int MAX = 5e3+5;
int ary[MAX], sub[MAX];

int main( )
{
    // 录入数组内容的同时构建查分数组
    int num, index, n=0, ans = 0; 
    while(cin>>num){
        ary[++n]=num;
        sub[n] = ary[n] - ary[n-1];
    }

    // 遍历差分数组寻找等差数列
    // 显然，当差分数组中存在至少两个连续相同的数时，表明当前出现了等差数列
    for(int i=2;i<=n;i++){
        // 定义后向扫描指针 
        index = i+1;
        
        // 寻找与当前元素不同取值的元素位置 
        while(index<=n && sub[index]==sub[i]) ++index;
        
        // 计算并叠加当前序列中的所有等差子序列 
        ans += (index-i)*(index-i-1)/2;
        
        // 循环扫描指针跳跃（注：由于 for 循环里会执行 i++，因此这里跳跃 i 至 index-1） 
        i = (index-1);
    } 
    
    // 输出等差子序列个数
    cout<<ans<<endl;
    
    return 0;
}

END

到了这里，关于【马蹄集】第十二周作业的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

【马蹄集】第十二周作业

前缀和与差分专题

MT2056 二阶前缀和

难度：黄金 时间限制：1秒 占用内存：128M

题目描述

格式

样例 1

备注

题解

MT2057 门票

难度：钻石 时间限制：1秒 占用内存：128M

题目描述

格式

样例1

备注

题解

MT2058 最大的平均值

难度：黄金 时间限制：1秒 占用内存：128M

题目描述

格式

样例 1

备注

题解

MT2068 高数考试

难度：黄金 时间限制：1秒 占用内存：128M

题目描述

格式

样例 1

备注

题解

MT2069 等差

难度：钻石 时间限制：1秒 占用内存：256M

题目描述

格式

样例1

备注

题解

END

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

难度：黄金时间限制：1秒占用内存：128M

难度：钻石时间限制：1秒占用内存：128M

难度：黄金时间限制：1秒占用内存：128M

难度：黄金时间限制：1秒占用内存：128M

难度：钻石时间限制：1秒占用内存：256M