策略

· · 个人记录

题目大意

给定一个集合 A，从集合 A 中删去一个数 a，将集合 A 中剩下的元素分成两个不同的子集 A_1,A_2且这两个子集都不是空集。问：\sum_{i = 1}^{|A_1|} = \sum_{i = 1}^{|A_2|} 是否成立。

思路：

根据题意我们可以得出：\sum_{i = 1}^{|A_1|} + \sum_{i = 1}^{|A_2|} + a = \sum_{i = 1}^{|A|}\

那我们不妨设 $\sum_{i = 1}^{|A_1|} = \sum_{i = 1}^{|A_2|} = m \therefore \sum_{i = 1}^{|A|} = 2m + a \Rightarrow 2m = \sum_{i = 1}^{|A|}-a$\ $\because 2m \text{为偶数} \therefore \sum_{i = 1}^{|A|}-a\text{为偶数}

假设 a 为偶数，那么 \sum_{i = 1}^{|A|} 一定也为偶数。又因为集合 A 中一定存在一个奇数，但是不管是奇数个偶数+奇数还是偶数个偶数+奇数结果一定是奇数，故假设不成立。

所以 a 一定是奇数，那么\sum_{i = 1}^{|A|}一定也为奇数。又因为不管奇数还是偶数个偶数相加结果一定为偶数，所以集合 A 的元素一定都是奇数。又因为奇数和奇数相加为奇数，偶数个奇数相加为偶数，所以集合 A 的元素个数为奇数。

所以我们只需要判断集合 A 的元素个数和元素之和是否都是奇数，如果同时满足则可以，输出 Yes；否则输出 No。

代码：

#include <bits/stdc++.h>
using namespace std;

int x;
int cnt, sum;
// cnt:计算元素个数，sum:计算元素之和

int main() {
    while (cin >> x) {
        if (x != -1) cnt ++;
        if (x != -1) sum += x;
    }

    // 判断是否满足条件:元素个数和元素之和都是奇数
    if (cnt % 2 == 0 || sum % 2 == 0) cout << "No";
    else if (cnt % 2 != 0 && sum % 2 != 0)cout << "Yes";
    return 0;
}