CF1157A Reachable Numbers 题解

发布于 2020-09-26  483 次阅读


作为一道 CF 的 A 题,私以为现有的题解都把这题做麻烦了或是太过于暴力了,决定提供一种其他的解法。

题目链接 题意非常明朗,不再赘述。

文章目录

解析

作为 A 题,显然这题是可以通过数学方法解决的,因此虽然数据范围的确可以暴力过,但是我第一个想到的并不是暴力。

我们首先考虑到,如果只有一位数,显然是一定会产生 $1 \sim 9$ 这 $9$ 种情况的,那接下来每一位呢?我们从最后一位开始倒退,考虑其能执行几次运算,也就是能产生几个不同的数,我们发现,第 $i$ 位数能支持的运算次数一定为 $9-a_i$ 次( $a_i$ 为第 $i$ 位上的数字)。因此,我们只需要把运算次数和,即除了第一位以外能够产生的不同数的数目求出来,再加上第一位的 $9$ 种情况以及该数本身的一种情况合计 $10$ 种,就可以了。

代码

#include<bits/stdc++.h>
using namespace std;
int num,a[15],cnt,ans=10;//第一位和该数本身的贡献为 10
int main(){
    scanf("%d",&num);
    while(num){
        a[++cnt]=num%10;
        num/=10;
    }
    if(cnt==1) ans--;//若该数只有一位,该数本身和第一位的贡献算重了,减去即可 
    for(int i=1;i<cnt;i++)
        ans+=9-a[i];//除了第一位以外每一位的贡献 
    printf("%d\n",ans);
    return 0;
}

月流华 岁遗沙 万古吴钩出玉匣