当前位置：网站首页>51nod 1413 权势二进制

51nod 1413 权势二进制

2022-07-15 11:44:00 【51CTO】

一个十进制整数被叫做权势二进制，当他的十进制表示的时候只由0或1组成。例如0，1，101，110011都是权势二进制而2，12，900不是。

当给定一个n的时候，计算一下最少要多少个权势二进制相加才能得到n。

Input

单组测试数据。第一行给出一个整数n (1<=n<=1,000,000)

Output

输出答案占一行。

Input示例

Output示例

一开始做这个我掏出了祖传的DFS，但并没有写出来。

然后观察数据，发现可以将所给的n的每一位都拿出来，然后找一个跟n一样长的权势二进制数，n的每一位如果大于1，这个二进制数的那一位就等于1，否则等于0，然后这个数绝对是能以最小加到n的，然后n减去这个数，再重复这些步骤，就能算出来了。

代码如下：

       
       #include<cstdio>
       
       #include<cstring>
       
       #include<iostream>
       
       #include<algorithm>
       
       using 
       
       namespace 
       
       std;
       
       #define N 300
       
       #define inf 0xfffffff
       
       int 
       
       n,
       
       Min;
       
       int 
       
       main(){
       
       int 
       
       i,
       
       j,
       
       m,
       
       r,
       
       x;
       
       scanf(
       
       "%d",
       
       &
       
       n);
       
       int 
       
       cnt
       
       =
       
       0,
       
       q;
       
       j
       
       =
       
       1;
       
       while(
       
       n){
       
       int 
       
       len
       
       =
       
       0;
       
       r
       
       =
       
       n;
       
       while(
       
       r){
       
       r
       
       /=
       
       10;
       
       len
       
       ++;
       
      }
       
       r
       
       =
       
       n,
       
       j
       
       =
       
       1,
       
       q
       
       =
       
       0;
       
       for(
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       len;
       
       i
       
       ++){
       
       int 
       
       x
       
       =(
       
       r
       
       /
       
       j)
       
       %
       
       10;
       
       if(
       
       x
       
       >=
       
       1) 
       
       x
       
       =
       
       1;
       
       else 
       
       x
       
       =
       
       0;
       
       q
       
       +=(
       
       x
       
       *
       
       j);
       
       j
       
       *=
       
       10;
       
      }
       
       n
       
       -=
       
       q;
       
       cnt
       
       ++;
       
    }
       
       printf(
       
       "%d\n",
       
       cnt);
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15719342/5475075

当前位置：网站首页>51nod 1413 权势二进制

51nod 1413 权势二进制

边栏推荐

猜你喜欢

随机推荐