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
4
说明/提示
样例说明
一共存在 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>
#define int long long
using namespace std;
int n,l,r,s[5000005],m[5000005];
signed main()
{
scanf("%lld",&n);
l=–9223372036854775807,r=9223372036854775807;
for(int i=1;i<=n;i++)scanf("%lld",&m[i]);
for(int i=1;i<=n;i++){//前缀和
if(i&1)s[i]=s[i–1]+m[i];
else s[i]=s[i–1]–m[i];
}
for(int i=1;i<=n;i++){//求左、右端点
if(i&1)r=min(r,(s[i–1]<<1ll)+m[i]);
else l=max(l,(s[i–1]<<1ll)–m[i]);
}
printf("%lld",max(r–l+1,0ll));
return 0;
}
后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
