自动搬运

查看原文

来自洛谷，原作者为

	Fire_flame 乐观乐观再乐观

搬运于2025-08-24 22:51:03，当前版本为作者最后更新于2023-06-12 22:38:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\mathbf{Solution}$

子任务 $1$：因为平均数小于等于 $3$，也就是说不会出现 $5$，输出 $0$ 即可。

子任务 $2$：平均数是 $5$，最大值也不超过 $5$，也就是说 $a_1=a_2=\dots=a_n=5$。

那么答案即为：

不难发现，枚举左端点 $l$，那么以左端点为 $l$ 的区间的贡献是 $(n - l + 2)\times(n - l + 1)\div 2$。

时间复杂度 $O(n)$。

子任务 $3$：枚举左端点，右端点，然后 $O(n)$ 求解答案即可。

时间复杂度 $O(n^3)$。

子任务 $4$：

因为序列单调不上升，而且最大数为 $5$。

所以如果出现了 $5$，肯定是只有前面连续的一段。

即可转化成子任务 $2$。

子任务 $5$：

考虑递推，假设当前右端点枚举到了第 $r$ 位，已经遍历了连续 $cnt$ 个 $5$。

• 如果 $a_r\neq5$，$cnt$ 清零，不添加贡献。

• 如果 $a_r=5$，考虑左端点 $l$：

  1. 首先 $cnt$ 要记得加一。
  2. 如果左端点 $l\le r-cnt$，每一个区间贡献添加 $cnt$。总贡献添加 $(r - cnt + 1) \times cnt$。
  3. 如果左端点 $r-cnt+1\le l\le r$，总贡献添加 $cnt\times(cnt-1)\div 2$。

最后统计答案即可。

标程：

#include<bits/stdc++.h>//by Fire_flame
#define int long long
using namespace std;
const int MAXN = 5e5 + 5, MOD = 1e9 + 7;
int n, ans, cnt, a[MAXN];
signed main(){
	scanf("%lld", &n);
	ans = 0, cnt = 0;
	for(int i = 1;i <= n;i ++)scanf("%lld", &a[i]);
	for(int i = 1;i <= n;i ++){
		if(a[i] == 5)cnt ++;
		else cnt = 0;
		ans += (i - cnt + 1) * cnt % MOD + cnt * (cnt - 1) / 2 % MOD;
		ans %= MOD;
	}
	printf("%lld", ans);
	return 0;
}