P9956 [USACO20DEC] Daisy Chains B 题解

2023gdgz01 · 2023-12-17 22:02:51 · 题解

此题只需按题意模拟即可。我们可以枚举出拍照区间 (i,j)，然后加和算平均值，最后统计答案即可。时间复杂度 O(n^3)。

代码如下：

#include <cstdio>

int n, ans, a[105], sum[105];
double temp;

int main() {
    scanf("%d", &n);
    for (register int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        sum[i] = sum[i - 1] + a[i]; //为了方便，我们使用前缀和，但时间复杂度相同
    }
    for (register int i = 1; i <= n; ++i) {
        for (register int j = i; j <= n; ++j) {
            temp = (sum[j] - sum[i - 1]) * 1.0 / (j - i + 1); //算平均值
            if (temp == (int)temp) //防止本来除不尽但是四舍五入的情况
                for (register int k = i; k <= j; ++k)
                    if (a[k] == temp) {
                        ++ans;
                        break; //有答案就 break
                    }
        }
    }
    printf("%d", ans);
    return 0;
}

AC 链接