题意 : 按照题目给定的规则将公里转化成英里,就是每个数都可以用斐波那契数列里的数表示,每个数都有一个编码,21可以表示成(1,0,0,0,0,0,0) ,13可以表示成(1,0,0,0,0,0),42可以表示成 (1,0,0,1,0,0,0,0),将这个数的编码的最后一位去掉,所以42就变成 (1,0,0,1,0,0,0),然后倒过来 (0,0,0,1,0,0,1),第四个和第7个是1,然后斐波那契中第四个和第七个数加起来就是26.
思路 : 这个题我一开始卡了很久,因为我实在不明白题目表达了什么意思,也不知道42为什么就可以表示成那样的,后来就算了一下,42等于34+8,正好是斐波那契中的第5个数和第8个数,所以就是(0,0,0,0,1,0,0,1),然后再倒过来就是题目中给的了,因为题目中还要再倒,所以自己做的时候就不用倒了。
#include#include #include using namespace std ;int fib[30] ,vis[30];void chart(){ fib[1] = 1 ; fib[2] = 2 ; for(int i = 3 ; i < 30 ; i++) fib[i] = fib[i-1]+fib[i-2] ;}int main(){ int n ,m; scanf("%d",&n) ; chart() ; while(n--) { scanf("%d",&m) ; memset(vis,0,sizeof(vis)) ; for(int i = 29 ; i >= 1 ; i--) { if(m <= 0) break ; if(fib[i] <= m) { m -= fib[i] ; vis[i] = 1 ; } } int ans = 0 ; for(int i = 2 ; i < 30 ; i++) ans += vis[i]*fib[i-1] ; printf("%d\n",ans) ; } return 0 ;}