题解：CF305A Strange Addition

OIerJiang_1017 · 2024-12-23 17:26:55 · 题解

CF305A 题目传送门

题目大意

对于一个整数对，如果这对整数中至少有一个数中包含有数字 0，那么就允许这两个数进行求和运算。例如，整数对 505 和 50 可以求和，但整数对 1 和 4 就不能求和。给定一个包含 k 个不同非负整数 d_1,d_2,d_3,\dots,d_k 的集合，请你确定从集合中做多能选择多少个整数，使得从这些数中任意选定两个数都可以求和。

解决思路

根据数据范围 0 \leq x \leq 100 分类讨论：

• 当 x=0 或 x=100 时 x 可以与任何数相加, 直接存入数组
• 当 1 \leq x \leq 9 时，如果没有出现过 x 为一位数而且 x 个位为零的情况，则将 x 存进数组并标记 f1=true。
• 当 10 \leq x \leq 99 时：
  • 如果没有出现过 $x$ 为两位数而且 $x$ 个位为零的情况 将 $x$ 存进数组并标记 $f2=true$。
  • 更新 $z=x$, 因为十位与个位都不是零的数最多用一次如果 $f1$ 与 $f2$ 都为零而且 $z$ 不是 $0$， 将 $z$ 加入到数组里。

代码展示

#include <iostream>
using namespace std;

const int N = 110;
int n, d[N], x, cnt, z;
//d[]为最终要输出的数d
//cnt是d数组下标
bool f1, f2;
//f1记录是否出现过 x为一位数 && x个位为零 的情况
//f2记录是否出现过 x为两位数 && x个位为零 的情况

int main()
{
    scanf("%d", &n);//建议scanf,更快
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &x);
        if(x == 0 || x == 100)//第一种情况
            d[++cnt] = x;
        if(1 <= x && x <= 9)//第二种情况
            if(f1 == false)
            {
                d[++cnt] = x;
                f1 = true;
            }
        if(10 <= x && x <= 99)
            if(x % 10 == 0)
            {
                if(f2 == false)
                {
                    d[++cnt] = x;
                    f2 = true;
                }
            }
            else z = x;
    }
    if(f1 == false && f2 == false && z != 0)
        d[++cnt] = z;
    printf("%d\n", cnt);//建议printf,更快
    for(int i = 1; i <= cnt; i++)
        printf("%d ", d[i]);
    return 0;
}