1537. 【中山市第十一届信息学邀请赛决赛】未命名 （noname）

题目描述

这是一个独一无二的世界，所以有 N 张写有互不相同的自然数的卡片，第 i 张卡片写着 Ai ，现在你得到了一个未命名的空白卡片，想在上面写上一个自然数 x 满足以下条件：
1.x 不等于任意一张卡片上的数字。
2.x 可以表示为两张互不相同卡片的数字之和。
现在，你想知道有哪些自然数 x 可以写在空白卡片上。

输入

第一行一个正整数 N，表示已写有自然数的卡片数量。
第二行有 N 个用空格隔开的互不相同的自然数，表示卡片上的自然数。

输出

第一行一个正整数 M，表示可以写在空白卡片上的数字的个数。
第二行有 M 个用空格隔开的自然数，表示可以写在空白卡片上的数字，需要从小到大输出。

样例输入

4
4 9 3 5 

样例输出

5
7 8 12 13 14 

数据范围限制

对于 15% 的数据，N ≤ 5，Ai ≤ 10。
对于 30% 的数据，N ≤ 50，Ai ≤ 100。
对于 40% 的数据，N ≤ 200，Ai ≤ 5000。
对于 100% 的数据，3 ≤ N ≤ 2000，0 ≤ Ai ≤ 100000。

提示

满足条件 2 的数有 7, 8, 9, 12, 13, 14，但是 9 在已有的卡片出现过，不符合条件 1，因此答案有7, 8, 12, 13, 14。

Code

#include <stdio.h>

#define max(a, b) ((a) > (b) ? (a) : (b))

int cnt1[200001] = {0};
int cnt2[200001] = {0};
int result[200000] = {0}; // 最多可能满足条件的数有很多
int a[2005];
int n;

int main() {
    scanf("%d", &n);
    int maxd = 0; // 记录最大的卡片数字，以便后续遍历
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        cnt1[a[i]] = 1;
        if (a[i] > maxd) maxd = a[i];
    }

    // 计算所有不同卡片组合的和
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int sum = a[i] + a[j];
            cnt2[sum] = 1;
        }
    }

    int count = 0;

    for (int i = 1; i <= 200000; i++) {
        // 数字不在已有卡片上，且可由两不同卡片之和得到
        if (cnt1[i] == 0 && cnt2[i] == 1) {
            result[count++] = i;
        }
    }

    printf("%d\n", count);
    for (int i = 0; i < count; i++) {
        printf("%d ", result[i]);
    }
    return 0;
}