[KMOI R1] 五五五五 （Easy）题解

Fire_flame · 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;
}