CF1157A Reachable Numbers 题解

作为一道 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;
}
本文作者:water_tomato
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇