fibonacci进制
Fibonacci进制
https://ac.nowcoder.com/acm/problem/15663
这道题就是通过位运算的方法实现的.
具体可以把比如45位二进制都初始化为一,再从高位到低位进行判断,判断此位能否给置为0(因为高位为零有利于最后保留低位的一,最终得到最小的数字.
具体展开有多种多样.
里面对数据比较苛刻,所以可以通过long long 类型予以解决.
int 类型的范围一般是-20亿~20亿,long long 就比他大得多了.
除了位运算还可以枚举,不过dfs枚举的话,大约2^45次运算,级别就太高了,运行不下去的.
最后一点就是为何会有45,而不是46,47等,原因是45时f[45]已经满足题目中数据要求,没必要更大的数了.
