Codeforces Round 1070 (Div. 2) C. Odd Process

发表于 分类于 阅读次数：

解题报告：C. Odd Process

题目概述

You have n coins with denominations a1,a2,…,an and a natural number k. You also have a bag, which is initially empty, where you can place coins. You need to perform exactly k actions. In each action, you take one coin from those you have left and put it in your bag. After that, you can no longer take that coin.

At the same time, you have a cat that loves even numbers, so every time the sum of the denominations of the coins in your bag becomes even, your cat empties the bag, meaning it takes all the coins to a place known only to it, and the bag is empty again. Note that the bag is emptied every time the sum becomes even during the process of adding coins, not just at the very last moment.

Let your score be the sum of the denominations of the coins in the bag. Your task is to perform k actions such that your final score is maximized. Find the answer for all 1≤k≤n.

问题分析

我们需要选择硬币的放入顺序，以最大化最终得分。关键在于理解奇偶性的变化规律：

  • 奇数 + 奇数 = 偶数
  • 偶数 + 偶数 = 偶数
  • 奇数 + 偶数 = 奇数

放入硬币后，如果总和为偶数，袋子被清空（总和变为 0）。因此，为了在操作结束时袋子不为空，最后一次操作后的总和必须是奇数。

关键观察

  1. 最终得分非零的条件：必须至少使用一个奇数，且最后一段（最后一次清空之后的操作序列，或从开始就没有清空）只能包含一个奇数和若干个偶数（因为再放入一个奇数会触发清空）。
  2. 构造方式：先将最大的奇数和较大的偶数依次放入，若偶数放完，保证接下来放入的奇数个数为偶数，否则将最小的偶数换为奇数。

算法设计

将数组按奇偶分开从大到小排序，放入顺序为最大奇数，最大偶数，第二大偶数……，注意考虑不存在奇偶数的边界情况。

代码实现

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;
void sas(const std::vector<long long>& input, std::vector<long long>& odd, std::vector<long long>& even) {
    for (long long num : input) {
        if (num % 2 != 0) {
            odd.push_back(num);
        }
        else {
            even.push_back(num);
        }
    }

    std::sort(odd.begin(), odd.end(), std::greater<long long>());
    std::sort(even.begin(), even.end(), std::greater<long long>());
    if (even.size() == 0) {
        even.push_back(0);
    }
}

int main() {
    long long t;
    std::cin >> t;
    while (t--) {
        long long n,i;
        cin >> n;
        std::vector<long long> a(n), odd, even;
        for (i = 0; i < n; i++) {
            std::cin >> a[i];

        }
        sas(a, odd, even);
        if (odd.size() == 0) {
            for (i = 1; i <= n; i++) {
                std::cout << 0 << " ";
            }
            
        }
        else if(odd.size()%2 == 1) {
            cout << odd[0] << " ";
            long long sum1 = 0;
            if (even[0] != 0) {
                for (i = 0; i <= even.size() - 1; i++) {
                    if (even[i] == 0) {
                        break;
                    }

                    sum1 += even[i];
                    cout << sum1 + odd[0] << " ";
                }
                if (odd.size() > 2) {

                    for (i = 0; i <= odd.size() - 2; i++) {
                        if (i % 2 == 0) {
                            cout << sum1 - even[even.size() - 1] + odd[0] << " ";
                        }
                        else {
                            cout << sum1 + odd[0] << " ";
                        }
                    }



                }
            }
            else {
                for (i = 0; i < n - 1; i++) {
                    if (i % 2 == 0) {
                        cout << 0 << " ";
                    }
                    else {
                        cout << odd[0] << " ";
                    }
                }
            }
            
        }
        else {
            cout << odd[0] << " ";
            long long sum1 = 0;
            if (even[0] != 0) {
                for (i = 0; i <= even.size() - 1; i++) {

                    sum1 += even[i];
                    cout << sum1 + odd[0] << " ";
                }
                if (odd.size() > 2) {
                    for (i = 0; i <= odd.size() - 3; i++) {
                        if (i % 2 == 0) {
                            cout << sum1 - even[even.size() - 1] + odd[0] << " ";
                        }
                        else {
                            cout << sum1 + odd[0] << " ";
                        }
                    }
                    cout << 0;
                }
                else {
                    cout << 0;
                }
            }
            else {
                for (i = 0; i < n - 1; i++) {
                    if (i % 2 == 0) {
                        cout << 0 << " ";
                    }
                    else {
                        cout << odd[0] << " ";
                    }
                }
            }
        }
        
        std::cout << endl;
    }

    return 0;
}

比赛时被这题恶心了很久才拉出来的代码，也是能让你们吃上了😀