当前位置：首页 > news >正文

打卡信奥刷题（2942）用C++实现信奥题 P5847 [IOI 2005] mea

news 2026/9/1 16:35:47

P5847 [IOI 2005] mea

题目描述

考虑一个非递减的整数序列S1,⋯ ,Sn+1S_1,\cdots,S_{n+1}S1,⋯,Sn+1(Si≤Si+1S_i \le S_{i+1}Si≤Si+1，1≤i≤n1 \le i \le n1≤i≤n)。序列M1⋯MnM_1 \cdots M_nM1⋯Mn是定义在序列SSS的基础上，关系式为Mi=Si+Si+12M_i = \frac{S_i + S_{i+1}}{2}Mi=2Si+Si+1（1≤i≤n1 \le i \le n1≤i≤n），序列MMM叫做序列SSS的平均数序列。

例如序列1,2,2,41,2,2,41,2,2,4的平均数序列为1.5,2,31.5,2,31.5,2,3. 注意到平均数序列中的元素可能为小数。但是本题的任务只是处理平均数序列都为整数的情况。

给出一个nnn个数字的非递减的整数序列M1,M2,⋯ ,MnM_1,M_2,\cdots,M_nM1,M2,⋯,Mn。请你计算出：序列S1,⋯ ,Sn+1S_1,\cdots,S_{n+1}S1,⋯,Sn+1的平均序列是M1,⋯ ,MnM_1,\cdots,M_nM1,⋯,Mn。求满足以上条件的序列SSS的总个数。

任务：从标准输入文件中读入一个非递减的整数序列。计算出平均序列是给出序列的整数序列的总个数。把计算结果写到标准输出文件中。

输入格式

输入文件的第一行包含一个整数nnn（2≤n≤5×1062 \le n \le 5 \times 10^62≤n≤5×106）。

接下来的nnn行包含了这个给出的整数序列M1,⋯ ,MnM_1,\cdots,M_nM1,⋯,Mn。第i+1i+1i+1行包含一个整数MiM_iMi(1≤Mi≤1091 \le M_i \le 10^91≤Mi≤109)。

输出格式

输出文件仅一行，即所求答案。

输入输出样例 #1

输入 #1

3 2 5 9

输出 #1

说明/提示

样例说明

一共存在444种序列，它们的平均数序列都是2,5,92,5,92,5,9。这四种序列如下：

2,2,8,102,2,8,102,2,8,10
1,3,7,111,3,7,111,3,7,11
0,4,6,120,4,6,120,4,6,12
−1,5,5,13-1,5,5,13−1,5,5,13

数据范围

对于50%50\%50%的数据，2≤n≤10002 \le n \le 10002≤n≤1000，1≤Mi≤2×1041 \le M_i \le 2 \times 10^41≤Mi≤2×104；

对于100%100\%100%的数据，2≤n≤5×1062 \le n \le 5 \times 10^62≤n≤5×106，1≤Mi≤1091 \le M_i \le 10^91≤Mi≤109。

C++实现

#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<cmath>#include<algorithm>#defineintlonglongusingnamespacestd;intn,l,r,s[5000005],m[5000005];signedmain(){scanf("%lld",&n);l=-9223372036854775807,r=9223372036854775807;for(inti=1;i<=n;i++)scanf("%lld",&m[i]);for(inti=1;i<=n;i++){//前缀和if(i&1)s[i]=s[i-1]+m[i];elses[i]=s[i-1]-m[i];}for(inti=1;i<=n;i++){//求左、右端点if(i&1)r=min(r,(s[i-1]<<1ll)+m[i]);elsel=max(l,(s[i-1]<<1ll)-m[i]);}printf("%lld",max(r-l+1,0ll));return0;}