Daisy Chains

题意

给定一排 N 朵花，第 i 朵花有 p[i] 片花瓣。

每张照片对应一个连续区间 [l, r]。如果这个区间中存在一朵花，它的花瓣数正好等于区间平均花瓣数，那么这张照片计入答案。

求满足条件的照片数量。

思路

直接枚举

最直接的想法是枚举每张照片 [l, r]，求出区间和，再扫描区间内所有花，判断是否存在一朵花等于平均值：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 13:58
 * update_at: 2026-07-11 13:59
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n;
int p[MAXN]; // p[i] 表示第 i 朵花的花瓣数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }

    int ans = 0;

    // 枚举每一张照片 [l, r]，再检查照片内是否有一朵花等于平均值。
    for (int l = 1; l <= n; l++) {
        for (int r = l; r <= n; r++) {
            int sum = 0;
            for (int k = l; k <= r; k++) {
                sum += p[k];
            }

            int len = r - l + 1;
            bool ok = false;
            for (int k = l; k <= r; k++) {
                if (p[k] * len == sum) {
                    ok = true;
                }
            }

            if (ok) {
                ans++;
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

这个做法是 $O(N^3)$ 。由于本题 $N <= 100$ ，它已经可以通过；不过还可以利用“固定左端点向右扩展”的过程，把判断降到 $O(1)$ 。

固定左端点

固定左端点 l，让右端点 r 从 l 向右移动。

移动过程中维护两个量：

text

1
2sum       当前区间 [l, r] 的花瓣总数
seen[x]   当前区间内是否出现过花瓣数 x

每次加入 p[r] 后，如果平均值是整数：

text

1avg = sum / (r-l+1)

那么只要检查 seen[avg] 是否为真，就知道区间里是否存在平均花。

因为 p[i] <= 1000，所以平均值也不会超过 1000，可以直接用布尔数组记录出现情况。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 13:58
 * update_at: 2026-07-11 13:59
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
const int MAXP = 1005;

int n;
int p[MAXN]; // p[i] 表示第 i 朵花的花瓣数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }

    int ans = 0;

    // 固定左端点，向右扩展区间，同时维护区间内出现过的花瓣数。
    for (int l = 1; l <= n; l++) {
        bool seen[MAXP];
        memset(seen, 0, sizeof(seen));

        int sum = 0;
        for (int r = l; r <= n; r++) {
            sum += p[r];
            seen[p[r]] = true;

            int len = r - l + 1;
            if (sum % len == 0) {
                int avg = sum / len;
                if (seen[avg]) {
                    ans++;
                }
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

复杂度

枚举所有区间共有 $O(N^2)$ 次，每个区间 $O(1)$ 判断，所以时间复杂度为 $O(N^2)$ 。

使用输入数组和 seen[1005]，空间复杂度为 $O(N + 1000)$ 。

总结

这题先要看出“照片”就是连续区间。

直接做 $O(N^3)$ 已经足够，但固定左端点时顺手维护 sum 和 seen[]，可以让每个区间只做一次常数判断。

目录

题意

思路

直接枚举

固定左端点

代码

复杂度

总结