Even More Odd Photos

题意

给定 N 头牛的品种编号。要把所有牛分成若干组，并把这些组排成一行。

第 1 组编号和必须是偶数，第 2 组必须是奇数，第 3 组又是偶数，依次交替。求最多能分成多少组。

思路

暴力想法

小数据可以只记录剩余偶数牛和奇数牛的数量，然后 DFS 枚举当前组使用多少头偶数牛、多少头奇数牛：

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71/**
 * 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:45
 * update_at: 2026-07-11 13:49
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

int memo[15][15][2];
bool vis[15][15][2];

int dfs(int even_cnt, int odd_cnt, int need_parity) {
    if (even_cnt == 0 && odd_cnt == 0) {
        return 0;
    }

    if (vis[even_cnt][odd_cnt][need_parity]) {
        return memo[even_cnt][odd_cnt][need_parity];
    }
    vis[even_cnt][odd_cnt][need_parity] = true;

    int best = -1000000;

    // 枚举当前组使用多少头偶数牛、多少头奇数牛。
    for (int use_even = 0; use_even <= even_cnt; use_even++) {
        for (int use_odd = 0; use_odd <= odd_cnt; use_odd++) {
            if (use_even == 0 && use_odd == 0) {
                continue;
            }
            if (use_odd % 2 != need_parity) {
                continue;
            }

            int next_value = dfs(even_cnt - use_even, odd_cnt - use_odd, 1 - need_parity);
            if (best < next_value + 1) {
                best = next_value + 1;
            }
        }
    }

    memo[even_cnt][odd_cnt][need_parity] = best;
    return best;
}

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

    int n;
    cin >> n;

    int even_cnt = 0;
    int odd_cnt = 0;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (x % 2 == 0) {
            even_cnt++;
        } else {
            odd_cnt++;
        }
    }

    cout << dfs(even_cnt, odd_cnt, 0) << '\n';

    return 0;
}

这个暴力能直接验证“每组只关心奇偶性”，但满数据下可以推公式。

只看奇偶数量

设：

text

1
2E = 偶数牛数量
O = 奇数牛数量

如果每头牛都单独成组，那么组的奇偶性就是牛本身的奇偶性。由于组序列从偶数组开始交替，所以偶数组数量只能等于奇数组数量，或者比奇数组多 1。

当 O > E，奇数牛太多。两个奇数牛放在同一组时，和为偶数，所以可以把两个奇数牛“合成”一个偶数组：

text

1
2O -= 2
E += 1

重复直到 $O <= E$ 。

当 E > O + 1，偶数组太多。多出来的偶数牛无法单独形成新组，只能并入已有偶数组，所以有效的偶数组数量最多是：

text

1O + 1

最后答案就是调整后的 E + O。

代码

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/**
 * 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:45
 * update_at: 2026-07-11 13:49
 */
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;

    int even_cnt = 0;
    int odd_cnt = 0;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (x % 2 == 0) {
            even_cnt++;
        } else {
            odd_cnt++;
        }
    }

    // 两个奇数可以合成一个偶数组，相当于 odd 减 2，even 加 1。
    while (odd_cnt > even_cnt) {
        odd_cnt -= 2;
        even_cnt++;
    }

    // 偶数组最多只能比奇数组多 1 个，因为照片从偶数组开始交替。
    if (even_cnt > odd_cnt + 1) {
        even_cnt = odd_cnt + 1;
    }

    cout << even_cnt + odd_cnt << '\n';

    return 0;
}

复杂度

统计奇偶数量并调整，时间复杂度为 $O(N)$ 。

只使用常数个计数变量，空间复杂度为 $O(1)$ 。

总结

这题的关键是只保留奇偶信息。

两个奇数可以合成一个偶数组；而分组从偶数组开始交替，所以偶数组数量最多只能比奇数组多 1。

目录

题意

思路

暴力想法

只看奇偶数量

代码

复杂度

总结